1597: 薛XX后代的IQ

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 228  Solved: 55

[][][]

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

4180 80 1 1 190 1189 83 2 2 190 1189 83 1 1 190 2 172 73 23 19 273 9999

Sample Output

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

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;struct Maxtri{    int v[2][2];};int X,Y,a,b,p,n;Maxtri mult(Maxtri a,Maxtri b){    Maxtri c;    for(int i=0;i<2;i++){        for(int j=0;j<2;j++){            c.v[i][j] = 0;            for(int k=0;k<2;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[0][0] = ans.v[1][1] = 1;    ans.v[0][1] = ans.v[1][0] = 0;    while(n){        if(n&1) ans = mult(ans,ma);        ma = mult(ma,ma);        n>>=1;    }    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[0][0] = b,ori.v[0][1] = a;        ori.v[1][0] = 1,ori.v[1][1] = 0;        Maxtri ans = pow_mod(ori,n);        printf("%d\n",(ans.v[0][0]*Y+ans.v[0][1]*X)%p);    }    return 0;}