省选准备?

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!

[ARC117E] Zero-Sum Ranges 2

考虑前缀和, 折线模型, 相等元素个数, dp扫序列不行自然扫值域, 则从上往下不断插入数, 插入规则是相等相邻的两个数之间必须插入至少一个, 设当前已经用了 $i$ 个数, 已经有 $j$ 对相等, 当前能插入的位置有 $k$ 个, 转移时这一层插入几个数 $c$, 则 $f_{i, j, k}\to f_{i+c, j+\binom{c}{2}, c-k-2}$($-2$ 是序列两端必须插入一个), 转移系数是 $c$ 个数放到 $k+2$ 个盒子中, 即 $\binom{c-1}{k+1}$.

然后这样求出的是所有值都在某条线上的, 于是按照 $\ge 0, <0$ 部分合并即可: $\sum_{i, j, k} f_{i, j, k}f_{2n-i, K-j, k-1}$

复杂度是 $n^5$

[ARC096E] Everything on It

$\ge 2$ 这个 $2$ 很小, 考虑容斥, 先容斥没有选恰好一次的数的方案数:

$$
f_n=\sum_c \binom{n}{c}(-1)^c \cdot 2^{2^{n-c}}\sum_i {c\brace i} 2^{(n-c)i}
$$

再容斥没有不选的

$$
\begin{gathered}
ans=\sum_k \binom{n}{k}f_k (-1)^{n-k} \
=\sum_{k=0}^n \binom{n}{k} (-1)^{n-k} \sum_{c=0}^k \binom{k}{c}(-1)^c \cdot 2^{2^{k-c}}\sum_{i=0}^c {c\brace i} 2^{(k-c)i}\
a=n-k+c\
ans=\sum_{a=0}^n (-1)^a \sum_{c=0}^a \binom{n}{a}\binom{a}{c}2^{2^{n-a}}\sum_{i=0}^c {c\brace i}2^{(n-a)i}\
=\sum_{a=0}^n(-1)^a2^{2^{n-a}}\binom{n}{a}\sum_{i=0}^n2^{(n-a)i}\sum_{c=i}^n\binom{a}{c}{c\brace i}
\end{gathered}
$$

注意 $\binom{a}{c}{c\brace i}$ 的组合意义, 即选择 $c$ 个元素再划分成 $i$ 组, 那么剩下的元素划分成一组, 再添加一个元素用来标识这个组, 即这个式子等于 ${a+1\brace c+1}$ 于是做完了.

[ARC119F] AtCoder Express 3

走的过程一定最多往回走一格切换颜色方便往后跳. 考虑已知划分的话怎么求最短路, 可以记录前 $i$ 个点中最后一个 $A/B$ 类点(包括自己)到起点距离 $d_0, d_1$, 设当前点为 $A$ 类, 若下个点为 $A$ 类则 $d_0’=d_0+1, d_1’=d_1$, 否则 $d_0’=\min(d_0, d_1+2), d_1’=\min(d_0+1, d_1+1)$. 于是dpofdp思想可以得到一个 $n^3$ 的状态: $f_{i, j, k, c}$ 表示填到第 $i$ 个位置, $d_0, d_1$ 和当前点颜色.

感觉可能这种题都跑dfa最小化能赢. 接下来两种走法, 一种是人脑出等价且更小的自动机, 一种是发现性质, 对于一个 $A$ 类点首先总有 $d_0\ge d_1-1$ 因为当前点是由这个 $B$ 点后一格格走的. 而如果 $d_1<d_0-2$, 那么以后一定直接用这个 $d_1$ 的B类点跳过去更好, 所以这样的都和 $d_=d_0-2$ 的等价, 于是就只有 $n^2$ 状态了.

后面这个分析感觉很像小N的独立集? 但是树上问题显然不能搞dfa.

P5206 [WC2019] 数树

好强的题.

想到容斥, 此时能想到对两棵树的集合容斥, 但系数不好确定, 不如对两棵树的边的交集大小容斥.

然后因为是交集求 $\sum_A\sum_B f(A\cap B)$, 我们希望有一种容斥是 $f(S)=\sum_{T\subseteq S} f(T)c(T)$.

[trick] $f(S)=\sum_{T\subseteq S}\sum_{P\subseteq T}f(P)(-1)^{\vert T\vert-\vert P\vert}$. 证明: $=\sum_{P\subseteq S} f(P)\sum_{T\supseteq P}(-1)^{\vert T\vert-\vert P\vert}
=\sum_{P\subseteq S} f(P)\sum_{i=0}^{\vert S\vert-\vert P\vert} \binom{\vert S\vert-\vert P\vert}{i}(-1)^i=f(S)$

有了这个的话会很好, 比如对于subtask3:

$$
\begin{gathered}
ans=\sum_A \sum_B \sum_{S\subseteq A\cap B}\sum_{T\subseteq S} (-1)^{\vert S\vert-\vert T\vert}y^{n-\vert T\vert}\
=\sum_S \sum_{T\subseteq S} y^{n-\vert T\vert}(-1)^{\vert S\vert-\vert T\vert}\sum_{A\supseteq S}\sum_{B\supseteq S}\
=\sum_S F(S)^2 \sum_{T\subseteq S} y^{n-\vert T\vert}(-1)^{\vert S\vert-\vert T\vert}\
=y^{n}\sum_S F(S)^2 y^{-\vert S\vert}\sum_{T\subseteq S} (-y)^{\vert S\vert-\vert T\vert}\
=y^{n}\sum_S F(S)^2 y^{-\vert S\vert}\sum_i \binom{\vert S\vert}{i}(-y)^{\vert S\vert-i}\
=y^{n}\sum_S F(S)^2 (\dfrac{1}{y}-1)^{\vert S\vert}\
let\ K=\dfrac{1}{y}-1\
ans=y^nn^{-4}K^{n}\sum_P K^{-\vert P\vert} n^{2\vert P\vert} \prod_i p_i^2
\end{gathered}
$$

$P$ 是枚举划分, 则大小为 $i$ 的集合贡献 $\dfrac{n^2}{K}i^i$(一个有 $i^{i-2}$ 种方式组成连通块), exp即可.

对Subtask2, 把上面的转化式子抄一份下来:

$$
ans=y^{n}\sum_{S\subseteq A} F(S) K^{\vert S\vert}\
=y^n K^nn^{-2}\sum_{P\subseteq P_A}K^{-\vert P\vert}n^{\vert P\vert}\prod_{p_i}p_i
$$

树上选连通块, 大小为 $i$ 的连通块贡献 $w=K^{-1}ni$. 考虑dpGF, 设考虑点 $u$ 子树, $u$ 所在连通块为 $i$ 的方案数为 $[x^i]H_u$(常数为 $0$)转移是 $H_u: =H_uH_v+KH_v’(1)H_u$(第一个是并入连通块, 第二个是这里断开乘上贡献), 对这个式子求导带入1得到:

$$
H_u’(1)=H_u’(1)H_v(1)+H_v’(1)H_u(1)+KH_v’(1)H_u’(1)
$$

答案只要用到 $H_1(1)$, 于是只要维护 $H’_u(1)$ 和 $H_u(1)$ 即可做到线性. 可以用来维护转移是GF, 最后要点值的dp.