矩阵快速幂 HDU3483

  1 #include <iostream>
  2 #include <cstring>
  3 
  4 using namespace std;
  5 
  6 //矩阵大小上限
  7 const int SIZ=100;
  8 int MOD;
  9 
 10 //矩阵大小为n*m，初始化全部为0
 11 struct mat
 12 {
 13     int n,m;
 14     long long  ar[SIZ][SIZ];
 15     mat()
 16     {
 17         memset(ar,0,sizeof(ar));
 18         n=m=SIZ;
 19     };
 20 };
 21 
 22 //矩阵乘法
 23 mat operator *(mat a,mat b)
 24 {
 25     mat c;
 26     c=mat();
 27     c.n=a.n;
 28     c.m=b.m;
 29     for(int i=1;i<=a.n;i++)
 30         for(int j=1;j<=b.m;j++)
 31             for(int k=1;k<=a.m;k++)
 32             {
 33                 c.ar[i][j]+=(a.ar[i][k]*b.ar[k][j])%MOD;
 34                 c.ar[i][j]%=MOD;
 35             }
 36     return c;
 37 }
 38 
 39 //矩阵加法
 40 mat operator +(mat a,mat b)
 41 {
 42     mat c;
 43     c=mat();
 44     c.n=a.n;
 45     c.m=a.m;
 46     for(int i=1;i<=a.n;i++)
 47         for(int j=1;j<a.m;j++)
 48             c.ar[i][j]=a.ar[i][j]+b.ar[i][j];
 49     return c;
 50 }
 51 
 52 //矩阵快速幂
 53 mat operator ^(mat a,int k)
 54 {
 55     mat c;
 56     c=mat();
 57     c.n=a.n;
 58     c.m=a.m;
 59     for(int i=1;i<=a.n;i++)
 60         c.ar[i][i]=1;
 61     while(k)
 62     {
 63         if(k&1)
 64             c=c*a;
 65         a=a*a;
 66         k/=2;
 67     }
 68     return c;
 69 }
 70 
 71 long long  tarr[100][100];
 72 long long  C(long long  a,long long  b)
 73 {
 74     memset(tarr,0,sizeof(tarr));
 75     for(int i=0;i<=a;i++)
 76         tarr[i][0]=1;
 77     for(int i=1;i<=a;i++)
 78         for(int t=1;t<=i;t++)
 79         {
 80             tarr[i][t]=(tarr[i-1][t-1]+tarr[i-1][t])%MOD;
 81         }
 82     return tarr[a][b];
 83 }
 84 
 85 int main()
 86 {
 87     int n,x;
 88     while(cin>>n>>x>>MOD&&(n!=-1||x!=-1||MOD!=-1))
 89     {
 90         mat tt;
 91         tt=mat();
 92         tt.m=tt.n=x+2;
 93         for(int i=1;i<tt.m;i++)
 94         {
 95             for(int t=1;t<=i;t++)
 96             {
 97                 tt.ar[i][t]=C(i-1,t-1)*x%MOD;
 98             }
 99         }
100         tt.ar[tt.m][tt.m-1]=tt.ar[tt.m][tt.m]=1;
101         mat ans;
102         ans=mat();
103         ans.n=x+2;
104         ans.m=1;
105         for(int i=1;i<x+2;i++)
106         {
107             ans.ar[i][1]=x;
108         }
109         ans.ar[x+2][1]=0;
110         cout<<((tt^(n))*ans).ar[x+2][1]%MOD<<endl;
111     }
112     return 0;
113 }
View Code