「学习总结」正睿 计数选讲
wzy哥哥的一些有趣计数题~
例题壹
给定 \(n, m\) ，构造 \(n\) 堆石子，每堆石子的数量 \(\in[1, 2^m-1]\)，每堆石子数目互不相同。求使得 Nim 先手必胜的构造方案数。
\(n\le 10^7, m\le 10^9\) 模数：\(10^9 + 7\)
考虑直接后手必胜的情况，即长度为 \(n\) 的序列，异或和为 \(0\)。
设长度为 \(n\) 的方案数为 \(f(n)\)。能够得到如下递推式： \[ f(n) = (2^m-1)(2^m-2)(2^m-3) \cdots(2^m - n+1)\\ -f(n - 1)\\ -(2^m-1)(i-1)f(n-2) \] 考虑到前 \((n-1)\) 位置个随意填上互不相同的值域为 \([1, 2^m-1]\) 的数字。然后减去前面正好填出异或和为 \(0\) 的方案（因为最后一个位置还要填数字）（即：\(f(n-1)\)）。理论上，最后一个数字应该等于前面 \((n - 1)\) 数字的异或和，但是可能不满足互不相同的条件，先枚举不合法的方案最后一个数字是什么，然后枚举和前面哪一个冲突，再乘上 \(f(n-2)\)。
例题贰
给出 \(n\) 个正整数 \(a_i\)，选出 \(n\) 个正整数 \(b_i\) ，\(n\) 个正整数 \(d_i\)，满足
\(\forall i \in [1, n], d_i|b_i|a_i\)，求有多少种选法满足 \(\prod_{i}^n d_i^2 \ge \prod_{i=1}^{n}b_i\)
\(n\le 100, a_i \le 10^9\)
对于任意一种方案 \(\prod_{i=1}^{n}d_i^2 > \prod_{i=1}^{n}b_i\)
试想把所有 \(d_i\) 取成 \(\frac{b_i}{d_i}\)，即： \(\prod_{i=1}^{n} \frac{b_i^2}{d_i^2} > \prod_{i=1}^{n}b_i\)
即： \(\prod_{i=1}^{n}d_i^2 < \prod_{i=1}^{n}b_i\)
所以其实 \(\prod_{i=1}^{n}d_i^2 < \prod_{i=1}^{n}b_i\) 和 \(\prod_{i=1}^{n}d_i^2 > \prod_{i=1}^{n}b_i\) 的方案是一一对应的。
只需要求出 \(\prod_{i=1}^{n}d_i^2=b_i\) 的方案数即可。这个可以对每一个质因子单独 dp。
例题叁
\(n\) 个位置排成一排,有 \(m\) 个人依次进场选位置,每个人一开始选一个方向,从左到右/从右到左,并选择一个位置,然后按照她选择的方向进入场地,走到这个位置,如果有人,就继续按当前方向往后寻找,知道找到一个空位坐下,如果没有空位,他就会生气.
为每个人确定一个方向和选择的位置。求没有人生气的方案数。
考虑把序列首尾之间连接一个点 \(n+1\) 转化成一个环，相当于每个人选择一个位置，然后选择一个方向转圈，方案不合法，当且仅当有一个人占据了 \(n+1\) 这个位置。
因为是一个环，所以任意一个位置都是等价的，所以任意一个位置有人的概率为 \((1 -\frac{m}{n+1})\)
答案就是 \((1 - \frac{m}{n + 1})2^m(n + 1) ^ m\)
例题肆
例题伍
例题陆
一棵树，每条边的两个端点的大小关系给出，形如 \(a_u > a_v\) 或者 \(a_u < a_v\)。求有多少种满足条件的排列 \(a\) 。 \(n \le 5000\)
例题柒
给定一个字符串 \(S\)，仅包含 < 和 > 两种字符。
你需要计算「使得 \(p_i < p_{i+1}\) 当且仅当 \(s_i\)为 < 的排列 \(p_1, p_2, \cdots p_{n+1}\) 」的数量。
可以发现，答案可能很大，因此你只要输出它对 \(998244353\) 取模的结果。
巧妙容斥。
先不考虑所有 > 的限制，只考虑 < 的限制，> 处的偏序关系任意，将一段 < 视为连续的一段，设每一连续的一段长度为 \(a_i\) ，这样的方案数就是 \(\frac{n!}{\prod_{i}a_i!}\)。
然后显然答案需要减去任意位置为 < 的情况，对这个 < 满足数量容斥即可。
考虑设 \(f(n)\) 表示只考虑前 \(n\) 个数字方案数。
考虑 \(f(n)\) 的答案和 \(f(n-1)\) 的答案的差别，枚举最后一段有多长即可。 \[ f(n) = \sum_{i=1}^{i-1}\frac{[S_j = '>']}{(i-j)!}f(i)(-1)^{cnt_{i-1}-cnt_{j}} \] 这东西可以分治 \(NTT\) 优化。
例题玐
\(n\) 阶 循环矩阵是一种形如： \[ A=\begin{bmatrix} a_0 & a_{n-1} &\cdots & a_2 & a_1\\ a_1 & a_{0} &a_{n-1} & & a_2\\ \vdots & a_1 &a_0 & \ddots & \vdots\\ a_{n-2} & &\ddots & \ddots & a_{n-1}\\ a_{n-1} & a_{n-2} &\cdots & a_1 & a_0 \end{bmatrix} \] 的矩阵。
设 \(f(x)=\sum_{i=0}^{n-1}a_ix^i\) 没必要拘泥于\(a_i\) 的下标，取第一行依次排开即可，是等价的。
则：\(\det(A)=\prod_{i=0}^{n-1}\limits{f(\omega_i)}\)
即 对于循环矩阵，有快速的求值方式。
LGV引理
在一张 DAG 上，给定 \(n\) 个起点 \(a_1,\cdots,a_n\) ，\(n\) 个终点 \(b_1,\cdots,b_n\)，求选出 \(n\) 条路径 \((a_i, b_i)\) 互不相交（不经过同一个点）的方案数。
设 \(f(a, b)\) 表示从 DAG 上从 \(a\) 走到 \(b\) 的方案数。
构造矩阵 \(C\), 满足 \(c_{a, b}=f(a, b)\)。
LGV引理指出，其方案数为： \[ \det(C) \] 考虑任意一个有交方案，都能够对应一种其他方案，对应奇偶排列，这些方案会被抵消。
栗题
\(\mathbb{Y}\) 轴正半轴上有 \(n\) 个点 \((0, a_1),(0, a_2), \cdots,(0, a_n)\)，他们每次可以向右或向下走一格，求最后分别走到 \((1, 0), (2, 0), \cdots, (n, 0)\) 的方案数。 \(n, a_i \le 10^6\)
考虑这里的从 \((0, a_i)\) 到 \((j, 0)\) 的方案数为 \(\dbinom{a_i + j}{j}\)
构造行列式为： \[ \begin{vmatrix} \dbinom{a_1+1}{1}&\cdots&\dbinom{a_1+n}{n}\\ \vdots & \ddots& \vdots\\ \dbinom{a_n+1}{1}&\cdots&\dbinom{a_n+n}{n} \end{vmatrix} \] 对于每一列 \(j\) 提出公因子 \(\frac{1}{j!}\)，得： \[ \frac{1}{1!\ 2!\cdots n!}\begin{vmatrix} (a_1+1)^{\underline{1}}&\cdots&(a_1+n)^{\underline{n}}\\ \vdots & \ddots& \vdots\\ (a_n+1)^{\underline{1}}&\cdots&(a_n+1)^{\underline{n}} \end{vmatrix} \] 对每一行 \(i\) 提出公因子 \((a_i+1)\) 得到： \[ \frac{(a_1+1)(a_2+1)\cdots(a_n+1)}{1!\ 2!\cdots n!} \begin{vmatrix} 1&\cdots&(a_1+n)^{\underline{n-1}}\\ \vdots & \ddots& \vdots\\ 1&\cdots&(a_n+1)^{\underline{n-1}} \end{vmatrix} \] 类似于归纳法的消元方法，注意到每一列都是一系列形式相同的关于 \(a_i\) 的多项式，考虑可以用前面的每一列来消这一列，使得这一列 \(i\) 只剩下第 \(i\) 次项。
最后能得到一个范德蒙行列式，形如： \[ F=\begin{vmatrix} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1} \\ \vdots & & &\ddots &\vdots\\ 1 & a_n & a_n^2 & \cdots & a_n^{n-1} \\ \end{vmatrix} \] 范德蒙行列式的值有如下结论： \[ \det(F)=\prod_{i < j}(a_j - a_i) \] 注意按照归纳法推导过程，不难发现其实应该会推导出一个 \(\alpha F\) 的形式，但是这里的 \(\alpha\) 的值为 \(1\) ，可以忽略。
可以考虑枚举差值 \(k\) ，计算有多少对数字差值为 \(k\)。
记 \(g_i\) 表示有多少 \(a\) 等于 \(i\)，构造 \(g_i\) 的生成函数 \(G(x)\)。
易知：\([x^k]\sum_{i=k}\limits{g_ig_{i-k}}\) 就是所求。复杂度为 \(\mathcal{O}(a_i \log a_i)\)。