好题分享
GDSYZX cjh
题目描述
https://vjudge.csgrandeur.cn/problem/OpenJ_Bailian-4052
你将制作一条项链。项链由 \(m\) 颗宝石组成，有 \(n\) 种宝石可供选用。对于第 \(i\) 种宝石，它在项链上的出现次数是如下四种限制中的一种：
A要求第 \(i\) 种宝石的出现次数为奇数。B要求第 \(i\) 种宝石的出现次数为偶数。C要求第 \(i\) 种宝石至少出现一次。D不对出现次数作要求。
求可以制作多少种不同的项链。两条项链不同，当且仅当组成项链的宝石排成一排后不能旋转同构。
模 \(10007\)，多测 \(T\leq 50, n\leq 25, m\leq 10^5\)。
Polya 原理
考虑所有宝石都是 D 限制的情况。用置换群的概念刻画旋转同构，我们记一个群 \(G\)，\(G\) 里面是所有的旋转置换，例如当 \(m=5\) 时就有
这五个置换。同时要注意群的其他性质。将运算定义为置换的复合，则这个群有单位元 \(\binom{1, 2, 3, 4, 5}{1, 2, 3, 4, 5}\)，运算满足结合律，\(G\) 中元素互相复合后还在 \(G\) 中，\(G\) 确实是一个群。
Polya 原理告诉我们，若想知道项链在 \(G\) 中置换的作用下有多少个本质不同的项链，则它是：
其中 \(cyc(g)\) 表示有多少条项链使得被 \(g\) 作用之后仍不变。对于旋转置换 \(i\to (i+d)\bmod n\)，\(cyc(g)\) 就是将项链（这时候看作链）拆成 \(n/\gcd(n, d)\) 段，要求每一段都相等，这样旋转之后不变。
指数生成函数
不考虑旋转同构的限制，如何求出方案数？使用指数生成函数 EGF。
数列 \(a = \{a_0, a_1, a_2, \cdots\}\) 的 EGF 为 \(A(x) = \sum_{i=0}^\infty a_i\dfrac{x^i}{i!}\)。两个 EGF 的二项卷积 \(A*B\) 定义为：
也就是 \(c_n=\sum_{i}\binom n ia_ib_{n-i}\)。这个卷积的意义在于，如果 \(a_i, b_i\) 表示某种大小为 \(i\) 的组合对象的方案数，那么 \(c_i\) 就表示大小为 \(i\)，由 \(a, b\) “归并”而成的组合对象的方案数。例如 AA 和 CD 归并有 \(\binom{2+2}{2}=6\) 种结果：AACD, ACAD, ACDA, CADA, CAAD, CDAA。就是原来的每一种方案，保持原来顺序的前提下插入到另一种方案，而 EGF 刻画的就是这个东西。
另外有 \(e^x=\sum_{i=0}^\infty x_i/i!\)。
考虑题目中的宝石怎么刻画限制。
- 出现次数为奇数，可以认为是所有奇数个数都有一个方案，偶数个数没有方案，所以尝试找到 \(\{0, 1, 0, 1, 0, 1, \cdots\}\) 的 EGF。它为 \(\dfrac{e^x-e^{-x}}{2}\)，可以感受一下正确性。
- 出现次数为偶数：\(\dfrac{e^x+e^{-x}}{2}\)。
- 至少出现一次：\(e^x-1\)。
- 没有限制：\(e^x\)。
记限制 ABCD 的出现次数为 \(a, b, c, d\)，则答案为
使用二项式定理展开这些式子并暴力相乘，最终得到类似于 \(\sum_kc_ke^{d_ix}\) 的东西。提取 \([x^n/n!]\) 系数，实际上就是分开每一项，因为 \([x^n/n!]ce^{dx}=cd^n\)，所以答案就是 \(\sum_k c_kd_k^n\)。
细节
- 最终统计答案的时候大概是这样：\(ans = \sum_{i=1}^mcalc(\gcd(i, m))/m\)。其中 \(calc(n)\) 计算项链长度为 \(n\) 时的答案，不考虑旋转同构。
- 如果 \(10007|m\)，\(m\) 没有逆元，考虑先计算答案模 \(10007^2\) 的结果 \(ans'\)，然后计算 \(ans=\frac{ans'/10007}{m/10007}\)，这时候 \(m/10007\) 在 \(\pmod {10007^2}\) 意义下有逆元，可以计算。
- 时间复杂度视具体实现大约为 \(O(Tn^2\log n\sqrt m)\)。