题解
\(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;
}
标签:颜色,int,题解,Most,Colors,abc279,dp
From: https://www.cnblogs.com/BLDramer/p/17740499.html