BUPT2017 wintertraining(15) #4E Gym - 101138K
题意
题解
代码
代码语言：javascript复制#include <cstdio>
#define M 1000000007
#define N 3344
using namespace std;
int n,d,t,l;
long long f=1,g[N][N],s[N][N];
int main() {
scanf("%d%d%d%d",&n,&d,&t,&l);
g[0][0]=l;
for(int i=1;i<=n;i ){
if(i<d)
f=f*l%M;
else
f=((s[i-1][0]-s[i-d][0])%M M)%M;
g[i][0]=f*(l-1)%M;
s[i][0]=(s[i-1][0] f*(l-1))%M;
}
for(int i=1;i<=n;i )
for(int j=1;j<=t;j ){
f=s[i-1][j];
if(i>=d)f=((f-s[i-d][j] g[i-d][j-1])%M M)%M;
s[i][j]=(s[i-1][j] f*(l-1))%M;
g[i][j]=(g[i-1][j-1] f*(l-1))%M;
}
printf("%lld",f);
return 0;
}
