题解

\(dp[i]\) 表示长度为i的格子的合法涂色数，考虑第 \(i\) 个怎么放

第 \(i\) 个前面 \(k-1\) 个位置有2种颜色，则第 \(i\) 个位置只能放这两种颜色中的一种
用合法方案减只有一种的方法，即得两种颜色的方案数
而只有一种颜色的方案数，等于 \(f[i-k+1]\)，
此时，让中间的 \(k-2\) 个格子都和 \(i-k+1\) 涂一样的即可。
第i个前面k-1个位置仅有一种颜色，刚求过，\(f[i-k+1]\) ，
此时，第i个位置有c种选择可以涂，
\(dp[i]=(dp[i]-dp[i-k+1])*2+c*dp[i-k+1]\)
当 \(i-k+1<1\) 时，相当于前缀没有限制，
而目的是为了让这中间夹着的 \(<=k-2\) 个格子同色，
此时方案数有 \(c\) 种，与 \(dp[1]\) 统一
注意到 \(c=1\) 或2时， \(c-2<=0\) ，可以特判，
但代入式子后发现，可以和式子统一

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,mod=998244353;
int n,k,c,dp[N];
int main(){
    cin>>n>>k>>c;
    dp[1]=c;
    for(int i=2;i<=n;++i){
        dp[i]=(2ll*dp[i-1]%mod+1ll*(c-2)*dp[max(1,i-k+1)]%mod)%mod;
    }
    cout<<dp[n]<<endl;
	return 0;
}