题意

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种选择，都不会增加方案。

\[ \begin{cases} f[i][0]=K^i,&i<D\\ f[i][0]=(K-1)\cdot \sum_{j=1}^{j=D-1}f[i-j][0],&i\ge D \end{cases} \]

大于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]=(K-1)\cdot \sum_{k=1}^{D-1}f[i-k][j]+(K-1)\cdot \sum_{k=D}^{k=i-1}f[i-k][j-(k-D+1)]+K\cdot f[0][j-(i-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 
    
     #define M 1000000007#define N 3344using 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-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;}