BUPT2017 wintertraining(15) #4E
Gym - 101138K
题意
N节车厢的火车，每节车厢容量是1~K，那么有(K^N)种火车。
求选择D个连续的且容量相同的车厢的方案恰为T种的火车有多少种 模(10^9+7)。
(1 ≤ D ≤ n ≤ 3333, 0 ≤ T ≤ N - D + 1, 1 ≤ K ≤ (10^9)).
题解
(f[i][j])表示前i节车厢，恰有j种选择方案的火车数量，那么
初始条件：(f[0][0]=1)
状态转移：
我们考虑扩展长度i的火车来增加方案个数，在第i节后面添加相同容量的车厢，且与第i节容量不同。
0种选择方案的情况：
如果i<D，方案一定是0种，每节都有K种容量可选择。
如果i>=D，扩展到 i 节车厢，扩展的长度j为1到D-1，容量有K-1种选择，都不会增加方案。
大于0种选择方案的情况，必须i>=D，考虑扩展到 i 节车厢：
扩展的长度k为1到D-1，都不会增加方案。
扩展长度k为D到i-1，K-1种容量选择，增加了方案数k-D+1（前提条件是j>=(k-D+1)）。
扩展长度k=i，有K种容量选择，增加了方案数i-D+1。（前提条件是j>=(k-D+1)）
但是这样进行动态规划，会超时，我们观察式子可以发现，求和的部分可以用前缀和来代替，就能免去冗余计算了。并且(f[i][j])也没必要存下来了。
(s[i][j]=(f[1][j]+f[2][j]+..+f[i][j])cdot (K-1))
(g[i][j]=(f[i][j]+f[i-1][j-1]+..+f[i-min(i,j)][j-min(i,j)])cdot (K-1))且(f[0][0])乘的是K。
实际上的计算过程是
(s[i][j]=s[i-1][j]+f[i][j]cdot(K-1))
(g[i][j]=g[i-1][j-1]+f[i][j]cdot(K-1))且(g[0][0]=K)，(g[i][0]=f[i][0]cdot(K-1))
那么(f[i][j]=s[i-1][j]-s[i-D][j]+g[i-D][j-1])
注意一下有减法的取模要模一下再加M再模一下。
代码
#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;
}