HDU 5667 Sequence【マトリックス高速べき乗】【Euler関数】


テーマリンク
http://acm.hdu.edu.cn/showproblem.php?pid=5667
考え方
fn=𖜇𖒐1,ab,abfcn−1 fn−2,n=1 n=2 others wiseをあげます.fnをお願いします.
まず、両方ともaを底にしていますので、ロゴを取って、aのべき乗wn=b+c×wn−1+wn−2は、行列で素早くべき乗計算できます.
𖐏⎜c 101001Ώn−1×𖐏⎜w 2 w 1 bΏΏ=𖜇𖜇𖜇𖜇
それからfn=awn、これも高速べき乗で計算すればいいです.
注意したいのはAb%C=Ab%です.ϕ(c)+ϕ(c)%Cはc=pが素数なのでϕ(p)=p−1ですので、マトリクス乗算ではモードp−1、awnを計算するとモードpが加算されます.
それから注意したいのですが、a%p=0でwn%p=0の場合、awn%pは0となりますが、a 0の場合は1となりますので、特に判定します.
ACコード
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll MOD;
const int N=3;
struct matrix
{
    ll mat[N][N];
    matrix(void)
    {
        memset(mat,0,sizeof mat);
    }
    matrix friend operator * (matrix a, matrix b)
    {
        int n=N;
        matrix ans;
        for(int i=0 ; i<n ; ++i)
        {
            for(int j=0 ; j<n ; ++j)
            {
                int sum=0;
                for(int k=0 ; k<n ; ++k)
                {
                    sum+=a.mat[i][k]*b.mat[k][j]%(MOD-1);
                    sum%=(MOD-1);
                }
                ans.mat[i][j]=sum;
            }
        }
        return ans;
    }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll n,a,b,c;
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&MOD);
        if(n==1)
        {
            printf("1
"
); continue; } if(n==2) { printf("%lld
"
,b); continue; } if(a%MOD==0) { printf("0
"
); continue; } matrix A; A.mat[0][0]=c;A.mat[0][1]=1;A.mat[0][2]=1; A.mat[1][0]=1;A.mat[1][1]=0;A.mat[1][2]=0; A.mat[2][0]=0;A.mat[2][1]=0;A.mat[2][2]=1; matrix ans; ans.mat[0][0]=1;ans.mat[0][1]=0;ans.mat[0][2]=0; ans.mat[1][0]=0;ans.mat[1][1]=1;ans.mat[1][2]=0; ans.mat[2][0]=0;ans.mat[2][1]=0;ans.mat[2][2]=1; n--; while(n) { if(n&1) { ans=ans*A; } A=A*A; n>>=1; } ll wn=(ans.mat[1][0]*b+ans.mat[1][2]*b)%(MOD-1); ll res=1; while(wn) { if(wn&1) { res*=a; res%=MOD; } a=a*a; a%=MOD; wn>>=1; } printf("%lld
"
,res); } return 0; }