CF1081C Colorful Bricks

chlchl · 2022-08-08 20:27:51 · 题解

这个题想咋样吧，又不卡 DP，又是数论题……

原本以为题解里的都是数论做法，结果发现我并不是唯一一个发现有 DP 做法的人。

Solution

言归正传，这个题数据很水，所以考虑方案数 DP。

思路：设 f_{i,j,l} 为第 i 个格子染 j 颜色，一共有 l 个格子颜色与上一个不一样的方案数。这个枚举是 n^3 的，转移是 n 的，总时间复杂度是 O(n^4)，写个搜索都比你家快。

但是注意到，我们枚举的 m 完全多余，根本不需要在意染的是什么颜色，只需要知道是否相等就可以了。

考虑删掉 j 这一维。现在，f_{i,l} 表示前 i 个格子有 l 个与上一格颜色不相同的方案数。这是可以转移的。

• 这个格子颜色与上一格不相同，那就从前 i-1 个格子有 l-1 个不相同的状态，即 f_{i-1,l-1} 转移过来。这一格只需要跟前面一格颜色不同就行了，所以有 m-1 种颜色可填，乘上 m-1。
• 这个格子颜色与上一格相同，那就从前 i-1 个格子有 l 个不相同的状态，即 f_{i-1,l} 转移过来。此时只能填上一格的那种颜色，所以只有一种情况。

然后就做完了。也不知道为啥滚动数组炸了。

代码

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

const int N = 2000 + 10;
const int MOD = 998244353;
int n, m, k, f[N][N];

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1;i<=n;i++)   f[i][0] = m;
    for(int i=1;i<=n;i++){
        for(int l=1;l<=k;l++)   (f[i][l] += 1LL * f[i - 1][l] * (m - 1) % MOD + f[i - 1][l - 1] % MOD) %= MOD;
    }
    printf("%d\n", f[n][k]);
    return 0;
}