http://acm.timus.ru/problem.aspx?space=1&num=1036
简单的DP，要注意细节的处理，s为奇数，s最大值为1000（n=50 s=1000,answer=0）
1 #include <iostream>
2 using namespace std;
3 int n,s;
4 int f[600][51];
5
6 void jia(int a[51],int b[51]){
7 for (int i=1;i<=50;++i) a[i]+=b[i];
8 for (int i=1;i<50;++i){
9 a[i+1]+=a[i]/10000;
10 a[i]%=10000;
11 }
12 }
13
14 void cheng(int a[51],int b[51]){
15 int c[111];
16 for (int i=1;i<=110;++i) c[i]=0;
17 for (int i=1;i<=50;++i)
18 for (int j=1;j<=50;++j) c[i+j-1]+=a[i]*b[j];
19 for (int i=1;i<=50;++i){
20 c[i+1]+=c[i]/10000;
21 c[i]%=10000;
22 }
23 for (int i=1;i<=50;++i) a[i]=c[i];
24 }
25
26 int main(){
27 scanf("%d %d",&n,&s);
28 if (s%2==1) cout<<0;
29 else{
30 s/=2;
31 for (int i=0;i<10;++i) f[i][1]=1;
32 for (int i=1;i<n;++i)
33 for (int j=450;j>0;--j)
34 for (int k=1;k<=9&&j>=k;++k) jia(f[j],f[j-k]);
35 cheng(f[s],f[s]);
36 int p=50;
37 while (f[s][p]==0&&p>0) --p;
38 if (p==0) cout<<0;
39 else{
40 printf("%d",f[s][p]);
41 for (int i=p-1;i>0;--i) printf("%04d",f[s][i]);
42 }
43 }
44 }
45
46
posted on 2008-11-04 17:52
Joseph 阅读(426)
评论(0) 编辑 收藏 引用