CF1487G Solution
想一想没有字符的限制怎么做。
首先,没有长度大于一的奇回文串显然等价于没有长度为 \(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