|
|
题目链接：
题意：
有 \text{n} 个格子， \text{c} 个颜色，要保证每连续 \text{k} 个格子中至多存在两种颜色，问有多少种涂色方案数。
感谢CKY对本题的大力支持(●'◡'●)
感谢 @cup-pyy 对本题的大力纠正(●'◡'●)
分析：
先考虑一个二维的转移问题：
idea①
dp_{i,j} 表示当前情况（当前有i个格子，最后j个同色）的方案数，那么易得：
①当前颜色直接取上一个尾巴取的颜色： dp[j] = dp[i - 1][j - 1]\ (2 \leq j \leq k-1)
②当前颜色取和上上个同色区间相同的颜色贡献为 dp[i - 1][k - 1] ，当前区间取和上一个同色区间相同的颜色，所以就是 dp[i-1][k] ，所以就是 dp[k] = dp[i - 1][k - 1] + dp[i - 1][k]
③当前颜色取上上个同色区间的颜色，该贡献是 \sum\limits_{j = 1}^{k - 2} dp[i - 1][j] ；当前颜色取和上一个尾巴区间不同的颜色，该贡献是 dp[i - 1][k - 1] \cdot (c - 1) 。
\begin{cases} dp[j] = dp[i - 1][j - 1]\ (2 \leq j \leq k-1)\\ dp[k] = dp[i - 1][k - 1] + dp[i - 1][k] \\ dp[1] = dp[i - 1][k - 1] \cdot (c - 1) + \sum\limits_{j = 1}^{k - 2} dp[i - 1][j] \\ dp[1] = c(1\le i \le k) \end{cases}
由 dp[j] = dp[i - 1][j - 1]\ (2 \leq j \leq k-1) 容易推得 dp[i-1][j]=dp[i-j][1] ，所以 dp[1] = dp[i - k + 1][1] \cdot (c - 1) + \sum\limits_{j = 1}^{k - 2} dp[i - j][1]
最后：
\begin{cases} dp[k] = dp[i - k + 1][1] + dp[i - 1][k] \\ dp[1] = dp[i - k + 1][1] \cdot (c - 1) + \sum\limits_{j = 1}^{k - 2} dp[i - j][1] \\ dp[1] = c(1\le i \le k)\\ \end{cases}
我们发现只需要计算 dp_{i,1} 和 dp_{i,k} 即可。
idea②:
容易知道：如果只有一种颜色可供选择，答案就是1。
如果是两种颜色，那么每个格子都有两种可能，答案就是 2^n 。
修正后的解释：
如果是多种颜色，第一个格子有C种方案，而后面的第 i 个格子可以选择和上一个颜色相同也可以选择和上上个同色区间颜色相同，所以该部分贡献就是 2 \times dp_{i-1} ，第二种就是当前选择的颜色和前面两个区间的颜色都不相同，那么我自己从 dp_{i-k+1} 开始转移， [i-k+1,i-1] 为相同颜色，第 i 个位置在 c-2 个颜色里面选择即可。
如果是前面区间全是同色的方案的话，转移直接就是一个 \times c ，同时 dp_{same}[i-1] 和 dp_{same}[i-k+1] 的区间全同色方案数是必定是相同的，所以也是类似的dp_i=c\times dp_{same}[i-1]=2 \times dp_{same}[i-1]+(c-2) \times dp_{same}[i-k+1] 。（该 dp_{same} 是同色方案数，dp表示通过相同方案数带来的贡献)
另一种来自pyy同学的解释：
转移有两种情况，
第一种情况是前\text{k-1}位有两种颜色，这时有 \text{2} 种填法，而前 \text{k-1} 位有两种颜色的方案数就是前\text{k-1}位所有填法的方案数减去只有一种颜色的方案数，所以这部分转移的答案是 (f[i - 1] - f[max(1, i - k + 1)]) \times 2 。
注意：如果 \text{k=2} 的话，该式子直接抵消了
第二种情况是前 \text{k-1} 位只有一种颜色，填法有 \text{c} 种，所以这部分答案是 f[max(1, i - k + 1)] \times c ，两项合并正好是 f[i - 1] \times 2 + (f[max(1, i - k + 1)]) \times (c - 2)
综上所述：
答案为 dp_i=2 \times dp_{i-1}+(c-2) \times dp_{i-k+1} 。
代码：
ll dp[maxn]={0};
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1){
ans*=a;
}
a*=a;
a%=mod;
ans%=mod;
b>>=1;
}
return ans;
}
int main(){
int n=read();int k=read(); int c=read();
if(c==1){
puts("1");
return 0;
}else if(c==2){
cout<<qpow(2,n);
return 0;
}
dp[1]=c;
for(int i=2;i<=n;i++){
dp=2*dp[i-1]%mod+(c-2)*dp[max(1,i-k+1)]%mod;
dp%=mod;
}
printf(&#34;%lld\n&#34;,dp[n]);
} |
|
发表于 2023-1-1 17:14:46