hdu3483之二项式展开+矩阵快速幂

A Very Simple ProblemTime Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 589    Accepted Submission(s): 305


Problem DescriptionThis is a very simple problem. Given three integers N, x, and M, your task is to calculate out the following value:


 
InputThere are several test cases. For each case, there is a line with three integers N, x, and M, where 1 ≤ N, M ≤ 2*109, and 1 ≤ x ≤ 50.
The input ends up with three negative numbers, which should not be processed as a case.
 
OutputFor each test case, print a line with an integer indicating the result. 
Sample Input

100 1 100003 4 1000-1 -1 -1

 
Sample Output

5050444

/*分析:Sn=1^x * x^1 + 2^x * x^2 +...+ n^x * x^n;Sn+1=1^x * x^1 + 2^x * x^2 +...+ n^x * x^n+(n+1)^x * x^(n+1)=Sn+(n+1)^x * x^(n+1),将(n+1)^x二项式展开然后用矩阵快速幂构造矩阵:|1 xC(x,0) xC(x,1) xC(x,2) ... xC(x,x)|  |Sn   | |S(n+1)   ||0 xC(0,0) 0       0       ... 0  |  |x^n * n^0| |x^(n+1) * (n+1)^0||0 xC(1,0) xC(1,1) 0       ... 0  | *|x^n * n^1|=|x^(n+1) * (n+1)^1||0 xC(2,0) xC(2,1) xC(2,2) ... 0  |  |x^n * n^2| |x^(n+1) * (n+1)^2||...  |  |...   | |...   ||0 xC(x,0) xC(x,1) xC(x,2) ... xC(x,x)|  |x^n * n^x| |x^(n+1) * (n+1)^x|*/#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<queue>#include<algorithm>#include<map>#include<iomanip>#define INF 99999999using namespace std;const int MAX=50+10;__int64 array[MAX][MAX],sum[MAX][MAX],mod;__int64 C(int n,int m){if(m<0 || m>n)return 0;__int64 ans=1;for(int i=1;i<=m;++i){ans=ans*(n-m+i)/i;}return ans%mod;}void MatrixInit(__int64 a[MAX][MAX],int &x,bool flag){a[0][0]=1;for(int j=1;j<=x+1;++j){if(flag)a[0][j]=x*C(x,j-1)%mod;else a[0][j]=0;} for(int i=1;i<=x+1;++i){for(int j=0;j<=x+1;++j){if(flag)a[i][j]=x*C(i-1,j-1)%mod;else a[i][j]=(i == j);}}}void MatrixMult(__int64 a[MAX][MAX],__int64 b[MAX][MAX],int &x){__int64 c[MAX][MAX]={0};for(int i=0;i<=x+1;++i){for(int j=0;j<=x+1;++j){for(int k=0;k<=x+1;++k){c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;}}}for(int i=0;i<=x+1;++i){for(int j=0;j<=x+1;++j)a[i][j]=c[i][j];}}__int64 MatrixPow(int &x,int &k){MatrixInit(sum,x,0);while(k){if(k&1)MatrixMult(sum,array,x);MatrixMult(array,array,x);k>>=1;}return sum[0][1];}int main(){int n,x;while(scanf("%d%d%I64d",&n,&x,&mod),n>0){MatrixInit(array,x,1);printf("%I64d\n",MatrixPow(x,n));}return 0;}