2024省选准备

省选准备?

P3726 [AH2017/HNOI2017] 抛硬币

要求

$$
\sum_i \sum_j [j<i] \binom{a}{i}\binom{b}{j}
$$

这就不会了, 然而这是双射题, 考虑 $a=b$ 的时候赢的翻转能映输的, 就只需要求平局的 $\sum_i \binom{a}{i}^2$ 是经典问题.

现在 $a>b$, 设实际各证明 $x, y$ 次, 则 $a$ 输/平的翻转都会变成赢($x\le y, a-x>b-y$), 而问题就是A赢的可能仍然是赢, 这种情况要求 $a-x>b-y, x>y$, 于是 $x-y\in [0, a-b]$, 而 $a-b$ 很小, 枚举个差, 就是 $\sum_d \sum_i \binom{a}{i+d}\binom{b}{i}=\sum_d \sum_i \binom{a}{i+d}\binom{b}{b-i}=\sum_d \binom{a+b}{b+d}$ 暴力算就行了.

最后你需要用exlucas算组合数

P5279 [ZJOI2019] 麻将

dpofdp, 先考虑如何判定是否胡牌, 那么顺子这种性质肯定是扫值域, 从小到大, 设 $f_{i, j, 0/1}$ 表示前 $i$ 种牌, 形成 $j$ 个 $i, i-1$ 的对, 是否已经出现刻字, 转移显然, 可以对着转移建自动机.

发现节点并不对, $S\approx 2000$ 个

然后求期望可以累加前缀 $1\ldots i$ 加入之后还没胡的概率, 于是 $f_{i, j, k}$ 表示前 $i$ 种牌, 一共加入了 $j$ 张牌, 走到自动机的节点 $k$ 的期望步数.

转移是枚举当前种牌加了多少张, 复杂度是 $n^2S$ 的.

P3307 [SDOI2013] 项链

先数珠子有几种, 正三棱柱的置换包括3种, 横着转一/二下和左右翻转, 只要数互质数对个数, 莫反板子.

然后数项链是模板ploya吧?

P4916 [MtOI2018] 魔力环

先上一套burnside, 现在变成要求对每个 $d$, 设 $l=gcd(d, n)$, 求 $f_l$ 表示长 $l$ 的环(不可旋转), 有 $\dfrac{mn}{l}$ 个黑色珠子, 不能连续出 $k$ 个黑色的方案数.

先把白色放好开始插入黑色, 枚举插入的空隙数, 设黑色个数为 $b$, 得到

$$
\sum_i \binom{l-b}{i}g(b, i)
$$
于是求 $g(n, c)$ 表示把 $n$ 个不区分的球分成 $c$ 个区分的盒子每份大小不超过 $k$ 的方案数, 于是

$$
g(n, c)=x^n^c=(1-x^{k+1})^c(1-x)^{-c}=(\sum_i \binom{c}{i}x^{ik+i})(\sum_i \binom{c+i-1}{i}x^i)
$$

于是可以 $\dfrac{n}{k}$ 算一项, 而枚举插入的空隙数是 $O(k)$ 的, 所以算一次是 $O(m)$, 于是算所有 $f$ 的复杂度是关于 $n$ 约数和线性, 而约数和最大是 $n\log n$ 的(根号为界分开分析), 于是总复杂度是单log的.

[ARC120F] Wine Thief

考虑对每个元素计算贡献, 要算挖去一个区间后两边选 $k-1$ 个元素的方案数. 是两边的方案卷起来, 不可做.

考虑设从 $n$ 个中选 $i$ 个且满足限制的方案数为 $f_{n, i}$, 从 $n$ 个中选 $i$ 个且第 $j$ 个强制选的方案数为 $g_{n, i, j}$, 则对于 $i\in [D, n-D+1]$, $g_{n, i, j}$ 就是先选一个 $j$, 然后要求 $[j-D+1, j+D-1]$ 这块不能选, 相当于挖掉这块添加一个长 $d$ 的空段(使得两边互不影响), 那么你不能选到空段上, 于是 $g_{n, i, j}=f_{n-D, i-1}-\sum_{k\in [i, i+D-1]} g_{n-D, i-1, k}$.

这可以看成卷积: $G_{n, i}(x)=\sum_j x^j g_{n, i, j}$, 则 $G_{n, i}=\dfrac{1}{1-x}f_{n-D, i-1}-G_{n-D, i-1}*(\sum_{j=0}^d -x^{-j})$

而初始状态应该是 $G_{n-kD, 0}=0$, 每次区间加并卷上一个平移的多项式, 对于变换 $m$ 次的多项式, 发现满足性质前 $mD项和后mD项对称相等而中间全部相等, 于是直接卷起来复杂度就从$ n^2\log n\log k $变为$ n\log n\log k $

P4500 [ZJOI2018] 树

考虑要求$ \sum_{a\in A} s^k(a)$, 其中$ s(a)$为$ a $这一无根树对应有标号树个数, 则要设出乘法/加法复合意义的GF, 设$ a $的GF为$ F_k(a)=\dfrac{s(a)^k x^{\vert a\vert}}{(\vert a\vert! )^k} $, 容易发现满足条件, 而一个组合类的GF自然是$ F_k(A)=\sum F_k(a)=\sum_i \dfrac{f_ix^i}{(i! )^k} $.

则现在建立树形方程, 有$ \mathrm{xD}F=\mathrm{MSET} F $, 其中$ \mathrm{xD}, \mathrm{MSET} $分别是使组合类大小减少$ 1 $和多重集构造.

考虑推出这个特殊GF的$ \mathrm{MSET} $, 则显然是

$$
\begin{gathered}
\mathrm{MSET}(A)
=\prod_{a\in A} \sum_{i=0} \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(i! )^k(\vert a\vert! )^i}
=\exp \sum_{a\in A} \ln \sum_{i=0} \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(i! )^k(\vert a\vert! )^i}\
let\ G(x)
=\ln \sum_{i=1} \dfrac{x^i}{(i! )^k}
\
\mathrm{MSET}(A)
=\exp \sum_a G(\dfrac{s(a)^{k}x^{\vert a\vert}}{(\vert a\vert! )})\
=\exp \sum_a \sum_{i=1} g_i \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(\vert a\vert! )^i}\
=\exp \sum_{i=1} g_i \sum_a \dfrac{s(a)^{ki}x^{\vert a\vert i}}{(\vert a\vert! )^i}\
=\exp \sum_{i=1} g_i F_{ki}(x^i)
\end{gathered}
$$

于是有

$$
\mathrm{xD} F=\exp \sum_{i=1} g_{i} F(x^i)\
\ln (\mathrm{xD} F)-g_1F(x)=\exp \sum_{i=2} g_{i} F_{ki}(x^i)
$$

于是可以提取系数递推了,$ F_i $从大到小推, 则推$ F_{i} $时,$ F $只用推到第$ \dfrac ni $项, 于是等号左边推$ \exp $和右边算$ \ln $得到$ g $的复杂度是$ \sum_i \dfrac{n^2}{i^2}=O(n^2)$, 而右边的求和只求$ \sum_i \dfrac{n}{i}\ln \dfrac{n}{i}=n\ln^2 n $项即可.

总复杂度$ n^2 $

重点应该是构造满足乘法性质的特殊GF并整出对应运算.

[ARC154F] Dice Game

应该想到叶开WC的论文选讲!

列GF,设$F(x)$为$PGF$,所求即$F(e^x)$,$F(x)$应该枚举最后一次是几得到,除了最后这次其他的元素用EGF分配时间轴上标号,$L$为拉普拉斯变换:

$$
\begin{gathered}
F(x)=L(x(e^{\frac{x}{n}}-1)^{n-1})\
=L\left(
\sum_{i=0} \binom{n-1}{i}(-1)^ix\exp(\frac{ix}{n})
\right)\
\because L(x\exp(\frac{ix}{n}))=L\left(\sum_{j=0} (\dfrac{i}{n})^j\dfrac{x^{j+1}}{j!}\right)\
=\sum_{j=0} (\dfrac{i}{n})^j(j+1)x^{j+1}\
=\dfrac{n}{i}\sum_{j=1}j(\dfrac{ix}{n})^j\
=\dfrac{nx}{i(1-\dfrac{ix}{n})^2}\
\therefore
F(x)=\sum_{i=0} \binom{n-1}{i}(-1)^i\dfrac{nx}{i(1-\dfrac{ix}{n})^2}
\end{gathered}
$$

我们要求$F(e^x)$,这里不能先求$F$再复合$e^x$因为$F$其实是无限项$H/G$的形式,$e^x$有常数项$1$使得后面的项有贡献,应该先求$H$和$G$,分别复合之后再求逆.

先求$F$的话,可以考虑求$F(x+1)$的系数,复合$e^x-1$,就没有刚才的问题了.

复合$e^x$怎么做?

$$
F(e^x)=\sum_{i=0} f_ie^{ix}=\sum_i f_i\sum_{j=0} \dfrac{(ix)^j}{j!}
$$

$j!$可以最后除,去掉之后就简单了:

$$
\sum_i f_i\sum_{j=0}(ix)^j=\sum_i \dfrac{f_i}{1-ix}
$$

分治FFT!