算法分析
记 dp[i]
表示给前 $i$ 个格子染色使得方格 $1 \sim i$ 中至少有两种颜色的合法染色方案数
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
int main() {
int n, k, c;
cin >> n >> k >> c;
vector<mint> dp(n);
for (int i = 1; i < n; ++i) {
// 一段:指连续的 k-1 个格子
// dp[i-1]*2: 当前格子染前一段中恰染两种颜色的染色方案中的两种颜色
// c*(c-1): 当前格子染和前一段中恰染一种颜色的染色方案中不同的颜色,有 c-1 种染法
dp[i] += dp[i-1]*2 + mint(c)*(c-1);
// i+1~i+k-1:染相同的颜色,而且颜色和前一段中恰染两种颜色的染色方案中的颜色都不同,有 c-2 种染法
if (i+k-1 < n) dp[i+k-1] += dp[i]*(c-2);
}
// 0...n-1 颜色都相同满足任意 k 个格子颜色相同
mint ans = c+dp[n-1];
cout << ans.val() << '\n';
return 0;
}