CF1227F2 题解

· · 题解

这道题二维 dp 的方法就行不通了。我尝试优化 dp 状态但是失败了（悲），考虑一下奇妙的性质和数学手段。

我做这个题还是基于简单版的式子的。先把式子一放：

设 f_{i,j} 表示填完前 i 个位置，提交答案错位后比原来多对了 j 个题的方案数。

如果 a_i=a_{(i \bmod n) +1}，则 f_{i,j}=f_{i-1,j}\times k。

否则 f_{i,j}=f_{i-1,j+1}+f_{i-1,j-1}+f_{i-1,j}\times(k-2)。

式子很好理解，不懂的话随便去简单版的题解区看一眼就懂了。

有一个性质：f_{i,j}=f_{i,-j}。即固定 i 后第二维对称位置相等。尝试用数学归纳的思想证明这个结论，即从 f_i 这一维性质成立推出 f_{i+1} 这一维也成立。

首先考虑 i=0，f_{0,0}=1，其余值都为 0，满足对称性质。

现在假设 f_i 这一维已经成立了，我们推 f_{i+1} 这一维。

先看 a_i=a_{(i \bmod n) +1} 的情况。f_{i+1,j}=f_{i,j}\times k 且 f_{i+1,-j}=f_{i,-j}\times k。由于第 i 维满足那个性质，所以 f_{i,j}=f_{i,-j}，故 f_{i+1,j}=f_{i+1,-j}。

再考虑其余情况。f_{i+1,j}=f_{i,j+1}+f_{i,j-1}+f_{i,j}\times(k-2) 且 f_{i+1,-j}=f_{i,-j+1}+f_{i,-j-1}+f_{i,-j}\times(k-2)。由于第 i 维满足性质，所以 f_{i,j}=f_{i,-j}，f_{i,j-1}=f_{i,-j+1}，f_{i,j+1}=f_{i,-j-1}。不难发现，f_{i+1,j} 和 f_{i+1,-j} 还是相等。

于是我们成功证明了 f_{i,j}=f_{i,-j}。

我们最后的答案是 \sum_{i=1}^n f_{n,i}，结合上面的性质，这个东西其实就是总方案减去 f_{n,0} 再除以 2。即：

\frac{k^n-f_{n,0}}{2}

问题变成了填完 n 个位置的数有多少种方案满足错不错位得分一样。这就是一道简单的组合数学题了。有一些位置 i 满足 a_i=a_{(i \bmod n) +1}，这些位置可以随便填，因为错不错位这个数对应的正确答案都是一样的，错位和不错位两种情况在该题的正误情况应该相同。计不满足该条件的位置数量为 m，这些位置是需要仔细考虑的。

对于这 m 个位置，我们枚举 i，表示原来的答案和错位的答案分别有 i 个位置是正确的。我们先从这 m 个位置中挑 i 个位置让原来答案的这一位正确，再从 m-i 个位置中挑 i 个位置让错位答案的这一位正确。还剩 m-2\times i 个位置，这些位置要求原答案和错位答案都错，每位有 k-2 种填法（扣除 a_i 和 a_{(i\bmod n)+1} 两种填法）。于是：

f_{n,0}=k^{n-m}\times \sum_{i=0}^{\left\lfloor\frac{m}{2}\right\rfloor}\times C_{m}^i\times C_{m-i}^i\times (k-2)^{m-2\times i}

代码很好写，不放了。任何疑问欢迎评论区留言，我会尽量及时回复。