nfls 2024.1.3 专题训练：计数与数学-526互联

似乎有一个引理是越往后越没意思。

F. UOJ450/LOJ6696 复读机/复读机加强版

多项式基础烂到家了。

群里有 $k$ 个不同的复读机。为了庆祝平安夜的到来，在接下来的 $n$ 秒内，它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是，一个复读机只有总共复读了 $d$ 的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐。模数 $19491001$。

数据范围：$1\le n\le 10^9, d, k\ge 1$。

原题：

$d = 2, k\le 5\times 10^5$。

$d = 3, k\le 1000$。

加强版：

$d = 4, k\le 2000$。

$d = 6, k\le 1000$。

首先表示出答案：

\[\begin{aligned} F(z) &= \sum\limits_{i=0}^{\infty}[d|i]\frac{z^{i}}{i!}\\ Ans &= n![z^{n}](F(z))^k \end{aligned} \]

考虑使用单位根反演处理整除，则：

\[F(z) = \sum\limits_{i=0}^{\infty}\frac{z^{i}}{i!\cdot d}\sum\limits_{j=0}^{d-1}\omega_d^{ij}=\frac{1}{d}\sum\limits_{j=0}^{d-1}\sum\limits_{i=0}^{\infty}\frac{z^i\omega_d^{ij}}{i!}=\frac{1}{d}\sum\limits_{j=0}^{d-1}\exp(\omega_d^j\cdot z) \]

注意到 $19491001 = 2^3\times 3\times 5^3\times 73\times 89+1$，所以不需要扩域，$2,3,4,6$ 阶单位根均存在。

对于原题，我们已经有了做法，直接使用二项式定理 $\Theta(k^{d-1})$ 统计答案即可。

对于加强版，展开 $(F(z))^k$，容易发现由于单位根的性质，结果的每一项都形如 $\exp(z(\sum\limits_{j=0}^{d-1}c_j\omega_d^j))$。考虑如何更高效地表示它。注意到 $d$ 次单位根可以表示为其中的 $\varphi(d)$ 项的线性组合。利用这个性质，以及 $\varphi(4) = \varphi(6) = 2$，我们可以化简上式，也即：

\[(F(z))^k = \sum p_{a, b}\exp((a\omega_d^1+b)z) \]

注意到 $|a|, |b|\le k$，实际上这个多项式具有 $k^2$ 项，如果能递推计算出其中每一项的系数，就能快速求得答案。考虑设 $G(x, y) = \sum\limits_{j=0}^{d-1} x^{a_j}y^{b_j}$，其中 $a, b$ 分别表示 $\omega_d^j$ 拆解成 $\omega_d^1 $ 和 $\omega_d^0 = 1$ 的线性表示产生的系数。则只需要求 $G(x, y)$ 的 $k$ 次幂。通过一些指数平移，我们可以让 $G$ 的次数为非负。它的 $k$ 次幂的每一项系数可以用微分有限在 $\Theta(k^2d)$ 时间内求得。

\[\begin{aligned} H(x, y) &= (G(x, y))^k \\ (\frac{\partial}{\partial x} H(x,y))G(x,y) &= kH(x, y)(\frac{\partial}{\partial x}G(x, y))\\ \sum\limits_{j=0}^{d-1} [x^{p-a_j}y^{q-b_j}](\frac{\partial}{\partial x} H(x,y)) &= k\sum\limits_{j=0}^{d-1}a_j[x^{p-a_j+1}y^{q-b_j}]H(x,y)\\ \sum\limits_{j=0}^{d-1}(p-a_j+1)[x^{p-a_j+1}y^{q-b_j}]H(x,y) &= k\sum\limits_{j=0}^{d-1}a_j[x^{p-a_j+1}y^{q-b_j}]H(x,y) \end{aligned} \]

注意到左侧有 $x^{p+1}$ 的项（系数 $p-a_j+1 = p + 1\neq 0$），而右侧没有（系数 $a_j$ 为 $0$），所以可以递推。

H. QOJ4916/LOJ3653 抽奖机

奆$\mathscr{L}$ 有一个神秘的抽奖机，它由 $n$ 个转轮组成。

每个转轮有三个档位，记作$0,1,2$，转轮的转动与档位关系如下：

当一个$0$档位转轮被转过一次，会变成$1$档位

当一个$1$档位转轮被转过一次，会变成$2$档位

当一个$2$档位转轮被转过一次，会变成$0$档位

一开始所有 $n$ 个转轮都在0档，将所有转轮的集合记作 $S$。

抽奖机的抽奖器有 $m$ 个模式，每个模式可以用两个数字 $a_i,b_i$ 描述，表示：

将$S$分为三个集合$A,B,C$，即满足：

$A\cap B,A\cap B,B\cap C=\emptyset,A\cup B\cup C=S,|A|=a_i,|B|=b_i$

其中$|A|$表示集合$A$的大小，容易发现一共有$\cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$种分配集合的方法

然后将集合$A$中的转轮转动一次，所有集合$B$中的转轮转过两次

每次拉下摇杆，抽奖机都会进行转动，一次转动如下：

从所有模式里选取一个进行；

从所有可能的转动情况中选择一个进行。

最终，应该有$\displaystyle \sum_{i=1}^m \cfrac{n!}{a_i!b_i!(n-a_i-b_i)!}$种方案，在这样的所有方案中选择一个。

现在奆$\mathscr{L}$通过py手段得知了所有的模式，但是ta依然无法控制抽奖机的结果。

自暴自弃的ta决定连续乱拉$k$次拉杆，而并且在此之前，ta暴怒地逼问你：

最终抽奖机恰好有 $i$ 个转轮在 $1$ 档，$j$ 个转轮在 $2$ 档的方案数。

由于答案可能非常大，请输出其 $\mod 10^9+9$ 的结果。

考虑 $n$ 阶多项式 $F$，下标 $(i_1,i_2,\dots,i_n)$ 位置的值表示第一个位置移动了 $i_1$ 次，第二个位置 $i_2$ 次……的方案数（下标对 $3$ 取模）。那么我们要求的即是 $F^k$，这样我们拥有一个 $\Theta(n3^n)$ 做法。考虑高维 $DFT$，也即 $g$ 的下标 $(i_1,i_2,\dots,i_n)$ 位置表示 $\sum f_{j_1,j_2,\dots,j_n}\prod\limits_{k=1}^n\omega_3^{i_k\cdot j_k}$。

注意到 $f$ 的特定位置值只和下标中 $1, 2$ 的个数有关，也就是只有 $\Theta(n^2)$ 种本质不同的位置。由于一些对称性，我们认为 $g$ 也具有相同的性质（不予证明）。下面我们只要考虑从 $f_{a\times1, b\times 2}$ 转移到 $g_{c\times 1, d\times 2}$ 的转移系数。通过二元多项式 $(1+x+y)^{n-c-d}(1+\omega_3^1x+\omega_3^2y)^c(1+\omega_3^2x+\omega_3^1y)^d$，我们刻画了有 $n-c-d$ 个 $0$，$c$ 个 $1$ 和 $d$ 个$2$ 的位置，括号内的三个项分别表从原多项式在这个位置是 $0, 1, 2$ 的系数，则它的 $x^ay^b$ 项系数就是我们要求的结果。设多项式为 $T_{c,d}$，从 $T_{c-1,d}$ 可以乘上 $\frac{1+\omega_3^1x+\omega_3^2y}{1+x+y}$ 转移过来，则总复杂度是 $\Theta(n^4)$。

G. QOJ4889 愚蠢的在线法官

先写出题人做法，主要是想写一下 $\gcd$ 矩阵的技巧和 Cauthy-Binet 公式。后面的对称性视角也是很经典的。2021 集训队互测题解 (Remake) 中似乎有很简洁的想法。

给定一棵以 $1$ 为根的 $n$ 个点的树，点有点权 $v_i$。给定长度为 $k$ 的序列 $a$。矩阵 $M_{i,j} = v_{lca(i,j)}$，求 $\det M$ 对 $998244353$ 取模的结果。$1\le n, k\le 5\times 10^5$。

一个经典问题：给定 $n$，$n\times n$ 矩阵 $M$ 满足 $M_{i, j} = \gcd(i, j)$，求行列式。注意到 $\gcd(i, j) = \sum\limits_{k=1}^n[k|i][k|j]\varphi(k)$，因此可以将 $M$ 分解为 $AB$，其中 $A_{i, j} = [j|i]\varphi(j),B_{i, j} = [i|j]$。根据行列式的性质 $\det M = \det A\cdot \det B$，而 $A,B$ 都是三角矩阵，所以很容易求得答案 $\prod\limits_{i=1}^n\varphi(i)$。

我们发现 $lca$ 和 $\gcd$ 有着异曲同工之妙。首先考虑 $k=n$ 的部分分。注意到 $v_{lca(a, b)} = \sum [x\to a][x\to b](v_x-v_{fa_x})$，其中 $x\to a$ 表示 $x$ 是 $a$ 祖先，$v_{fa_1} = 0$。所以可以将 $M$ 拆分成 $AB$，其中 $A_{i,j} = [j\to i](v_j - v_{fa_j})$，$B_{i, j} = [i\to j]$，注意到两者同样都是三角矩阵（事实上这是偏序关系带来的性质），所以答案即 $\prod\limits_{i=1}^n(v_i-v_{fa_i})$。

接下来，考虑 $k < n$。此时的 $A, B$ 分别变成了 $k\times n, n\times k$ 的矩阵而非方阵，所以我们不能求出其行列式。考虑 Cauthy-Binet 公式：$\det M = \sum\limits_{S\subseteq \{1\dots n\}, |S| = k} \det A_{\{1\dots k\}, S}\cdot \det B_{S, \{1\dots k\}}$。其组合意义即，从所有 $n$ 个点中选出 $k$ 个特殊点，再将序列 $a$ 中的元素与之用两种方案两两匹配（分别表示 $A$ 和 $B$），匹配的权值是 $(-1)^\text{两种方案总逆序对数}$ 乘以所有特殊点的 $v_i-v_{fa_i}$。然而这个东西还是不太好做，所以考虑是否存在行列式带来的对称抵消。

注意到如果在一组方案中，存在至少一对特殊点 $u, v$，使得 $u$ 被 $u'$ 匹配，$v$ 被 $v'$ 匹配，且两者的匹配可以交换，那么我们选择字典序最小的那一对 $(u, v)$，将之交换，那么得到了权值相同，但是符号相反的另一组方案。注意到在新的方案中 $(u, v)$ 仍然是字典序最小的可交换对，所以这是一组逆序对数为奇数的可交换方案到逆序对数为偶数的可交换方案的双射，于是所有这些方案的贡献均为 $0$。于是我们只需要考虑不可交换的方案。

另一个结论是，如果存在某种不可交换方案，那么它对应的特殊点选择方法只有唯一的一种方案也就是当前这种。于是，在所有不可交换方案中，$A, B$ 中选择的匹配方式必然相同，所以总逆序对数必然为偶数，于是符号项无需考虑，只需要 DP 所有选择特殊点的方案，使得有唯一的一种匹配方法，求它们的权值。如果匹配方法唯一，那么从每个子树出来的匹配边最多只有一条，所以 DP 的复杂度是 $\Theta(n)$。

E. 分层图

不难。

给定 $L\times n$ 个节点的图，分成 $L$ 层，每层是 $n$ 个点的完全图，相邻两层之间的 $n$ 对点对应连边。求这张图的哈密顿回路数量。 $1\le L, n\le 500$。

首先可以将各层被访问到的节点按照访问时间排序，第一层的顺序是任意的，共 $(n-1)!$ 种。考虑第一层当中，共有 $n$ 次移动 $u \to v$，这些移动有一些是直接通过第一层中的边 $(u, v)$ 进行，还有一些是通过 $u\to u'\leadsto v'\to u$，也就是从 $u$ 走到第二层进行一系列转移以后，再走回到 $v$。假设有 $a$ 次转移通过第二种方式进行，则选择方法有 $2\dbinom{n-a}{a}-\dbinom{n-1-a}{a}$ 种，且这样会把第二层划分成 $a$ 段，每一段的开头、结尾都被固定，其它位置任选。我们不再需要考虑环形结构，每一段只有 $\text{长度} - 1$ 次转移。考虑确定第二层的分段方式和没有被固定的位置的排列顺序，接着从 $n-a$ 个转移中选择一些（假设 $b$ 个）传递到下一层。这个过程很容易使用 DP 维护（记 $f_{i, j}$）表示第 $i$ 层需要分成 $j$ 段，$i$ 层之前的层的方案数。我们只需要处理出 $g_{a, b}$ 表示当前层分为 $a$ 段，希望让下一层分为 $b$ 段的方案数（转移系数）即可做到 $\Theta(n^3)$。实际上这是这样一个问题：当前有 $a-1$ 个红球，$b$ 个蓝球，$(n-1)-(a-1)-b = n-a-b$ 个白球，要求把他们排成一行，红球不能和红球相邻，蓝球不能和蓝球相邻，答案即是 $g_{a,b}$。不能相邻的限制是比较难搞的，但是我们可以容斥钦定出现了若干个红球相邻，则相当于捆绑了一些红球，这样是 $n^3$ 的，我们只需要 $\Theta(1)$ 计算有若干个红球、白球，要求蓝球不能相邻的方案数，这个可以直接采用插板法，一个组合数解决。

A. CF1392I Kevin and Grid

不难但是非常恶俗，非常非常恶俗，非常非常非常恶俗。

题目太长，自行查看：Kevin and Grid - 洛谷。

考虑欧拉公式 $|V|+|F|-|E| = 1 + \text{连通块个数}$，我们稍微魔改一下，不算最外面那个面，那么等式右边就是连通块个数。注意题目要求完全在内部的连通块要算两遍，这个东西有点别扭。如果注意力比较集中就能发现，实际上可以将权值算成 $2 = 1 - (-1)$，也就是对于红色（温度高）连通块，如果它完全被包含在蓝色（温度低）连通块内，那么计算蓝色的 $|F|$ 的时候就不要计算对应的那个面，这样刚好是对的（这里已经非常恶俗了）。于是我们要算的是：

红色的格子数减掉蓝色的格子数
相邻的都是红色的格子数减掉都是蓝色的格子数
相邻的四个红色格子数减掉四个蓝色格子数

三个问题实际上有着相似的结构：给定若干组 $x$ 和两个序列 $A, B$，要求有多少对 $i, j$ 满足 $A_i + B_j \ge x$。考虑怎么解决。其实做法更加恶俗。注意到你其实希望 $x - A_i \le B_i$，而左边只有 $2\times10^5$ 种可能，直接枚举加二分求出 $x - A_i = t$ 时的答案 $f_t$，那么每一组询问你要求 $\sum\limits_{i=1}^n f_{x-A_i}$。记 $t_v = \sum\limits_{i=1}^n[A_i = v]$，则要求 $\sum\limits_{a+b=x}f_at_b$，NTT 一下即可。

B. Prefix Sum

怎么是牛客多校的题。没意思。

有 $k+1$ 个数组 $a_0\dots a_k$，其中 $a_0$ 是给定的，初始为全 $0$，$a_i$ 是 $a_{i-1}$ 的前缀和（$a_{i,j} = \sum\limits_{k=1}^j a_{i-1,k}$）。有两种操作：给 $a_{0,x}$ 单点加；求 $a_{k,x}$ 的值。对 $10^9+7$ 取模。

$1\le n, q\le 10^5, 1\le k\le 40$。

首先 $a_{k,i} = \sum\limits_{j=1}^n\dbinom{i-j+k}{k}a_{0,j} = \frac{1}{k!}\sum\limits_{j=1}^n\frac{(i-j+k)!}{(i-j)!}a_{0,j}$。有脑瘫第一时间想到了根号重构 FFT，这种人建议一辈子禁止看小圆。那么应该怎么做呢？注意到 $\frac{(i-j+k)!}{(i-j)!}$ 是关于 $i-j$ 的 $k$ 次多项式，枚举 $i$ 以后会得到这个 $i$ 对应一个 $j$ 的 $k$ 次多项式 $F_i(j)$，那么只需要对于所有 $0\le t\le k$ 维护 $a_{0,i}i^t$ 的前缀和即可，直接用树状数组复杂度 $\Theta(nk^2 + mk\log n)$。

D. CF1085G Beautiful Matrix

EZ。

一个 $n\times n$ 矩阵是好的当且仅当其值域是 $[1, n]\cap\mathbb Z$，每一行内的元素互不相同，每一列内直接相邻的元素互不相同，好的矩阵按照字典序排名（从 $0$ 开始）。给定一个好的矩阵，求它的排名 $\bmod 998244353$。$1\le n\le 2000$。

设 $f_{i,j}$ 表示有 $i$ 个位置，其中 $j$ 个有限制的错排方案数，非常容易 $n^2$ 递推求得。枚举位置 $(i, j)$ 使得在它之前（$x<i$ 或 $x=i, y<j$）的位置都和当前矩阵相等，且第 $(i, j)$ 位小于的方案数。容易对每个位置预处理出这一行后面的有限制位置个数，但是如果枚举当前位置的值就是 $n^3$ 了，注意到我们只关心当前位置填的数有没有在这一行后面出现过，于是分出现过和没出现过讨论一下，这里需要树状数组。时间复杂度 $\Theta(n^2\log n)$。