题解 P4187 【[USACO18JAN]Stamp Painting】

· · 题解

这题是一道很经典的DP，还用了一点点逆向思维。

题目大意:有n个格子，用m种颜色覆盖，每次只能覆盖k个格子，原来有颜色也可以覆盖，问一共有多少种最终状态？

题意看上去貌似有点像数学题，但仔细思索就会发现题目只是要求至少有一个长度为k的相同颜色的块。刚开始以为可以用数学方法，将一个长度为k的块单独拿出来，当成一格，然后算排列组合。交上去只过了2个点。仔细想发现有很多重复，于是就放弃了。

后来经过老师的点拨，发现可以用逆向思维来做，先用排列组合算出没有k这个限制条件的所有可能方案，即n的m次方。再算出不符合方案的情况，也就是没有一个长度至少为k的相同颜色的块减去即可。想要算出不符合的方案总数也很简单，一个简单的一维DP就行了，因为我们规定不能有长度超过k的块，所以最多只有连续k-1个格子颜色相同。所以DP方程为:

f[0]=1

当i<k时，f[i]=f[i-1]*m;

当i>k时，f[i]=(f[i-k+1]+...+f[i-1])*(m-1); （第i-k位必须与第i-k+1位到第i位不同，所以乘m-1）

最后答案即为总方案数减去不符合方案数。

程序：

#include<bits/stdc++.h>
using namespace std;

long long f[1000001];

int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    long long sum1=1,sum=0;
    for(int i=1;i<=n;i++) sum1=(sum1*m)%1000000007;
    f[0]=1;
    for(int i=1;i<k;i++) 
    {
        f[i]=(f[i-1]*m)%1000000007;
        sum=(sum+f[i])%1000000007;
    }
    for(int i=k;i<=n;i++)
    {
        f[i]=(sum*(m-1))%1000000007;
        sum=(sum+f[i]+1000000007-f[i-k+1])%1000000007;
    }
    printf("%lld",(sum1+1000000007-f[n])%1000000007);
    return 0;
}