「Celeste-B」Say Goodbye

做法一

提供一个后半部分略微不同的做法。

首先，基环旋转同构肯定是用 Burnside 那套理论求不动点来解，设 \(f(n, m)\) 为每种颜色 \(/m\) 构成 \(n\) 棵（树之间有标号）无标号有根有序带颜色树的方案，那么答案为（记 \(G = \gcd(a_1, a_2, \cdots a_n)\)）：

\[\begin{aligned}
& \ \ \ \ \ \sum\limits_{i = 2} ^ m \frac{1}{i} \sum\limits_{j \mid i} [\forall k \in [1, n], \frac{i}{j} \mid a_k] f(j, i / j) \varphi(i / j)\\
&= \sum\limits_{i = 2} ^ m \frac{1}{i} \sum\limits_{j \mid i} [j \mid G] f(i / j, j) \varphi(j)\\
&= \sum\limits_{i \mid G} \sum\limits_{i \mid j} \frac{1}{j}f(j / i, i)\varphi(i) - f(1, 1)
\end{aligned}
\]

考虑一下 \(f\) 怎么求，由于是无标号有根有序带颜色树的方案，可以先忽略颜色的限制，最后再染色即可。

令 \(g(s) = \frac{(m / s)!}{\prod\limits_{i = 1} ^ n (a_i / s)!}\)，\(f'(n, m)\) 为 \(m\) 个点构成 \(n\) 棵（树之间有标号）无标号有根有序树的方案，则：

\[f(n, k) = g(k) \times f'(n, m / k)
\]

考虑怎么求 \(f\)，注意到一颗无标号有根有序树方案为卡特兰数 \(C(x)\) 前一项的值，则有：

\[f'(m, n) = [x ^ n](xC(x)) ^ m
\]

有 \(C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}, F(x) = xC(x) = \frac{1 - \sqrt{1 - 4x}}{2}\)，易得 \(F(x)\) 复合逆 \(G(x) = x(1 - x)\)，令 \(H(x) = x ^ m\)，则根据扩展拉格朗日反演：

\[\begin{aligned}
f'(m, n) &= [x ^ n](xC(x)) ^ m\\
&= [x ^ n]H(F(x))\\
&= \frac{1}{n}[x ^ {n - 1}]H'(x)\left(\frac{x}{G(x)}\right) ^ n\\
&= \frac{m}{n}[x ^ {n - m}]\frac{1}{(1 - x) ^ n}\\
&= \frac{m}{n}\binom{2n - m - 1}{n - 1}
\end{aligned}
\]

当然，这个通项公式也存在一个组合解释，下面考虑 \([x ^ n]C ^ m(x)\) 的组合意义：

所有合法长度为 \(2n\) 的完美匹配括号序列划分成 \(m\) 个完美匹配括号序列的方案，划分可以为空。

将括号序列转化为 \(1 / -1\) 排列的问题，可以将一个划分的末尾加上一个 \(-1\) 以示区分，为了方便不在最后放 \(-1\)，发现此时的括号序列满足两个必要条件：

有 \(n\) 个 \(1\) 和 \(n + m - 1\) 个 \(-1\).
任意前缀前缀和 \(\ge -m + 1\).

此时容易证明这两个必要条件也是充要条件，将这个问题再转化，就是从 \((0, 0)\) 开始走到 \((n, n + m - 1)\) 不穿过 \(y = x + m - 1\) 的方案，这是一个经典问题，答案为：

\[\binom{2n + m - 1}{n} - \binom{2n + m - 1}{n - 1}
\]

此时通过简单化简就可以解释由拉格朗日反演导出的组合恒等式。

带回最初的答案式：

\[\frac{1}{m}\left(\sum\limits_{i \mid G} g(i) \varphi(i)\sum\limits_{j = 1} ^ {m / i} \binom{2(m / i) - j - 1}{m / i - 1} - g(1)\binom{2m - 2}{m - 1}\right)
\]

可以直接暴力计算，复杂度 \(\mathcal{O}(n\sigma_0(G) + \sigma_1(m))\).

做法二

将 \(f\) 直接带入初始的表达式：

\[\begin{aligned}
& \ \ \ \ \ \sum\limits_{i \mid G} \sum\limits_{i \mid j} \frac{1}{j}f(j / i, i)\varphi(i) - f(1, 1)\\
&= \sum\limits_{i \mid G} g(i)\varphi(i) \sum\limits_{i \mid j} \frac{1}{j} [x ^ {m / i}]F ^ {j / i}(x) - \frac{1}{m}g(1)\binom{2m - 2}{m - 1}\\
&= \sum\limits_{i \mid G} \frac{1}{i}g(i)\varphi(i) [x ^ {m / i}]\sum\limits_{j = 1} ^ {m / i} \frac{F ^ {j}(x)}{j} - \frac{1}{m}g(1)\binom{2m - 2}{m - 1}\\
&= \sum\limits_{i \mid G} \frac{1}{i}g(i)\varphi(i) [x ^ {m / i}]\sum\limits_{j = 1} ^ \infty \frac{F ^ {j}(x)}{j} - \frac{1}{m}g(1)\binom{2m - 2}{m - 1}\\
&= \sum\limits_{i \mid G} \frac{1}{i}g(i)\varphi(i) [x ^ {m / i}]-\ln(1 - F(x)) - \frac{1}{m}g(1)\binom{2m - 2}{m - 1}\\
\end{aligned}
\]

于是可以先多项式求 \(\ln\) 再直接暴力统计，复杂度 \(\mathcal{O}(m \log m + n\sigma_0(G))\)，注意学习和式修改上界的技巧。

巴特西

「Celeste-B」Say Goodbye

做法一

做法二

最新文章

热门文章