题解 AT_abc288_h【A Nameless Counting Problem】
Nathaly
·
·
题解
非常好题目。
定义合法序列是满足如下条件的整数序列：
- 其中每个元素均在 [0,M] 中；
- 所有元素的异或和是 X。
注意到若 A_i=A_{i+1}，则直接删掉 A_i,A_{i+1} 不会对整个序列的异或和造成影响。于是，假如能算出 g_i 表示长为 i 的不含重复元素的合法序列，那么我们再枚举有多少个重复元素，最终的答案就是
\sum_{0\le i\le N/2} \frac{g_{N-2i}}{(N-2i)!}\binom{M+i}{i}.
于是只需要考虑如何算 g。由于 x\operatorname{xor} x=0，所以一个长度为 l 的含有重复数字的合法序列，一定可以被缩成长度 <l 的不含重复数字的合法序列。利用这个可以进行容斥，假设当前要计算 g_l，我们先计算 f_l 表示长为 l 的合法序列个数，开始时令 g_l\gets f_l。
再减去包含重复元素的合法序列个数，设：
- 序列中有 i 个出现了奇数次的元素；
- 序列中有 j 种出现了奇数次的数字；
- 序列中有 k 种出现了偶数次的数字。
那么这个序列有重复元素，当且仅当 j<l。我们可以将这个序列缩成长为 j 的不包含重复数字的序列，因此对于固定的 (i,j,k)，满足条件的序列个数是
\binom{l}{i} \mathrm{odd}_{i,j} g_j \mathrm{even}_{l-i,k}(M+1-j)^{\underline{k}}.
其中 \mathrm{odd}_{i,j} 表示将 i 个可区分的元素划分成 j 个不可区分的集合，使得每个集合的大小都是奇数的方案数，\mathrm{even}_{i,j} 同理。
对于所有的 i\in [0,l],j\in [0,l-1],k\in [0,l]，我们都令 g_l 减掉上面的式子，最终就能计算出所有 g_0,g_1,\dots,g_n。
上述所有过程中，只有 f 的计算是 O(N^3\log X) 的，其余都是可以做到 O(N^3) 的。
代码：https://atcoder.jp/contests/abc288/submissions/38666417。