2026.5 折腾吉林

qoj6891 String and GCD
何意味，核桃上 8s 512MB TLE，qoj 上 16s 256MB MLE。
这个答案看起来没有性质，考虑把每个 \(f\) 算出来。
你发现这个 \(j\) 其实是 \(s[1:i]\) 的 border，直接建 border 树！
border 树就是，对每个 \(i\) 找到最长的 border 长度 \(j\)，连 \(j\) 和 \(i\) 的边，如果没 border 那么 \(j=0\)。树根为 \(0\)。
这个 \(f(i)\) 就是 \(i\) 在树上所有祖先和它的 \(\gcd\)，这里规定 \(\gcd(0,x)=0\)。
对于 \(f(i)\)，你如果直接枚举 \(\gcd\) 然后算出现次数的话会很难做，注意到 \(\sum\limits_{d\mid n}\varphi(d)=n\)，所以可以算 \(i\) 的因子的出现次数。
枚举因子，然后对它的倍数建虚树，就做完了。
时间单 \(\log\)。
CF995F Cowmpany Cowmpensation
直接 dp 会爆。
显然的，记 \(g_i\) 表示只填 \(i\) 种不同的数上去且根填的是 \(i\) 的种类数，答案就是 \(\sum_{i=1}^{\min(n,m)}\binom{m}{i}g_i\)。
这个东西看上去要容斥。设 \(f_{i,j}\) 表示只考虑 \(i\) 子树，\(i\) 填 \(j\) 的方案数，前缀和优化一下就是 \(O(n^2)\)。
容斥是简单的，若现在算到 \(g_i\)，且 \(g_{1}\) 到 \(g_{i-1}\) 都做完了，那么 \(g_{i}=f_{1,i}-\sum_{j=1}^{i-1}\binom{i-1}{j-1}g_j\)。
CF891E Lust
你发现这个 \(res\) 其实是 \(\prod a_i\) 减去最后序列的乘积。
就能列出一个东西

\[res=\frac{1}{n^k}\sum_{\sum c=k}\prod(a_i-c_i)\times\frac{k!}{\prod c_i!} \]

\[=\frac{k!}{n^k}\sum_{\sum c=k}\prod\frac{a_i-c_i}{c_i!} \]

设 \(F_j(x)=\sum_{i\ge 0}(a_j-x)\frac{x^i}{x!}\)。注意到 \(e^x=\sum_{i\ge 0}\frac{x^i}{i!}\)，所以

\[F_j(x)=(a_j-x)e^x \]

\[res=\frac{k!}{n^k}[x^k]\prod F_i(x) \]

\[=\frac{k!}{n^k}[x^k]e^{nx}\prod(a_i-x) \]

\[=\frac{k!}{n^k}[x^k]\sum_{i\ge 0}\frac{n^i}{i!}x^i\prod(a_i-x) \]

\(\prod(a_i-x)\) 可以用分治+FFT 或者做 \(n\) 次 FFT 求出来。令 \(\prod(a_i-x)=\sum_{i=0}^{n}f_ix^i\)，则

\[res=\frac{1}{n^k}\sum_{i=0}^{n}f_in^{k-i}\times\frac{k!}{(k-i)!} \]

直接爆算！