DP. 状态方程挺简单的, 本题主要考的就是滚动数组和高精度.
注意输出为0的情况.
#include<iostream> using namespace std; const int MAXL=70; const int MAXS=1000; const int BIG=100000000; __int64 T[MAXS+1][MAXL*2]; int n,s; void add(int x,int y) { int i; for(i=0;i<MAXL;i++) T[x][i]+=T[y][i]; for(i=0;i<MAXL;i++) if(T[x][i]>BIG) { T[x][i+1]+=T[x][i]/BIG; T[x][i]%=BIG; } return; } void mul() { int i,j,k; for(i=0;i<MAXL;i++) for(j=0;j<MAXL;j++) T[MAXS][i+j]+=T[s][i]*T[s][j]; for(i=0;i<MAXL;i++) if(T[MAXS][i]>BIG) { T[MAXS][i+1]+=T[MAXS][i]/BIG; T[MAXS][i]%=BIG; } return; } int main() { int i,j,k; scanf("%d%d",&n,&s); if(s&1) { printf("0/n"); return 0; } memset(T,0,sizeof(T)); s>>=1; T[0][0]=1; for(i=0;i<n;i++) for(k=s;k>0;k--) { for(j=1;j<10;j++) if(k-j>=0) add(k,k-j); else break; } mul(); for(i=MAXL;i>=0;i--) if(T[MAXS][i]) { printf("%d",T[MAXS][i]); break; } if(i<0) printf("0"); else for(i--;i>=0;i--) printf("%08d",T[MAXS][i]); printf("/n"); return 0; }
