| Time Limit: 3 second(s) | Memory Limit: 32 MB |
You have N dices; each of them has K faces numbered from 1 to K. Now you can arrange the N dices in a line. If the summation of the top faces of the dices is S, you calculate the score as the multiplication of all the top faces.
Now you are given N, K, S; you have to calculate the summation of all the scores.
Input starts with an integer T (≤ 25), denoting the number of test cases.
Each case contains three integers: N (1 ≤ N ≤ 1000) K (1 ≤ K ≤ 1000) S (0 ≤ S ≤ 15000).
For each case print the case number and the result modulo 100000007.
Sample Input |
Output for Sample Input |
|
5 1 6 3 2 9 8 500 6 1000 800 800 10000 2 100 10 |
Case 1: 3 Case 2: 84 Case 3: 74335590 Case 4: 33274428 Case 5: 165 |
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<math.h> 6 #include<stdlib.h> 7 #include<queue> 8 using namespace std; 9 typedef long long LL; 10 LL dp[2][15005]; 11 const int mod=100000007; 12 LL sum[15005]; 13 int main(void) 14 { 15 int i,j,k; 16 scanf("%d",&k); 17 int s; 18 int n,m,c; 19 for(s=1; s<=k; s++) 20 { 21 scanf("%d %d %d",&n,&m,&c); 22 memset(dp,0,sizeof(dp)); 23 memset(sum,0,sizeof(sum)); 24 for(i=1; i<=m; i++) 25 { 26 dp[1][i]=i; 27 dp[1][i]%=mod; 28 sum[i]=(sum[i-1]+dp[1][i])%mod; 29 } 30 for(i=m+1;i<=c;i++) 31 sum[i]=sum[i-1]; 32 for(i=2; i<=n; i++) 33 { 34 int uu=(i)%2; 35 int kk=(i+1)%2; 36 for(j=0; j<i; j++) 37 { 38 dp[uu][j]=0; 39 } 40 for(j=i;j<=c; j++) 41 { 42 dp[uu][j]=((dp[kk][j-1]+dp[uu][j-1])%mod+(sum[j-2]-sum[max(0,j-1-m)])%mod-dp[kk][max(0,j-m-1)]*m%mod)%mod; 43 dp[uu][j]%=mod; 44 dp[uu][j]+=mod; 45 dp[uu][j]%=mod; 46 } 47 for(j=1; j<=c; j++) 48 { 49 sum[j]=sum[j-1]+dp[uu][j]; 50 sum[j]%=mod; 51 } 52 } 53 printf("Case %d: ",s); 54 printf("%lld\n",(dp[n%2][c]%mod+mod)%mod); 55 } 56 return 0; 57 }
原文：http://www.cnblogs.com/zzuli2sjy/p/5636173.html