《通用测评号》
对不起，之前写错了。我是菜菜，我谢罪。
枚举一个最后填至燃料足够，枚举一个提供贡献。
\[\frac{n^{-b}x^{b-1}}{(b-1)!}\left(\exp(n^{-1}x)-\sum_{i=0}^{a-1}\frac{n^{-i}x^i}{i!} \right)\left(\exp(n^{-1}x)-\sum_{i=0}^{b-1}\frac{n^{-i}x^i}{i!} \right)^{n-2}\]
二项式展开，只需计算 \(\left(\sum_{i=0}^{b-1}\frac{n^{-i}x^i}{i!}\right)^j\;(j\leqslant n-2)\) 。写个 \(\textit{NTT}\) 可以做到 \(\mathcal O[n^2a\log(na)]\)，但是好讨嫌啊。
回想做过的题，注意到实际有用的操作只有 \(\mathcal O(na)\) 个，所以背包：设 \(f(i,j)\) 为已操作 \(i\) 次、\(j\) 个已填满的概率。转移是 \(f(i,j)\to\frac{1}{n-j}f(i{+1},j)\) 和 \(f(i,j)\to{i-ja\choose a-1}f(i{+}1,j{+}1)\) 。
答案是 \(\sum\frac{f(i{-}1,j)}{n-j}g(i{-}ja,n{-}j)\cdot j\)，其中 \(g(s,k)\) 为用 \(s\) 次操作恰好将 \(k\) 个燃料舱填至 \([b,a)\) 内的方案数。显然 \(g(s,k)=k{s-1\choose b-1}h(s{-}b,k{-}1)\)，其中 \(h(s,k)\) 为用 \(s\) 次操作将 \(k\) 个燃料舱填至 \([b,a)\) 内的方案数。
显然 \(h(s,k)\) 是简单背包，可以前缀和优化。所以这是 \(\mathcal O[na(n{+}a)]\) 的非多项式解法。
《百鸽笼》
允许鞭尸。经典猎人杀。
\[F_i(x)=\sum_{j\geqslant a_i}\frac{n^{-j}x^j}{j!}=\exp(n^{-1}x)-\sum_{j=0}^{a_i-1}\frac{n^{-j}x^j}{j!}\]
\[ans_i=\frac{n^{-a_i+1}x^{a_i-1}}{(a_i-1)!}\mathcal H\left[\prod_{j=1}^{n}F_j(x)^{[j\ne i]}\right]\]
视作关于 \(\exp(n^{-1}x)=y\) 的（二元）多项式。其中算子 \(\mathcal H\) 是
\[\mathcal H(f)=\sum_{i\geqslant 0}f^{(i)}(0)\]
它可以计算含 \(y\) 的式子。比如
\[\begin{aligned}\mathcal H(\exp(vx)f)&=[x^0]\exp(vx)f+\mathcal H(v\exp(vx)f)+\mathcal H(\exp(vx)f')\\\Rightarrow(1-v)\mathcal H(\exp(vx)f)&=\mathcal H(\exp(vx)f')+[x^0]f\end{aligned}\]
递归出口
\[\mathcal H(\exp(vx))=\frac{1}{1-v}\]
\(\mathcal O(\deg)\) 搞定。这一步的总复杂度 \(\mathcal O(n^3 a)\) 很小。
将所有多项式乘起来需要 \(\mathcal O(n^3 a^2)\)，然后 做除法。不太好写，但我们不得不这样。
《新年的追逐战》
两个点连通，当且仅当在每张图中，对应节点都可以同时走奇数条边 \(or\) 偶数条边达到。
首先 “走偶数条边可达” 是良定义的等价性。于是有四类点：有奇环的连通块、二分图连通块的 \(\frak X\) 部、\(\frak Y\) 部、孤点（并不能说 “偶数条边都可达”）。
这四类内任选，不可能 “偶数条边可达”。但如果选择了至少一个 \(\frak X\) 部或 \(\frak Y\) 部，就存在一个 “奇数条边可达” 的对称状态。因此，设第 \(i\) 张图中有 \(x_i\) 个连通块是二分图、\(y_i\) 个连通块是非二分图、\(z_i\) 个孤点，则答案为
\[\frac{\prod(2x_i+y_i+z_i)+\prod(y_i+z_i)}{2}\]
分子的两个值可以分别计算。显然 \((2x_i+y_i+z_i)\) 严格更难算。只考虑之。
记 \(F(x)\) 为连通二分图的数量的 \(\rm EGF\)，只有边的存在情况不同被视作不同。
引入 辅助量 \(\varPhi(x)\) 为染色二分图（边的存在情况不同或 黑白染色情况不同 则不同）的数量的 \(\rm EGF\) 。注意到连通二分图 恰有两种染色方案，因此有
\[\begin{aligned}\varPhi(x)&=\sum_{i\geqslant 0}\frac{2^iF(x)^i}{i!}=\exp(2F(x))\\\end{aligned}\]
于是 \(F(x)=\frac{1}{2}\ln\varPhi(x)\)，而 \([{x^n\over n!}]\varPhi(x)=\sum_{i=0}^{n}{n\choose i}2^{i(n-i)}\) 易知。
\(\sum_{i=0}^{n}{n\choose i}2^{\frac{1}{2}n^2}\cdot 2^{-\frac{1}{2}(n-i)^2}\cdot 2^{-\frac{1}{2}i^2}\) 可以通过卷积求出，因此 \(F(x)\) 可知。
按：\(\textsf{Cirno9}\) 给出了 \(\textit{GGF}\) 的，看似暴力的，计算方法。我在此只能表示膜拜。
设连通非二分图的数量的 \(\rm EGF\) 为 \(G(x)\)，用连通图数量减 \(F(x)\) 即得。孤点的 \(\rm EGF\) 嘛……
现只需对所有 \(m\) 算出所有方案的 \(\sum(2x+y+z)\) 。计算每个连通块的贡献可知其为
\[[x^m](2F(x)+G(x)+x)\exp(F(x)+G(x))\]
其中 \(\exp(F(x)+G(x))\) 就是 \(2^{n(n-1)\over 2}\) 的 \(\rm EGF\) 。于是 \(\mathcal O(n\log n)\) 完成了所有事情。
《Math Ball》
\[\begin{aligned}F_i(x)&=\sum_{j\geqslant 0}j^{c_i}x^j\\ans&=[x^{w}]\frac{1}{1-x}\prod F_i(x)\end{aligned}\]
\[F_i(x)=\sum_{p=0}^{c_i}p!{c_i\brace p}\sum_{j\geqslant 0}{j\choose p}x^{j}=\sum_{p=0}^{c_i}p!{c_i\brace p}\frac{x^{p}}{(1-x)^{p+1}}\]
乘积的形式必为
\[\sum_{t=0}^{\sum c_i}\frac{f_t\cdot x^t}{(1-x)^{t+n}}\]
分治 \(\textit{NTT}\) 求呗。注意要按照 \(\sum c_i\) 均分。最后只需提取 \([x^w]\frac{f_t\cdot x^t}{(1-x)^{t+n+1}}=f_t{n+w-t\choose t+n}\)，组合数可递推（上下指标有 \(\mathcal O(1)\) 的变化）。复杂度 \(\mathcal O(\sum c_i\log^2\left(\sum c_i\right))\) 。
《RNG and XOR》
记集合幂级数——本质是 \(n\) 元生成函数——有
\[\pi(x)\cdot A(x)+\sum_{S\subseteqq\Bbb U}x^{S}=\pi(x)+\kappa x^0\]
其中 \(\kappa=1+\sum_{S\subseteqq\Bbb U}a_S e_S\) 为未定值。转点值有
\[\hat{e_S}\hat{a_S}+\hat{\lambda_S}=e_S+\kappa\]
由是 \(\hat{e_S}\) 为关于 \(\kappa\) 的一次式。解出值后核对 \(e_S=0\) 即可。复杂度 \(\mathcal O(n2^n)\) 。
Remark：能不能保证 \(\hat{e_S}\) 的 \(\kappa\) 系数非零？
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
