WC 赛前训练日志 2

染色问题

给出一个$n$个点$m$条边无向图，求$k$染色方案数（相邻点异色）。

$n\le 10^5, m\le n+5$，复杂度与$k$无关。

染色 缩点

染色数是 NPC 的。注意到$m\le n+5$的条件。常规思路是理解为一棵树加上若干条非树边，但这并不能方便地处理染色问题。

问题转化：对于一条边$(u,v)$，设$f(u,v), g(u,v)$分别表示$u,v$同色和异色时边的权值。初始时$f(u,v) = 0, g(u,v) = 1$。图的权值是边权之积。那么问题转化为求所有染色情况下的图的权值之和。

对于度数为$1$点$u$，假设他连到了$v$，那么可以直接删掉它，最后答案乘上$k-1$。实际上，应该是答案乘上$(k-1)g(u,v) + f(u,v)$。

对于度数为$2$的点$u$，假设它分别连接了$x,y$，那么删掉$u$，加一条边$(x,y)$，有

• $f(x,y) = g(u,x)g(u,y)(k-1) + f(u,x)f(u,y)$。即分$u$与$x,y$同色和异色两种情况考虑。
• $g(x,y) = g(u,x)g(u,y)(k-2) + g(u,x)f(u,y) + f(u,x)g(u,y)$。即分三种情况考虑。

有一个小细节：如果删除$u$后$x,y$出现了重边，那么应该把两条边合并，权值则是$f$和$g$分别相乘。

这样图中就只剩下了$3$度及以上的点。即$3n'\le 2m'$。又因为$n+5\ge m$，可以得到$n'\le 10, m'\le 15$。

设新图为$G=(V,E)$，设$F(i,S)$表示用$i$种颜色对集合$S$中的点染色的方案数。则

$$F(i,S) = \sum_{T\subseteq S}F(i-1,S\setminus T)\prod_{(u\in T,v\notin T)\in E} g(u,v)\prod_{(u\in T, v\in T)\in E} f(u,v)$$

从而算出答案。

时间复杂度$O(n+m+n'm'3^{n'})$。

代码

The Journey of Geor Autumn

给出$n,k$，求有多少个$n$的排列$p$满足$\forall i\in[k+1,n]$，$p_i > \min_{1\le j\le k}p_{i-j}$。

$k, n\le 10^7$。

DP

枚举$1$在排列中出现的位置。显然它只能出现在$p_1,\ldots,p_k$中。假设$p_x=1$。

那么$p_x$左边的位置可以随便填。右边的位置则是个递归子问题。设$f_n$表示长度为$n$的排列的答案，因此

$$f_n = \sum_{x=1}^k {(n-1)}^{\underline{x-1}} f_{n-x}$$

变换一下可以得到

$$f_n = (n-1)! \sum_{x=1}^k \frac{f_{n-x}}{(n-x)!}$$

那么维护一下$\frac{f_i}{i!}$的前缀和即可$O(n)$计算。

代码

Sum of Log

给出$X,Y$，计算$\sum_{i=0}^X\sum_{j=[i=0]}^Y[i\&j=0]\lfloor\log_2(i+j)+1\rfloor$。$X,Y\le 10^9$。

DP 数位

即统计$i+j$的二进制位数。

设$f(i,S)$表示考虑到第$i$位（从高到低或者从低到高都行）的方案数，$g(i,S)$表示贡献和。

状态$S$包括：$X,Y$是否到达上界、当前的数字是否为$0$（是否有最高位的$1$）。

时间复杂度$O(2^3\log_2X)$。

代码

IOer

给出$u,v,m,n$，计算

$$[x^n]\prod_{i=1}^m\frac{1}{1-(ui+v)x}$$

$m\le 2\times 10^5, n\le 10^{18}$。

生成函数 组合意义

直接分治 NTT 没有用到$(ui+v)$的特殊形式。

这个组合意义做法是题解做法，感觉很反思维。

考虑我们要求的是

$$\sum_{t_1+\cdots + t_m = n}(u+v)^{t_1}(2u+v)^{t_2}\cdots (mu+v)^{t_m}$$

假装我们有理有据地想到：构造一个序列计数问题。

我们定义一个球具有编号和颜色两种属性：对于编号$< m$的球，有$u$种颜色可选。对于编号为$m$的球，有$u+v$种颜色可选。两个球不同当且仅当颜色或者编号不同。考虑

求长度为$n+m-1$的球的序列满足：

1. 编号在$[1,m-1]$中的球都有出现；
2. 设$p_i$表示编号为$i$的球第一次出现的位置，那么$\forall i<m$，有$p_{i-1} < p_i$。

的方案数。

枚举序列$p_1,\ldots,p_{m-1}$，那么$p_i$位置上的球有$u$种选法（编号被钦定了）。$[1,p_1)$只能放编号为$m$的球，因此有$(u+v)^{p_1-1}$种选法。$(p_1,p_2)$能放编号为$1$或者$m$的球，因此有$(2u+v)^{p_2-p_1-1}$种选法。推广得到，总方案数是

$$u^{m-1}\sum_p (u+v)^{p_1-1}(2u+v)^{p_2-p_1-1}\cdots(mu+v)^{n+m-1-p_{m-1}}$$

不妨设$p_0=0,p_m = n+m$。

设$d_i = p_i-1-p_{i-1}$，那么得到

$$u^{m-1}\sum_d (u+v)^{d_1}(2u+v)^{d_2}\cdots(mu+v)^{d_m}$$

那么我们只需要求出序列的方案数即可求出答案。

不妨去掉第二个条件。由于编号$<m$的球的可选颜色数都是$u$，因此可以看作等价。则

长度为$n+m-1$的球的序列满足：编号在$[1,m-1]$中的球都有出现

的方案数是

$$(m-1)!u^{m-1}\sum_d (u+v)^{d_1}(2u+v)^{d_2}\cdots(mu+v)^{d_m}$$

这个问题可以容斥：钦定有$i$个编号的球没出现，得到

$$\sum_{i=0}^{m-1}(-1)^i\binom{m-1}{i} ((m-i)u+v)^{n+m-1}$$

这样我们就得到了问题的答案。

Flip and Reverse

你有一个 01 串$s$，每次你可以选择$s$的一个子串$s[l,r]$满足$s[l,r]$中 01 出现的次数相等，然后将其反转并交换 01 字符（0 变 1，1 变 0）。求若干次操作最小化$s$的字典序，并输出这个新的$s$。

$|s| \le 5\times 10^5$。

折线图 贪心

01 序列通常可以理解为：

1. 括号序列
2. 折线图

使用折线图来理解，相当于每次我可以反转一段折线。

进一步，其实我们不关心折线图的形态，我们只关心每一层的上行和下行的折线数。

进一步，我们甚至不用区分是上行还是下行。也就是说，记$a_i$表示$i$和$i+1$之间的折线数。那么我们的问题转化成，优先往下走，要求走完所有折线，求路径。

可以局部贪心。

朴素策略：在每一步，如果能够往下走就走。

这个策略有个问题：如果上面存在未走的折线，而下面的折线数是 1（回不来），那么就走不完所有折线了。

所以特判一下，大于 1 或者上面已经走完了才走下面即可。

时间复杂度$O(|s|)$。

代码

Latin Square

给出一个$n\times n$的 Latin Square$A$：每一行每一列都是$n$的排列的矩阵。维护以下操作：

• 每一行循环左移 / 右移一位。
• 每一列循环上移 / 下移一位。
• 将每一行的排列取其逆元。
• 将每一列的排列取其逆元。

一个排列$p_1,\ldots,p_n$的逆元是指排列$q$使得$p_{q_i} = i$。

输出最终的矩阵。操作次数不超过$m$。

$n\le 10^3, m\le 10^5$。

矩阵 Latin Square

考虑排列的逆元：$q_{p_i} = i$。

不妨将矩阵映射为三维点：$A_{ij} \to (i,j,A_{i,j})$。

那么对行取逆元相当于：$(i,j,A_{i,j}) \to (i,A_{i,j},j)$。我们这个变换并不是原题目中的变换。严格来说，应该每一行再按照第二维坐标排序才行。但注意，我们维护的是三维空间的点集，不存在顺序的问题。

同理，对列取逆元相当于$(i,j,A_{i,j}) \to (A_{i,j},j,i)$。

也就是说，取逆元等价于坐标不同维度的交换。之后的部分就 trivial 了。

代码

珍珠

有$n$个$[1,d]$范围内的整数均匀随机变量。问满足以下条件的概率：

• 可以找出至少$m$个 pair，每个 pair 包含两个值相同的变量。

$n,m\le 10^9, d\le 10^5$。

CTS2019 生成函数

这题有个很迷的地方。先二项式反演再推 gf 可以很轻松，但直接推 gf 就会有一些高深步骤。

设$c_i$表示值为$i$的变量的个数。那么条件等价于$\sum_{i} \lfloor\frac{c_i}{2}\rfloor\ge m$。

变换一下得到$\sum_{i}c_i\bmod 2\le n- 2m$。也就是说出现次数为奇数的变量数$\le n-2m$。

于是我们设$f_k$表示出现次数为奇数的有$k$个的方案数。方案数除以$d^n$就是答案。

直接干

这玩意可以直接有

$$f_k = \binom{d}{k}n![x^n]\left(\frac{e^x-e^{-x}}{2}\right)^k\left(\frac{e^x+e^{-x}}{2}\right)^{d-k}$$

然后就会有一些 神必操作。这里就不复读了。

复读一个稍微好一点的。

考虑容斥，我们钦定$k$个数出现奇数次，其他的不做限制。那么有

$$\sum_{i\ge k}\binom{i}{k}f_i = \binom{d}{k}n![x^n]\left(\frac{e^x-e^{-x}}{2}\right)^ke^{d-k}$$

解释一下

序列$\{0,1,0,1,\ldots\}$即$a_i = \frac{1}{2}(1 - (-1)^i)$的 EGF 是$\frac{e^x-e^{-x}}{2}$，这个序列在$i$是奇数时值为$1$，否则为$0$。

$(\frac{e^x - e^{-x}}{2})^k$的含义是选$k$个数出现奇数次的方案数。其他数的方案数就是$e^{d-k}$。

因为是 EGF，得乘上一个$n!$表示系数。

不妨设$g_k = \sum_{i\ge k}\binom{i}{k} f_i$。那么$f$可以用$g$容斥（二项式反演）算出。

这玩意可以这么化简：

$$\begin{aligned} g_k &= \binom{d}{k}n![x^n]\left(\frac{e^x-e^{-x}}{2}\right)^ke^{(d-k)x} \\ &= 2^{-k}\binom{d}{k}n![x^n] \sum_{j=0}^k\binom{k}{j}(-1)^{k-j}e^{(2j-2k+d)x} \\ &= 2^{-k}\binom{d}{k}n!k!(-1)^k \sum_{j=0}^k\frac{(-1)^j}{j!} \frac{1}{(k-j)!} [x^n] e^{(2(j-k)+d)x} \\ &= 2^{-k}\binom{d}{k}n!k!(-1)^k \sum_{j=0}^k\frac{(-1)^j}{j!(k-j)!} \frac{(2(j-k)+d)^n}{n!} \\ &= 2^{-k}\binom{d}{k}n!k!(-1)^k \sum_{j=0}^k\frac{(-1)^j}{j!(k-j)!} \frac{(2(j-k)+d)^n}{n!} \end{aligned}$$

化简的方向就是，能提到前面去的就提到前面去。

把$j$和$k-j$相关的部分分开，可以做卷积。卷积的长度是$O(d)$的，故时间复杂度$O(d\log_2d)$。

树上游走

给定一颗$n$个点的树，每个点有点权$v_i$，你在点$S$开始随机游走。

当你离开一个点第二次的时候这个点就会消失，与其相连的所有边也会消失。

你每次会等概率地选择一个与当前所在节点有边相连的一个未消失节点并前往那个点。

如果不存在与当前所在节点有边相连的点，你就会停止随机游走并等于获取当前所在节点权值的分数。

求你获得分数的期望，对$998244353$取模。

$n\le 10^5, v_i\le 1000$。

DP 期望 分类讨论

以$S$为根。钦定最后走到的结点是$u$。

记$\deg u$表示结点$u$的度。

容易发现，与$u$相邻的结点都必须被删掉。因此$\deg u \le 2$，否则不可能停在$u$。

从$S$到$u$的简单路径上的点是必经点。由此我们可以按照结点访问顺序（DFS）刻画出 DP 状态。考虑到改变结点度的因素，设$f(u)$表示从$S$出发第一次到达$u$的概率。

$$\gdef\fa#1{\text{fa}({ #1 })} \gdef\son#1{\text{son}({ #1 })}$$

第一部分

设$p=\fa{u}$表示$u$的父节点。那么我们一定先到达$p$再到达$u$。从$p$到$u$，走$(p,u)$这条边的概率取决于$p$的度。为了方便转移，设$g(u)$表示删掉$p$并第一次到达$u$的概率。

第一种情况：到达$p$后直接到$u$：

$$P_1= \frac{g(p)}{\deg(p) - 1} + \frac{f(p)-g(p)}{\deg(p)}$$

第二种情况：到达$p$后，先走到$p$的儿子$v$（$v\ne u$），再走回来，再去$u$。这种情况，$p$必然会被删除。

$$P_2 = \frac{g(p)}{(\deg(p)-1)^2}\sum_{v\in \son{p},v\ne u}\frac{1}{\deg(v)} + \frac{f(p) - g(p)}{\deg(p)^2}\sum_{v\in \son{p},v\ne u}\frac{1}{\deg(v)}$$

第三种情况：到达$p$后，走到$p$某个儿子$v$（$v\ne u$）的子树中的某个结点$z$（$z\in \son{v}, z\ne v$），然后走回$p$。第二次到达$p$时，$\deg(p)$会发生变化，因为$v$会被删除。这种情况下，$p$也会被删除。

不妨设$v$到$z$简单路径上的点顺次构成序列$a_1,\ldots, a_k$（$a_k = z$）。那么可以发现除了$a_k$，其他结点都会被删。因此$a$的贡献是

$$w(a) = \frac{1}{\deg(a_{k-1})^2\deg(a_k)} \prod_{i=1}^{k-2}\frac{1}{(\deg(a_i)-1)\deg(a_i)}$$

于是

$$P_3 = \frac{g(p)}{(\deg(p)-1)(\deg(p)-2)}\sum_{a:a_k = z} w(a) + \frac{f(p) - g(p)}{\deg(p)(\deg(p)-1)}\sum_{a:a_k = z} w(a)$$

第四种情况：要删除$p$，还有一个走法：$\fa{p} \to p \to \fa{p} \to p \to u$。这个走法会同时删除$\fa{p}$和$p$：

$$P_4 = \frac{g(\fa{p})}{(\deg(\fa{p}) -1)^2\deg(p)(\deg(p)-1)} + \frac{f(\fa{p}) - g(\fa{p})}{\deg(\fa{p})^2\deg(p)(\deg(p)-1)}$$

因此有

$$\begin{aligned} g(u) &= P_2 + P_3 + P_4 \\ f(u) &= P_1 + P_2 + P_3 + P_4 \end{aligned}$$

注意：$f(S) = 1, g(S) = 0$。这很好理解，因为$S$没有父节点，因此不存在「删掉$S$的父节点」这样的操作。

第二部分

考虑统计答案。

首先，要能最终停在$u$的条件是$\deg(u)\le 2$。

我们必须要删掉$\fa{u}$或者$u$没有父节点才能保证停在$u$。

第一种情况：在第一次到达$u$时删掉$\fa{u}$：

如果$u$是个叶子结点（此时必然有$u\ne S$），那么对答案的贡献就是$g(u)v_u$。

如果$u$是个只有一个儿子$v$的结点，那么我们可以模仿第三种情况的 DP 转移，先删掉$\fa{u}$走到$u$，再走到$v$子树里的结点$z$（$z\ne v$）再走回$u$，以删除$v$。这部分的贡献是

$$v_u\left(\frac{g(u)}{\deg(u)-1} + [u=S]\frac{f(u)}{\deg(u)} \right) \sum_{a: a_k = z}w(a)$$

第二种情况：在第二次到达$u$时删掉$\fa{u}$。

这种情况适用于$u$是叶子结点，那么我们第一次到达$p$后一定会走$p\to u\to p\to u$的路线。因此贡献为

$$v_u \left( \frac{g(p)}{(\deg(p)-1)^2} + \frac{f(p) - g(p)}{\deg(p)^2} \right)$$

代码

树的同构

给出一个$n$个点的树，要求找到两个同构的不相交的连通块，求连通块最大大小。

$n\le 51$。

枚举一个点$x$，则$x$和$x$父亲的边将这棵树分成两个部分。然后选一个不在$x$子树里的点$y$，做为另一个部分的根。这样就可以树形 DP 了。$f(i,j)$表示$i$和$j$的子树的最大同构连通块，且$i$和$j$匹配。

转移是个二分图最大权匹配。用 KM 算法做就行。

这题的一个难点是算复杂度。

考虑$f(i,j)$这个状态被计算的次数，复杂度为

$$\sum_{i}\sum_j n \text{dist}(i,j) (d_i + d_j)^3 \\$$

我也不知道为啥它是$O(n^5)$。但既然题解这么说了那就是吧。

移球游戏

有$n+1$个柱子，每个柱子上有$m$个位置。第$1$到$n$个柱子上放满了球，颜色为$i$的球有$m$个，总共$n\times m$个球。

每次你可以把一个柱子顶端的球移到另一个柱子顶端，前提是目标柱子有空位。

要求在$8.2\times 10^5$步内将每种颜色的球各自集中到一个柱子上。

$n\le 50, m\le 400$。

首先，这东西可以桶排。

直接桶排不太行。考虑分治。

将颜色小于$mid$的记为$0$，否则记为$1$。那么我们每一轮，对于当前区间柱子，干两件事：

• 对于每个柱子，把它变成$00\cdots011\cdots 1$或$11\cdots100\cdots 0$的形式。
• 把每个柱子两两合并，最终变成全$0$或全$1$的形式。

这两个都可以简单操作得到。

操作一就不说了。对于操作二，我的方法是：对于$000111$和$111000$两个柱子的合并可以做到$O(3m)$，对于两个$000111$的柱子，把其中一个反转一下就行。

这样的步数是大概是$5n\log_2nm$的。

代码