题意

给你n,m,k
你现在要构造一个长度为n的序列
里面每个数的范围是$[1,m]$
问你有多少种方案使得至少有一段>=k的序列数字是一样的

题解

由于n是$10^6$
所以我们可以考虑一个和n有关的东西
考虑用全部减去不合法的
就是要减去没有的
那就可以DP了
我们考虑我们把序列分成若干个子序列，所有长度不能达到k
然后相邻的子序列颜色不一样，可以得到递推式
$f[i]=(f[i-1]+f[i-2]+f[i-3]+...+f[i-k])*(m-1)$
如果从0转移过来就特判一下

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const LL N=1e6+5;
LL n,m,k;
LL pow (LL x,LL y)
{if (y==1) return x;LL lalal=pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL f[N];
int main()
{scanf("%lld%lld%lld",&n,&m,&k);LL ans=pow(m,n);LL sum=0;for (LL u=1;u<=n;u++){f[u]=sum*(m-1);if (u<k) //可以填一段f[u]=f[u]+m;else sum=sum-f[u-k+1];sum=sum+f[u];sum=(sum%MOD+MOD)%MOD;f[u]=f[u]%MOD;//printf("%lld ",f[u]);}//printf("\n");printf("%lld\n",((ans-f[n])%MOD+MOD)%MOD);return 0;
}