首页 > 其他分享 >AT_abc279_g [ABC279G] At Most 2 Colors 题解

AT_abc279_g [ABC279G] At Most 2 Colors 题解

时间:2023-10-02 22:13:38浏览次数:45  
标签:颜色 int 题解 Most Colors abc279 dp

题解

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

  1. 第 \(i\) 个前面 \(k-1\) 个位置有2种颜色,则第 \(i\) 个位置只能放这两种颜色中的一种
    用合法方案减只有一种的方法,即得两种颜色的方案数
    而只有一种颜色的方案数,等于 \(f[i-k+1]\),
    此时,让中间的 \(k-2\) 个格子都和 \(i-k+1\) 涂一样的即可。

  2. 第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

相关文章

  • P4839 P 哥的桶 题解
    题目大意有\(n\)个桶,\(m\)次操作。在\(pos\)桶中加入一个\(val\)值,求\([l,r]\)中选任意个桶使得异或和最大,求最大的异或和,注意每个节点是一个桶可以放多个值\(n,m≤5×104\)。题目思路单点修改,区间查询,异或最大值很显然是线段树维护线性基然后这样的复杂度是......
  • CF906C题解
    可能更好的阅读体验大家好,我和DP有仇,所以我用猜结论的方法过了这道题。可能是这道题的一个全新思路,可能人自闭久了什么都能想出来(((upd:好像这也是官方题解思路,看来大家做题不太喜欢看CF官方题解(((首先考虑一个问题:如果这是一道构造题,怎么构造一组合法的解?在草稿纸上画了很久......
  • P2230 Tinux系统 题解
    传送门题目大意:一个\(n\)个叶子节点,一个节点最多可以有\(k\)条边连向子节点,每个节点\(i\)有一个权值\(P_{i}\)。记每个节点子树内点的个数(不包括它自己)为\(son_{i}\),那么每个节点对答案的贡献就是\(son_{i}^2\timesP_{i}\)。特别的,根节点贡献为\(0\),求总贡献。两......
  • P1045 麦森数 题解
    传送门前排提醒:本篇题解没有使用压位和快速幂,运用了一种预处理的思想,希望能提供一种新的思路。首先将\(2^{p}-1(d)\)转换为\(1111…111(b)\)。关于第一问:我们先考虑\(2\)进制转\(8\)进制,将每\(3\)位转为\(1\)位,即每\(\log{8}\)位转为\(1\)位。\(2\)进制转......
  • UVA1471 防线 Defense Lines 题解
    传送门首先可以将题意大概可以简化为:取两端不重复的连续子序列,组成一个最长的连续递增子序列。我们先dp预处理出以\(i\)为结尾的连续递增子序列长度\(dpr_{i}\)。同样预处理出以\(i\)为开头的连续递增子序列长度\(dpl_{i}\)。考虑对于每个\(dpr_{i}\),找到满足\(a_{......
  • P5503 灯塔 题解
    决策单调性二分传送门数据加强版:P3515前置知识:二分,决策单调性首先很容易写出答案式子:\[ans_{i}=\max_{j=i}^{n}{(a_{j}-a_{i}+\lceil\sqrt{\left|i-j\right|}\rceil)}\]先将向上取整符号拆掉,只要在输出时处理就行。再将绝对值符号拆掉,分\(j<i\)和\(j>i\)的情况......
  • 题解 Codeforces Round 901 (Div. 1) / CF1874A~E
    题解CodeforcesRound901(Div.1)/CF1874A~E比赛情况:过了AB。赛后发现B是假复杂度。https://codeforc.es/contest/1874A.JellyfishandGameProblemAlice&Bob又在博弈,Alice手上有\(n\)个苹果,第\(i\)个苹果的价值是\(a_i\);Bob手上有\(m\)个苹果,第\(i\)......
  • [题解]AT_abc240_f [ABC240F] Sum Sum Max
    思路题目要求的是\(\max_{a=1}^{n}\{\sum_{i=1}^{a}\sum_{j=1}^{a}{A_j}\}\),所以我们将\(\sum_{i=1}^{a}\sum_{j=1}^{a}{A_j}\)化简一下,得:\[i\timesA_1+(i-1)\timesA_2+\dots+1\timesA_x\]在\(a\)每增加\(1\)时,这个和\(s\)将会变为\(s+......
  • [题解]AT_abc245_f [ABC245F] Endless Walk
    思路首先我们可以发现,在任意一个节点数量大于\(1\)的强连通分量中的点都满足条件。所以,我们可以对这张图跑一边TarJan。但是这样是错的,因为我们还需要考虑节点数量为\(1\)的强连通分量。如果这种连通分量能够到达任意一个节点数量大于\(1\)的强连通分量,那么,这个连通分......
  • CSES.1141 C++题解
    题意传送门有一个长度为\(n\)的歌单,问最长多少首歌互不相同?每首歌用一个\(1-10^9\)的整数表示。样例输入812132742样例输出5算法双指针算法。桶思想。对于歌单中重复出现的数,可以用桶来存储。定义两个指针i,j,i指向大数,j指向小数。当出现某个桶的数大于1时,则......