hdu 1597(矩阵快速幂)

1597: 薛XX后代的IQ

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 228 Solved: 55
[Submit][Status][Web Board]

Description

薛
XX的低IQ是个令人头疼的问题，他的队友深受其害。幸运的是，薛XX非常有钱，所以他买了一些可以提高他的后代的IQ的药。这种药有三个属性，A，B和
P。当薛XX使用这种药的时候，他的基因会发生变化，所以他的儿子的IQ也会跟着变化。假设薛XX的父亲的IQ为X，薛XX自己的IQ为Y，那么薛XX的
儿子的IQ为(A*X+B*Y) mod P。薛XX的孙子的IQ依次类推。
现在给定X和Y，还有药的属性A、B和P，现在他想知道他的N代子孙的IQ（儿子是第一代，孙子是第二代）。

Input

第一行包含一个整数T（T<=100），表示数据组数
每组数据只有一行，包含六个整数X,Y,A,B,P,N（1 ≤ X, Y ≤ 300,1 ≤ A, B ≤ 30, 1≤ P ≤ 300 , 1 ≤ N < 1000000000），含义如题目所述

Output

对于每组数据，输出答案

Sample Input

4

180 80 1 1 190 1

189 83 2 2 190 1

189 83 1 1 190 2

172 73 23 19 273 9999

Sample Output

70

164

165

233

矩阵快速幂,构造矩阵 f[i+1] = a*f[i-1]+b*f[i] . 特征矩阵为 {{b,a},{1,0}}.

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <queue>

#include <string.h>

using namespace std;

typedef long long LL;

struct Maxtri{

    int v[][];

};

int X,Y,a,b,p,n;

Maxtri mult(Maxtri a,Maxtri b){

    Maxtri c;

    for(int i=;i<;i++){

        for(int j=;j<;j++){

            c.v[i][j] = ;

            for(int k=;k<;k++){

                c.v[i][j] = (a.v[i][k]*b.v[k][j]%p+c.v[i][j])%p;

            }

        }

    }

    return c;

}

Maxtri pow_mod(Maxtri ma,int n){

    Maxtri ans;

    ans.v[][] = ans.v[][] = ;

    ans.v[][] = ans.v[][] = ;

    while(n){

        if(n&) ans = mult(ans,ma);

        ma = mult(ma,ma);

        n>>=;

    }

    return ans;

}

int main()

{

    int tcase;

    scanf("%d",&tcase);

    while(tcase--)

    {

        scanf("%d%d%d%d%d%d",&X,&Y,&a,&b,&p,&n);

        Maxtri ori ;

        ori.v[][] = b,ori.v[][] = a;

        ori.v[][] = ,ori.v[][] = ;

        Maxtri ans = pow_mod(ori,n);

        printf("%d\n",(ans.v[][]*Y+ans.v[][]*X)%p);

    }

    return ;

}

秒客网