题目链接：
题意：将S分成n个数的和，分成的每个数x的范围[1,m]，每种分法n个数的乘积算作该分法的score值。求所有分法的score值之和。
思路：f[S][n]=sigama(f[S-i][n-1]*i)(1<=i<=m)。。。
View Code 1 #include2 #include 3 #include 4 #define i64 long long 5 using namespace std; 6 7 const i64 MOD=100000007; 8 int C,num=0; 9 int n,K,S;10 i64 f[15005][2],sum[15005][2];11 12 13 i64 DP()14 {15 int i,j,pre=0,cur=1;16 i64 temp[15005];17 memset(f,0,sizeof(f));18 memset(sum,0,sizeof(sum));19 for(i=1;i<=K;i++) f[i][pre]=i,sum[i][pre]=(sum[i-1][pre]+f[i][pre])%MOD;20 while(i<=S) sum[i][pre]=(sum[i-1][pre]+f[i][pre])%MOD,i++;21 22 for(j=2;j<=n;j++)23 {24 temp[1]=0;25 for(i=1;i<=S;i++)26 {27 if(i<=K) f[i][cur]=temp[i];28 else f[i][cur]=((temp[i]-temp[i-K]-sum[i-K-1][pre]*K)%MOD+MOD)%MOD;29 sum[i][cur]=(sum[i-1][cur]+f[i][cur])%MOD;30 temp[i+1]=(temp[i]+sum[i][pre])%MOD;31 }32 pre^=1;33 cur^=1;34 }35 return f[S][pre];36 }37 38 int main()39 {40 for(scanf("%d",&C);C--;)41 {42 scanf("%d%d%d",&n,&K,&S);43 printf("Case %d: %lld\n",++num,DP());44 }45 return 0;46 }