[abc279 G] At Most 2 Colors

这篇具有很好参考价值的文章主要介绍了[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]\)的颜色都相同

\[\begin{aligned} &dp[i][1]=\sum_{j=1}^{i-k+1}(dp[j][1]\times(c-1)+dp[j][2])\\ &dp[i][2]=\sum_{j=i-k+2}^{i-1}(dp[j][1]\times(c-1)+dp[j][2]) \end{aligned} \]

方法三

\(dp\)状态同二

\[\begin{aligned} &dp[i][1]=dp[i-1][1]+dp[i-k+1][1]\times(c-1)+dp[i-k+1][2]\\ &dp[i][2]=dp[i-1][1]\times(c-1)+dp[i-1][2]\times2-dp[i-k+1][1]\times(c-1) -dp[i-k+1][2] \end{aligned} \]
  • 对于\(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]\)的第二个大类,所以直接使用

综上:文章来源地址https://www.toymoban.com/news/detail-460080.html

\[\begin{aligned} &dp[i][1]=dp[i-1][1]+dp[i-k+1][1]\times(c-1)+dp[i-k+1][2]\\ &dp[i][2]=dp[i-1][1]\times(c-1)+dp[i-1][2]\times2-dp[i-k+1][1]\times(c-1) -dp[i-k+1][2] \end{aligned} \]
#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的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包赞助服务器费用

相关文章

  • AT_abc345_d 题解

    本文同步发表于洛谷。 是个逆天搜索。 最开始:爆搜,启动! 然后 TLE 到飞起。 赛后:我【数据删除】这么简单的吗?! dfs 每个位置,试着把没放过的块放到以这个位置为左上角的区域里面。 好了没了,就是这么简单! 对了记得这个块可以旋转!

    2024年03月21日
    浏览(9)
  • AT_abc344_e 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 赛时各种【数据删除】原因导致没做出来。 给你一个长度为 (N) 的序列 (A=(A_1,ldots,A_N)) 。保证 (A) 中的元素是不同的。 你要处理 (Q) 个操作。每个操作是以下两种类型之一: 1 x y :在 (A) 中元素 (x) 后面紧接着插入 (y) 。

    2024年03月13日
    浏览(10)
  • AT_abc344_d 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 你最开始有一个空字符串 (S) 。 你还有编号为 (1, 2, dots, N) 的袋子,每个袋子都包含一些字符串。 袋子 (i) 包含 (A_i) 个字符串 (S_{i,1}, S_{i,2}, dots, S_{i,A_i}) 。 对 (i = 1, 2, dots, N) 重复以下步骤 仅一次 (这里原题没有讲清楚

    2024年03月10日
    浏览(8)
  • 批量新增报错PSQLException: PreparedStatement can have at most 65,535 parameters.

    报错信息: org.postgresql.util.PSQLException: PreparedStatement can have at most 65,535 parameters. Please consider using arrays, or splitting the query in several ones, or using COPY. Given query has 661,068 parameters ; SQL []; PreparedStatement can have at most 65,535 parameters. Please consider using arrays, or splitting the query in several ones, o

    2024年02月05日
    浏览(8)
  • AtCoder Beginner Contest 350 (ABCDEF题)视频讲解

    AtCoder Beginner Contest 350 (ABCDEF题)视频讲解

    You are given a string S S S of length 6 6 6 . It is guaranteed that the first three characters of S S S are ABC and the last three characters are digits. Determine if S S S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest. Here, a string T T T is “the abbreviation of a contest held and concluded on AtCoder be

    2024年04月25日
    浏览(9)
  • Atcoder Beginner Contest 311 C - E题讲解

    Atcoder Beginner Contest 311 C - E题讲解

    Problem Statement There is a directed graph with N N N vertices and N N N edges. The i i i -th edge goes from vertex i i i to vertex A i A_i A i ​ . (The constraints guarantee that i ≠ A i i neq A_i i  = A i ​ .) Find a directed cycle without the same vertex appearing multiple times. It can be shown that a solution exists under the constraints of t

    2024年02月15日
    浏览(11)
  • AtCoder Beginner Contest 317(A~E题)讲解

    Problem Statement Naohiro has a monster. The monster’s current health is H H H . He also has N N N kinds of potions, numbered from 1 1 1 to N N N in ascending order of effectiveness. If you give the monster potion n n n , its health will increase by P n P_n P n ​ . Here, P 1 P 2 ⋯ P N P_1 lt P_2 lt dots lt P_N P 1 ​ P 2 ​ ⋯ P N ​ . He wants

    2024年02月11日
    浏览(10)
  • Atcoder Begginer Contest 327 讲解(A~E题)

    Atcoder Begginer Contest 327 讲解(A~E题)

    Problem Statement You are given a string S S S of length N N N consisting of lowercase English letters. If there are any adjacent occurrences of a and b in S S S , print Yes ; otherwise, print No . (The order of a and b does not matter.) 问题陈述 给你一个长度为 N N N 的字符串 S S S ,由小写英文字母组成。 如果在 S S S 中出现相邻

    2024年02月05日
    浏览(39)
  • Atcoder Beginner Contest 304——A-D题讲解

    Atcoder Beginner Contest 304——A-D题讲解

    蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提! Hello, 大家好哇!本 初中生蒟蒻 讲解一下 AtCoder Beginner Contest 304 这场比赛的 A-D题 ! =========================================================================================== 题目描述 Problem Statement There are N N N people numbered 1 , 2 , … , N 1, 2,

    2024年02月08日
    浏览(10)
  • AtCoder Beginner Contest 297——A-E题讲解

    AtCoder Beginner Contest 297——A-E题讲解

    蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提! Hello, 大家好哇!本 初中生蒟蒻 讲解一下 AtCoder Beginner Contest 297 这场比赛的 A-E题 ! 今晚比前面几场要简单点,但我在B题翻了下车,第一次提交竟然WA了,做题要仔细啊。 开心的是,今晚终于进到绿名了! ===============

    2024年02月03日
    浏览(8)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包