「Test」涂色

题意：一个一排 $N$ 个格子的纸，你要用一个宽度为 $K$ 个格子的图章和 $M$ 种不同的颜色在上面涂色。每次把纸上连续 $K$ 个格子染上同种颜色(会覆盖掉之前的颜色)，那么最后纸上的颜色序列有多少种不同情况？

一道容斥 DP 题。

易知最后的纸上的颜色序列肯定会有至少连续 $K$ 个格子为相同颜色，要计算不同的方案数，我们采用正难则反的思想，先算出总方案数，再减去不管怎样都小于 $K$ 个格子为相同颜色的方案数即可。

总方案数可以很快算出为 $M ^{N}$，所以关键就在如何算出不管怎样都小于 $K$ 个格子为相同颜色的方案数。

我们设 $f _{i}$ 代表 $i$ 个格子的纸小于 $K$ 个格子为相同颜色的方案数，我们分为 $2$ 个阶段，首先对于 $i<K$ 的情况，那么无论怎样都不能达到 $K$ 个格子为相同颜色，故此时 $f _{i}=M ^{i}$，对于 $i\ge K$ 的情况，那么 $f _{i}=(m-1)\times \sum _{j=i-(K-1)} ^{i-1} f[j]$，从前 $i-(K-1)$ 到 $i-1$ 个正好少了 $1\sim K-1$ 个格子，剩下的格子都不能和其小于 $K$ 个格子为相同颜色的那个颜色相同，所以要乘以 $m-1$。

因此得到 $f$ 的方程：

$$f _{i}=\begin{cases} M ^{i},i<K \\\\ (m-1)\times \sum _{j=i-(K-1)} ^{i-1} f[j],i\ge K \end{cases}$$

最后记得快速幂取模即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=1000010;
const long long mod=1000000007;
long long n,m,k,ans,f[maxn],sum;
long long power(long long a,long long b,long long p)
{
	long long ans=1%p;
	for(;b;b>>=1)
	{
		if(b&1)
			ans=(ans*a)%p;
		a=(a*a)%p;
	}
	return ans%p;
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	ans=power(m,n,mod);
	f[0]=1;
  	sum=0;
	for(int i=1;i<k;i++)
	{
		f[i]=f[i-1]*m%mod;
		sum=(sum+f[i])%mod;
	}
	for(int i=k;i<=n;i++)
	{
		f[i]=sum*(m-1)%mod;
		sum=(sum+f[i]+mod-f[i-k+1])%mod;
	}
	ans=(ans+mod-f[n])%mod;
	printf("%lld",ans%mod);
	return 0;
}