[abc279 G] At Most 2 Colors
2023/5/27 1:23:18
本文主要是介绍[abc279 G] At Most 2 Colors,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
G - At Most 2 Colors (atcoder.jp)
重点讲解方法三,因为
方法三是蒟蒻都能想出来的方法一和方法二都可以借助方法三的思想推出
方法一
这是最简单的设置状态的方法,\(dp[i]\)表示前\(i\)个的方案数,然后分类
-
若\([i-k+1,i-1]\)有两种颜色
那么第\(i\)位的取值肯定时这两种颜色中的一个,所以就是要\(\times2\),考虑如何使得\([i-k+1,i-1]\)必须有两个颜色,用总方案减去只有一种颜色的方案,也就是\(dp[i-1]-dp[i-k+1]\)
\(dp[i]+=(dp[i-1]-dp[i-k+1])\times2\)
- 若\([i-k+1,i-1]\)只有一种颜色
此时第\(i\)位有\(c\)种取值,则\(dp[i]+=dp[i-k+1]\times c\)
所以综上:\(dp[i]=dp[i-1]\times2+(c-2)\times dp[i-k+1]\)
方法二
设\(dp[i][1/2]\)表示\([i-k+2,i]\)中有\(1/2\)种颜色的方案数
分类讨论,然后枚举\(j\)表示\([j+1,i]\)的颜色都相同
方法三
\(dp\)状态同二
-
对于\(dp[i][1]\)
-
当\(i-k+1\)的颜色与\([i-k+2,i]\)的颜色相同时,显然有\(dp[i-1][1]\)
-
颜色不同时,将考虑的范围向前扩展到\([i-2k+3,i-k+1]\),这时可以保证对于以\([i-k+1,i-1]\)结尾的长度为\(k-1\)的区间都被囊括其中,以下所有方法的合法性都可以用这个来解释
-
当\([i-2k+3,i-k+1]\)的颜色都相同时,\([i-k+2,i]\)的颜色可以取除了\([i-2k+3,i-k+1]\)以外的任何颜色,这时就是\(dp[i-k+1][1]\times(c-1)\)
-
当\([i-2k+3,i-k+1]\)颜色不同时,若两种颜色分别为\(a\)和\(b\),且\(i-k+1\)的颜色为\(a\),\([i-k+2,i]\)的为\(b\),这时就是\(dp[i-k+1][2]\)
-
-
-
对于\(dp[i][2]\)
-
当\([i-k+1,i-1]\)的颜色相同时,显然有\(i\)的颜色取值有除了\([i-k+1,i-1]\)的颜色外的所有颜色,也就是\(dp[i-1][1]\times(c-1)\)
-
当\([i-k+1,i-1]\)的颜色不同时,\(i\)的取值就有两种,这时有\(dp[i-1][2]\times2\),但这并不合法,因为\(dp[i-1][2]\)中包含了\([i-k+2,i-1]\)的颜色都为\(a\),而\(i-k+1\)的颜色为\(b\)的方案数,所以考虑减去这种不合法的方案
发现这种不合法的情况就是\(dp[i][1]\)的第二个大类,所以直接使用
-
综上:
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+5,MOD=998244353; int n,k,c; ll dp[N][2],invf=499122177; int main(){ scanf("%d%d%d",&n,&k,&c); dp[1][1]=c%MOD; for(int i=2;i<=n;++i){ dp[i][1]=((dp[i-1][1]+dp[max(0,i-k+1)][1]*(c-1)%MOD)%MOD+dp[max(0,i-k+1)][2])%MOD; dp[i][2]=((dp[i-1][1]*(c-1)%MOD+dp[i-1][2]*2%MOD)%MOD-(dp[max(0,i-k+1)][1]*(c-1)%MOD+dp[max(0,i-k+1)][2])%MOD+MOD)%MOD; } printf("%lld\n",(dp[n][1]+dp[n][2])%MOD); return 0; }
这篇关于[abc279 G] At Most 2 Colors的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享