首页 > 其他分享 >cf1487g-solution

cf1487g-solution

时间:2024-02-28 13:46:28浏览次数:40  
标签:字符 26 sum pos solution gets cf1487g dp

CF1487G Solution

link

想一想没有字符的限制怎么做。

首先,没有长度大于一的奇回文串显然等价于没有长度为 \(3\) 的回文串。

也就等价于 \(\forall i\in[1,n-2],s_i\not=s_{i+2}\)。

那么在没有限制的情况下,我们确定好了前两位字符,后面的 \(n-2\) 位各有 \(25\) 种字符可选。

方案数即为 \(26^2\times25^{n-2}\)。

现在回到原题,我们考虑用全部方案数减去有字符超出限制的方案数得到答案。

注意到 \(c_i>\frac n 3\),这意味着超出限制的字符最多只有两个(否则字符数量将大于 \(n\))。

既然这样,答案就是全部方案数减去一个字符超限的方案数,再加上两个字符超限的方案数。

由于超限的字符顶多两个,我们试着 dp,设两个特殊字符 \(a,b\) 且 \(dp_{pos,i,j,x,y}\) 的五个维度分别表示:

\(pos\): 前 \(pos\) 位,\(i\): 字符 \(a\) 的数量,\(j\):字符 \(b\) 的数量,

\(x\in\{0,1,2\}\):第 \(pos-1\) 位为普通字符 / 字符 \(a\) / 字符 \(b\),\(y\) 同理表示第 \(pos\) 位。

那么初始状态:

\[dp_{1,0,0,0,0}\gets 24 \]

\[dp_{1,1,0,0,1}\gets 1 \]

\[dp_{1,0,1,0,2}\gets 1 \]

\[dp_{2,i,j,k,0}\gets dp_{1,i,j,0,k}\times24 \]

\[dp_{2,i,j,k,1}\gets dp_{1,i-1,j,0,k} \]

\[dp_{2,i,j,k,2}\gets dp_{1,i,j-1,0,k} \]

转移:

\[dp_{pos,i,j,k,0}\gets dp_{pos-1,i,j,0,k}\times23+dp_{pos-1,i,j,1,k}\times24+dp_{pos-1,i,j,2,k}\times24 \]

\[dp_{pos,i,j,k,1}\gets dp_{pos-1,i-1,j,0,k}+dp_{pos-1,i-1,j,2,k} \]

\[dp_{pos,i,j,k,2}\gets dp_{pos-1,i,j-1,0,k}+dp_{pos-1,i,j-1,1,k} \]

然后设 \(\displaystyle sum_{i,j}=\sum_{p=i}^n\sum_{q=j}^n\sum_{x=0}^2\sum_{y=0}^2dp_{n,p,q,x,y}\),也就是 \(dp_{n}\) 的后缀和,

那么答案即为 \(26^2\times25^{n-2}-\sum_{i=1}^{26}sum_{c_i+1,0}+\sum_{i=1}^{26}\sum_{j=i+1}^{26}sum_{c_i+1,c_j+1}\)。

时间复杂度 \(\mathcal O(n^3)\),空间复杂度滚掉一维可以 \(\mathcal O(n^2)\)。

标签:字符,26,sum,pos,solution,gets,cf1487g,dp
From: https://www.cnblogs.com/iorit/p/18040102

相关文章

  • cf1446d2-solution
    CF1446D2Solutionlink首先,最终答案区间中的众数一定包括整个序列的众数\(K\)。证明:设这个区间中众数出现次数为\(cnt\)。如果上述不成立,由于\(K\)在这个区间中出现次数小于\(cnt\),我们将区间向两边延申,\(K\)的出现次数应当不断增加直到等于区间的众数出现次数。这样子......
  • cf1396d-solution
    CF1396DSolutionlink题面:给你一个\(L\timesL\)的矩形,有\(n\)个点放在不同的格子内,每个点有颜色,共\(k\)种颜色,求有多少个矩形满足其内部含有所有颜色的点,对\(10^9+7\)取模。\(k\len\le2000,L\le10^9\)。首先离散化。看到数据范围说明可以枚举矩形的某个端点或者......
  • cf1340d-solution
    CF1340DSolutionlink手❤玩❤一❤下,答案大概就是所有点的度数最大值。下面证明。首先这个肯定是答案的下界,因为度数最大的点至少被经过了它的度数次。现在考虑构造。对于一棵以\(u\)为根的子树,如果我们能证明第一次到\(u\)的时间是\(t\),最后一次到\(u\)的时间是\(t-......
  • cf1332f-solution
    CF1332FSolutionlink设\(dp_{u,0/1,0/1}\)表示在\(u\)的子树中,节点\(u\)与它父亲的边是否在导出子图中,点\(u\)是否在独立集中,的方案数。\[dp_{u,0,0}\gets\prod_v(dp_{v,0,0}+dp_{v,1,0}+dp_{v,0,1}+dp_{v,1,1})\]\[dp_{u,1,0}\gets\prod_v(dp_{v,0,0}+dp_{v,1,0}+......
  • cf1303g-solution
    CF1303GSolutionlink\(k\)个数\(a_i\)的前缀和的和就是\(\displaystyle\sum_{i=1}^k(k-i+1)a_i\)。这个题可以考虑换一下\(u,v\),那么式子就变成了\(\displaystyle\sum_{i=1}^kia_i\)。注意到要统计树上路径的最值,考虑点分治。考虑上面的式子从\(j\)处断开,那么式子变......
  • cf1286d-solution
    CF1286DSolutionlink题面:有\(n\)个粒子,第\(i\)个粒子在位置\(x_i\)并有\(v_i\)的初速度。实验开始后,第\(i\)个粒子有\(p_i\)的概率向右移动,有\(1-p_i\)的概率向左移动。求第一次发生粒子碰撞的期望时间,对\(998244353\)取模。\(n\le10^5,|x_i|\le10^9\)。......
  • cf1265e-solution
    CF1265ESolutionlink题解在说啥???期望步数不就是期望轮数乘上每轮的期望步数期望轮数就是这轮结束的概率的倒数即\(\dfrac1{\prod_{i=1}^np_i}\)每轮期望步数根据期望的线性性就是\(\sum_{i=1}^ni(1-p_i)\prod_{j=1}^{i-1}p_j\)也就是步数乘上在这里停下来的概率,停下来的概......
  • 2.27 闲话 & solution 『你是太阳神倾倒而下美酒的甜香/是最高的永恒破碎之后的希望』
    考完试了,我想听歌写了几道LCT,但是都是板子我想听歌Cave洞穴勘测LCT板子啊,直接乱搞就行对于Connect操作和Destroy操作其实是Link和Cut的板子至于Query操作么...阿拉阿拉,直接对(u,v)都进行一次Find,然后判断是否相等即可核心代码就那么几行intn,m;FastI>>n>>m;while(m--......
  • cf1209g2-solution
    CF1209G2Solutionlink根据题意,对于一个颜色的所有下标集合\(S\),设其最小,最大位置是\(l,r\),那么最后染完色的\([l,r]\)区间一定是同一种颜色。如果有两个颜色\(i,j\),\([l_i,r_i]\)和\([l_j,r_j]\)有交集,那么这个区间并起来的大区间也一定是同一种颜色的。这样我们并并......
  • cf1153f-solution
    CF1153FSolutionlink题意:有一段长为\(l\)的线段,有\(n\)个实数区间,左右端点在\([0,l)\)间均匀随机。求期望被至少\(k\)段区间覆盖的长度,对\(998244353\)取模。\(1\lek\len\le10^7,1\lel\le10^{10^6}\)首先\(l\)是没用的,我们可以计算线段长为\(1\)时的......