CSU 1597 薛XX后代的IQ

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

很明显，对于这种类似的给出递推公式的都可以用矩阵快速幂解决。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int maxn=;

int a,x,b,y,c,mod;

ll n;

struct Matrix

{

    int a[maxn][maxn];

    Matrix(){memset(a,,sizeof(a));}

    Matrix operator* (const Matrix &p)

    {

        Matrix res;

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

        {

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

            {

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

                {

                    res.a[i][j]+=(a[i][k]*p.a[k][j]%mod);

                }

                res.a[i][j]%=mod;

            }

        }

        return res;

    }

}ans,base;

Matrix quick_pow(Matrix base,ll n)

{

    Matrix res;

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

    {

        res.a[i][i]=;

    }

    while(n)

    {

        if(n&) res=res*base;

        base=base*base;

        n>>=;

    }

    return res;

}

void init_matrix()

{

    ans.a[][]=y;

    ans.a[][]=x;

    ans.a[][]=;

    ans.a[][]=;

    base.a[][]=b;

    base.a[][]=;

    base.a[][]=a;

    base.a[][]=;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d%d%d%d%lld",&x,&y,&a,&b,&mod,&n);

        init_matrix();

        ans=ans*quick_pow(base,n);

        printf("%d\n",ans.a[][]);

    }

    return ;

}

iq

CSU 1597 薛XX后代的IQ