题目链接：
题目大意：
根据二项式定理，我们可以得到：
(n+1)k=C0knk+C1knk−1+C2knk−2+...+Ck−1kn+1
于是可以构造变化矩阵：
⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜C0k00...01C1kC0k−10...00C2kC1k−1C0k−2...00C3kC2k−1C1k−2...00..................111...11⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟∗⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜nknk−1...n1sum⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟=⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜(n+1)k(n+1)k−1...n+11sum⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟ sum 是 每一项N^K的累加和。对于操作矩阵可以杨辉三角可以快速得到
即C（m，k）=C（m-1，k-1）+C（m，k-1）；
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> using namespace std; #define ll long long #define N 60 const ll mod =(1ll<<32); ll n,k; struct Matrix { ll r,c; ll m[N][N]; Matrix(){} Matrix(ll r,ll c):r(r),c(c){} Matrix operator *(const Matrix& B)//乘法 { Matrix T(r,B.c); for(int i=1;i<=T.r;i++) { for(int j=1;j<=T.c;j++) { ll tt = 0; for(int k=1;k<=c;k++) tt +=( m[i][k]*B.m[k][j]) % mod; T.m[i][j] = tt % mod; } } return T; } Matrix Unit(ll h) // 对角线矩阵 { Matrix T(h,h); memset(T.m,0,sizeof(T.m)); for(int i=1;i<=h;i++) T.m[i][i] = 1; return T; } Matrix Pow(ll n) //矩阵幂 { Matrix P = *this,Res = Unit(r); while(n!=0) { if(n&1) Res =Res*P; P = P*P; n >>= 1; } return Res; } void Print()//输出 { for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) printf("%d ",m[i][j]); printf("\n"); } } }Single; ll power(ll a,ll n) //矩阵幂 { ll res=1; while(n) { if(n&1) res = res*a%mod; a= a*a%mod; n >>= 1; } return res; } int main(){ int t; scanf("%d",&t); int kase=1; while(t--) { scanf("%lld%lld",&n,&k); if(k == 0){ printf( "Case %d: %lld\n" , kase++ , n % mod ); continue; } if(n==1) { printf( "Case %d: 1\n" , kase++ ); continue; } Matrix res(1,k+2),ans(k+2,k+2); for(int i=1;i<=k+1;i++) res.m[1][i]=power(2,k-i+1); res.m[1][k+2]=1; memset(ans.m,0,sizeof ans.m); ans.m[k+2][k+2]=ans.m[1][k+2]=1; for(int i=k+1;i>=1;i--) for(int j=i;j>=1;j--) { ans.m[i][j]=ans.m[i][j+1]+ans.m[i+1][j+1]; } if(n>1) ans=ans.Pow(n-1); res=res*ans; printf( "Case %d: %lld\n" , kase++ , res.m[1][k+2] % mod ); } return 0; } /* 3 3 1 4 2 3 3 */
