Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 570 Accepted Submission(s): 183
递推实现 f[i][j]表示前i个数能够表示j状态的方案数，其中j为最多20位的二进制，表示前i个数的和（1-20）是否达到
#include "cstdio" #include "cstring" #define min(x,y) (x>y?y:x) #define MOD 1000000007 int f[1050000]; int n,k,l; int main() { int tt; scanf("%d",&tt); while(tt--) { memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&k,&l); int ms=(1<<k)-1; long long ans=0; for(int j=0; j<=min(l,k); j++) f[1<<(j-1)]=1; if(l>k) f[0]=(f[0]+l-k)%MOD; for(int i=1; i<n; i++) for(int s=ms; s>=0; s--) if(f[s]>0)// { long long tmp=f[s]; for(int j=1; j<=min(l,k); j++) { int ns=(s|(s<<j)|(1<<(j-1)))&ms; f[ns]=(f[ns]+tmp)%MOD; } if(l>k) f[s]=(f[s]+(l-k)*tmp%MOD)%MOD; } for(int s=0; s<=ms; s++) if(s&(1<<(k-1))) ans=(ans+f[s])%MOD; printf("%lld\n",ans); } return 0; }
超时代码：
#include "cstdio" #include "cstring" #define min(x,y) (x>y?y:x) #define MOD 1000000007 int f[21][1050000],c[21][21]; int n,k,l; inline long long pow(long long a, long long b) { long long ret=1,tmp=a%MOD; while(b) { if(b&1) ret=(ret*tmp)%MOD; tmp=(tmp*tmp)%MOD; b>>=1; } return ret; } int main() { for(int i=0; i<=20; i++) for(int j=0; j<=i; j++) if(j>0) c[i][j]=c[i-1][j]+c[i-1][j-1]; else c[i][j]=1; int tt; scanf("%d",&tt); while(tt--) { memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&k,&l); int ms=(1<<k)-1; for(int j=0; j<=min(l,k); j++) f[1][1<<(j-1)]=1; for(int i=1; i<n; i++) for(int j=0; j<=min(l,k); j++) for(int s=0; s<=ms; s++) { f[i+1][(s|(s<<j)|(1<<(j-1)))&ms]+=f[i][s]; f[i+1][(s|(s<<j)|(1<<(j-1)))&ms]%=MOD; } long long ans=0; if(l<=k) { for(int s=0; s<=ms; s++) if(s&(1<<(k-1))) ans=(ans+f[n][s])%MOD; } else { for(int i=1; i<=n; i++) for(int s=0; s<=ms; s++) if(s&(1<<(k-1))) ans=(ans+((long long)f[i][s]*(long long)c[n][i])%MOD*pow(l-k,n-i))%MOD; } printf("%lld\n",ans); } return 0; }
原文：http://www.cnblogs.com/Mathics/p/3887207.html
