題目大意：
有N個骰子，每個骰子有K個面，分別標號1~K，設每個骰子向上的面的值為fi，如果sum(fi)等於S，那麼獲得一個分數sco=mult(fi)。
sum(fi)=f1+f2+...+fn
mul(fi)=f1*f2*...*fn
求所有mul(fi)的和。
時間限制為2s
N (1 ≤ N ≤ 1000) K (1 ≤ K ≤ 1000) S (0 ≤ S ≤ 15000).
題目思路：
要求所有N個骰子的sum(fi)為S的所有mul(fi)的和，設為ans[n][s]。
顯然有ans[n][s]=ans[n-1][s-1]+2*ans[n-1][s-2]+...+k*ans[n-1][s-k]
可以把上式作為狀態轉移方程：
dp[i][j] = dp[i-1][j-1] + 2*dp[i-1][j-2] + ... + k*dp[i-1][j-k]
如果用該轉移方程，不難判斷復雜度為O(n*k*s)，肯定是超時的。
其實我們仔細觀察轉移方程的右邊可以看成：
= dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-k]
+ dp[i-1][j-2] + dp[i-1][j-3] + ... + dp[i-1][j-k]
.
.
.
+ dp[i-1][j-k]
我們設sum[i][j] = dp[i][j-1] + dp[i][j-2] + ... + dp[i][1]
那麼轉移方程的右邊又可以看成：
= sum[i-1][j-1] - sum[i-1][j-k-1]
+ sum[i-1][j-2] - sum[i-1][j-k-1]
.
.
.
+ sum[i-1][j-k] - sum[i-1][j-k-1]
我們再設ssum[i][j] = sum[i][j] + sum[i][j-1] + ... + sum[i][1]
這樣轉移方程的右邊又可以看成
= ssum[i][j-1] - ssum[i][j-k-1] - k*sum[i][j-k-1]
這樣我們就把O(k)求dp[i][j]，轉為了O(1)，而算法的整體復雜度也降為了O(n*s)，這樣就不會超時咯。
但是空間復雜度也是O (n*s)的，但是我們發現，求i只需要知道i-1，所以我們可以用滾動數組來處理，這樣空間復雜度就降到了O(2*s)。
需要注意的是j-k-1<1的時候，轉移方程略有區別，不過也只是小細節的問題，很容易處理。
代碼：
[cpp]
#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<string>
using namespace std;
#define ll __int64
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n))
#define clr_all(x,c) memset(x,c,sizeof(x))
#define IT iterator
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle l+r>>1
#define MOD 100000007
#define inf 0x3f3f3f3f
#define eps (1e-8)
#define PI 3.1415926535897932384626433832795
#define E 2.7182818284590452353602874713527
template <class T> T _min(T a,T b){return a<b? a:b;}
template <class T> T _max(T a,T b){return a>b? a:b;}
template <class T> T _abs(T a){return a>0? a:-a;}
template <class T> T _mod(T a,T m){return a<m? (a<0? (a%m+m)%m:a):a%m;}
template <class T> T _gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}
template <class T> void _swap(T &a,T &b){T t=b;b=a;a=t;}
template <class T> void getmax(T &a,T b){a= a>b? a:b;}
template <class T> void getmin(T &a,T b){a= (a!=-1 && a<b)? a:b;}
int TS,cas=1;
const int M=15000+5;
ll n,k,s,m;
ll dp[2][2][M],now,pre,tmp;
void run(){
ll i,j;
scanf("%lld%lld%lld",&n,&k,&s);
now=0;
dp[now][0][0]=dp[now][1][0]=0;
for(i=1;i<=s;i++){
dp[now][0][i]=dp[now][0][i-1]+(i<=k? i:0);
dp[now][1][i]=(dp[now][1][i-1]+dp[now][0][i])%MOD;
}
for(i=2;i<=n;i++){
pre=now;
now^=1;
dp[now][0][i-1]=dp[now][1][i-1]=0;
for(j=i;j<=s;j++){
if(j<i+k) tmp=dp[pre][1][j-1];
else tmp=((dp[pre][1][j-1]-dp[pre][1][j-k-1]-dp[pre][0][j-k-1]*k)%MOD+MOD)%MOD;
dp[now][0][j]=(dp[now][0][j-1]+tmp)%MOD;
dp[now][1][j]=(dp[now][1][j-1]+dp[now][0][j])%MOD;
}
}
printf("Case %d: %lld\n",cas,((dp[now][0][s]-dp[now][0][s-1])%MOD+MOD)%MOD);
}
void presof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
presof();
//run();
//while(~scanf("%d",&n)) run();
for(scanf("%d",&TS),cas=1;cas<=TS;cas++) run();
return 0;
}
