题意:
假设有x1个字母A, x2个字母B,..... x26个字母Z,同时假设字母A的价值为1,字母B的价值为2,..... 字母Z的价值为26。那么,对于给定的字母,可以找到多少价值<=50的单词呢?单词的价值就是组成一个单词的所有字母的价值之和,比如,单词ACM的价值是1+3+14=18,单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关,比如ACM与CMA认为是同一个单词)。
题解:用母函数求解;
错误分析:
是num[1],不是num[0];
#include<cstdio> #include<cstring> using namespace std; typedef long long ll; int a1[51],a2[51]; int num[51]; int main() { int i,j,k,t; scanf("%d",&t); while(t--) { ll sum=0; for(i=1;i<=26;i++) scanf("%d",&num[i]); memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2)); for(i=0;i<51&&i<=num[1];i++)//是num[1],不是num[0]; a1[i]=1;//不管第一个物体的个数是否为零,都不影响下面,因为表达式就变成1*(1+x^A1+x^2*A1+……) for(i=2;i<=26;i++) { for(j=0;j<51;j++)//j控制整个表达式的长度;可以到指定的位置,如本题到50就结束了; for(k=0;k+j<51&&k<=num[i]*i;k+=i) a2[j+k]+=a1[j]; for(j=0;j<51;j++) { a1[j]=a2[j]; a2[j]=0; } } for(i=1;i<51;i++) sum+=a1[i];//前50个系数的和即为和不大与50的情况;不包括a[0]; printf("%lld\n",sum); } return 0; }