AT_abc279_g题解

· · 题解

有点妙的 dp，感觉和大家的有点不同。

首先我们有个朴素的 dp，设 f_{i,j} 表示前 i 个格子中，从第 j 个格子到第 i 个格子都是同样颜色，且第 j-1 个格子和第 j 个格子颜色不同，满足 1 到 i 都合法的方案数，则

f_{i,j}=f_{i-1,j} \left[j<i\right]

（第 i 个格子要和第 i-1 个格子颜色相等）

f_{i,i}=\left( \sum_{j=i-k+2}^{i-1} f_{i-1,j} \right) + \left( \sum_{j=1}^{i-k+1}f_{i-1,j} \times\left(c-1\right) \right)

（如果第 j-1 个格子到第 i 个格子的格子数小于等于 k，则强制第 i 个格子与第 j-1 个格子同色，否则只需强制第 i 个格子与第 i-1 个格子不同色即可）

直接做是 O(n^2) 的。

发现第一部分可以直接继承，于是可以把第一维省掉。

直接用前缀和算第二部分，代码中的 g_i 为前缀和数组。

注意 f_1 转移到 f_i 时可能要特判，因为此时只出现过一种颜色。

这题就做完了。

代码真的很短。

int main(){
    scanf("%lld %lld %lld",&n,&K,&c);
    f[1]=g[1]=c;
    for(R i=2; i<=n; ++i){
        LL x=max(i-K+1,(LL)1);
        f[i]=g[i-1]-g[x]+g[x]*(c-1)%mo;//唯一的转移
        f[i]=(f[i]+mo)%mo;
        g[i]=(g[i-1]+f[i])%mo;
    }
    printf("%lld\n",g[n]);
}

如有错请指出，谢谢。