CF2134F Permutation Oddness
Diff：*2900
有 \(4\) 种数，如果要直接 \(\mathrm{dp}\) 造出序列时间复杂度是 \(O(n^5)\) 的，无法接受。考虑挖掘一下 \(\mathrm{lowbit}(b_i,b_{i+1})\) 的性质，注意到若 \(b_i=b_{i+1}\) 值是 \(0\)，如果组成 \((0,2),(1,3)\) 则值为 \(2\)，其他情况都是 \(1\)。此处考虑一个染色的技巧，将 \(0,2\) 染成红色，\(1,3\) 染成蓝色，则原序列可以刻画成一个红蓝极长连续段交替的形式，这样不同连续段之间的贡献就是 \(1\)，同一连续段内相同数贡献是 \(0\)，不同数贡献是 \(2\)。我们发现这样似乎比较好做了，因为我们可以将红色和蓝色连续段分开算，然后最后对应超级拼装起来，那么只需思考如何对红色求出方案数，蓝色同理。
考虑定义 \(r(i,j)\) 表示红色连续段个数为 \(i\)，这些连续段内部的贡献为 \(j\) 的连续段方案数。只有异色，即交替才有贡献，先考虑一个连续段内部的情况。定义 \(f(i)\) 表示用 \(c_0\) 个 \(0\)，\(c_2\) 个 \(2\) 组成的、交替数量恰好为 \(i\) 的方案数，这是一个经典的组合计数，考虑相同数组成的连续段，如果有 \(j\) 个那么交替数量就是 \(j-1\)，那么交替数量为 \(i\) 等价于同数连续段有 \(k=i+1\) 个。交替，考虑对 \(k\) 奇偶分类：
记 \(F(n,m)\) 表示把 \(n\) 个相同数划分成 \(m\) 个连续段的方案数，用插板法得到 \(F(n,m)=\binom{n-1}{m-1}\)。
- \(k\) 为奇数，记 \(k=2m+1\)
- 以 \(0\) 开头。那么 \(0\) 的连续段有 \(m+1\) 个，\(2\) 的连续段有 \(m\) 个，分别划分后拼接，方案数为 \(F(c_0,m+1)\times F(c_2,m)=\binom{c_0-1}{m}\binom{c_2-1}{m-1}\)。
- 以 \(2\) 开头。那么 \(0\) 的连续段有 \(m\) 个，\(2\) 的连续段有 \(m+1\) 个，同理方案数为 \(F(c_0,m)\times F(c_2,m+1)=\binom{c_0-1}{m-1}\binom{c_2-1}{m}\)。
- \(k\) 为偶数，记 \(k=2m\)
两者都有 \(m\) 个连续段，区分开头顺序有 \(2\) 种拼接方案，方案数为 \(2\cdot F(c_0,m)\times F(c_2,m)=2\binom{c_0-1}{m-1}\binom{c_2-1}{m-1}\)。
再将 \(k\) 变回 \(i\)，整理一下，得到：
\[f(2m)=\binom{c_0-1}{m}\binom{c_2-1}{m-1}+\binom{c_0-1}{m-1}\binom{c_2-1}{m} \\f(2m-1)=2\binom{c_0-1}{m-1}\binom{c_2-1}{m-1}\]
那么考虑用 \(f\) 计算 \(r\)，枚举 \(j\) 表示要划分有 \(j\) 个异色相邻的序列，其方案数对应 \(f(j)\)，划分时如果切开了两个相同色的则是没有贡献的，如果切开异色的则贡献为 \(-2\)，于是枚举 \(k\) 表示有多少个切到了异色位置，选择方案数是 \(\binom{j}{k}\)，对于同色部分可以随便放，总共有 \(c_0+c_2-1\) 个位置，\(j\) 个是异色的，则有 \((c_0+c_2-1-j)\) 个同色，划分成 \(i\) 段有 \((i-1)\) 个划分位置，划分异色用了 \(k\) 个，则有 \((i-1-k)\) 个用于划分异色，因此方案数为 \(\binom{c_0+c_2-1-j}{i-1-k}\)，综上得到：
\[r_{i,2(j-k)}\leftarrow f_j\times \binom{j}{k}\binom{c_0+c_2-1-j}{i-1-k}\]
同理可以计算出 \(b(i,j)\) 表示蓝色信息。接着就要用 \(r_{i,j}\) 拼装得到 \(ans\)，枚举 \(i_r,i_b\) 分别表示红、蓝连续段的个数，不难发现此时有 \(i_b\in [i_r-1,i_r+1]\)，这一部分的贡献就是连续段相接的部分，即 \((i_r+i_b-1)\)，再枚举 \(j_r,j_b\) 表示红蓝内部的贡献，拼接时再对开头方案数讨论，易得：
\[ans_{i_r+i_b-1+j_r+j_b}\leftarrow (1+[i_r=i_b])\cdot r(i_r,j_r)\times b(i_b,j_b)\]
时间复杂度是 \(O(n^3)\)，可以通过。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
