组合数
定义：\(\begin{pmatrix}n\\m\end{pmatrix}\) 表示 \(n\) 元集的 \(m\) 元子集个数。
通项
考虑其组合意义：
把所有 \(n!\) 个排列的前 \(m\) 个元素作为选出集合，每个集合被计算 \(m!(n - m)!\) 次。
二项式定理
组合意义：从 \(n\) 个括号里选出 \(i\) 个给 \(x\)，剩下给 \(y\)。
因此第 \(n\) 行组合数的普通生成函数 \(F_n(x)\) 的封闭形式为：
组合数的对称性
组合数的吸收公式
递推公式
组合意义就是讨论第 \(n\) 个元素是不是选出的第 \(m\) 个元素。
从生成函数的角度理解：\(F_n(x) = (x + 1) F_{n - 1}(x)\)，对比系数得到递推公式。
组合数的行和
组合数的列和
把和式中第一个非零项 \(\begin{pmatrix}m\\m\end{pmatrix}\) 看作 \(\begin{pmatrix}m + 1\\m + 1\end{pmatrix}\)。
- \(\binom{m + 1}{m + 1} + \binom{m + 1}{m} = \binom{m + 2}{m + 1}\)。
- \(\binom{m + 2}{m + 1} + \binom{m + 2}{m} = \binom{m + 3}{m + 1}\)。
以此类推得到 \(\begin{pmatrix}n\\m + 1\end{pmatrix} + \begin{pmatrix}n\\m\end{pmatrix} = \begin{pmatrix}n + 1\\m + 1\end{pmatrix} \)。
范德蒙德卷积
把 \(n + m\) 元集拆成一个 \(n\) 元集和一个 \(m\) 元集。
枚举 \(n + m\) 里面选 \(k\) 个出来的所有方案与这个 \(n\) 元集的交集 \(i\)，组合意义显然。
一个很有用的公式
\(n\) 个里面选 \(m\) 个，再在 \(m\) 个里面选 \(r\) 个。
等价于 \(n\) 个里面选 \(r\) 个，在剩下的 \(n - r\) 个里再选 \(m - r\) 个。
容斥原理
考虑每个元素在右式被计算几次。
如果一个元素在 \(k\) 个 \(S_i\) 中出现，那么他会被计算 \(\sum_{i = 1}^k(-1)^{i - 1}\begin{pmatrix}k\\i\end{pmatrix} = [k\ne 0]\)。
因此左边等于右边。
很多情况下要求同时满足 \(n\) 个条件的集合大小。
记 \(S_i\) 为不满足第 \(i\) 个条件的集合，那么答案即 \(\vert U\vert - \vert \bigcup_{i = 1}^n S_i\vert\)。
无限制的格路计数
题意：给定 \(n, m \ge 0\)，你一开始在原点，每次可以从 \((x,y)\) 走到 \((x + 1, y + 1)\) 或 \((x + 1, y - 1)\)，问走到 \((n, m)\) 的合法方案数。
设往右上走了 \(t\) 步，则往右下走了 \(n - t\) 步。
解方程 \(t - (n - t) = m\)，\(t = \dfrac{n + m}{2}\)。
如果 \(2 \not\mid n + m\)，那么方案数为 \(0\)，否则方案数为 \(\begin{pmatrix}n\\ \frac{n + m}{2}\end{pmatrix}\)。
从生成函数的角度理解，次数代表纵坐标：
反射容斥
例1：给定 \(n, m \ge 0\) 以及 \(p < 0\)，你一开始在原点，每次可以从 \((x,y)\) 走到 \((x + 1, y + 1)\) 或 \((x + 1, y - 1)\)，
问不经过直线 \(y = p\) 上的点走到 \((n, m)\) 的合法方案数。
考虑用上个模型的方案数减去经过 \(y = p\) 的方案数。
对于一个经过 \(y = p\) 的方案，我们将 \(p\) 上方的路径折下来，得到一条 \((0, 2p)\) 到 \((n, m)\) 的路径，任意新路径都能翻回去，因此这是一个双射。
则合法方案数等于 \(\begin{pmatrix}n\\\frac{n + m}{2}\end{pmatrix} - \begin{pmatrix}n\\\frac{n + m - 2p}{2}\end{pmatrix}\)。
例2：给定 \(n, m \ge 0\) 以及 \(p < 0,\ q > m\)，你一开始在原点，每次可以从 \((x,y)\) 走到 \((x + 1, y + 1)\) 或 \((x + 1, y - 1)\)，
问不经过直线 \(y = p\) 和 \(y = q\) 上的点走到 \((n, m)\) 的合法方案数。
还是用总方案减去不合法的方案，问题转化为经过 \(y = p\) 或 \(y = q\) 走到终点的方案数。
对于一条路径，如果经过 \(y = p\) 就写 'A'，经过 \(y = q\) 就写 'B'，如图路径写成 "BBBBAAB"。
把连续相同字符缩成一个，即 "BAB"。
每个路径都可以映射成一个字符串，字符串 “AB” 表示一条先经过 \(y = p\) 再经过 \(y = q\) 的路径，且没有其他地方与限制相交。
钦定先经过 \(y = p\) 再经过 \(y = q\) 的方案如何求？先将起点延 \(y = p\) 翻折转化为只有一条限制的情况，再延 \(y = q\) 翻折。
恰好呢？考虑上述计算方式会多计算哪些情况？
所谓 "AB"，我们在计算过程中并不关心 "A" 前面有没有 "B" 以及 "B" 后面有没有 "A", "AB", "ABA"...。
也就是说，"BAB", "BABA"... 和 "ABA", "ABAB"... 都会在计算 "AB" 时被算到。
如何构造容斥系数使得每种非法情况（"A", "B", "AB", "BA", "ABA"...）最后计算次数恰好为 \(-1\)。
从另一个角度考虑重复计算，如果 \(T\) 是 \(S\) 的子串，那么 \(S\) 的所有路径会在计算 \(T\) 时恰好被算一次。
对于字符串 "ABABA"，其本质不同子串有 "A", "AB", "ABA", "ABAB", "ABABA", "B", "BA", "BAB", "BABA"。共 \(2\vert S \vert - 1\) 个。
我们知道 \(\sum_{i = 1}^{2\vert S\vert -1}(-1)^{i} = -1\)，因此把每种字符串的容斥系数定为 \((-1)^{\vert S\vert}\) 可以恰好满足条件。
由于每增加一个字符，横坐标就要增加至少 \(q - p\) 的长度，需要考虑的字符串只有 \(O(\dfrac{n}{q - p})\)（不考虑从原点第一次到限制的距离，反正就是很少）。
卡特兰数
定义：第 \(n \ge 0\) 项卡特兰数 \(C_n\) 表示长度为 \(2n\) 的合法括号序列数。
通项
用反射容斥解释这个式子。
左括号表示 \((x, y) \to (x + 1, y + 1)\)，右括号表示 \((x, y) \to (x + 1, y - 1)\)，卡特兰数等于 \((0, 0)\) 走到 \((2n, 0)\) 不经过 \(y = -1\) 的路径数。
这样映射满足了合法括号序列的充要条件：左括号 = 右括号；任意前缀左括号不小于右括号。
递推式
枚举第一个右括号之间有多少括号对：
通过递推式解得卡特兰数的生成函数
子集反演
只考虑第一个式子，第二个类似。
从左推右：
记 \(h(S) = \sum_{T \subseteq S} (-1)^{\vert S\vert - \vert T\vert}\)。
带回原式：
从右推左：
二项式反演
引入
错排问题：\(n\) 个人排列。第 \(i\) 个人不能在位置 \(i\)，求合法排列数。
钦定 \(k\) 个人在自己位置上：
定义 \(f(n)\) 为 \(n\) 个人的排列数，\(g(n)\) 为 \(n\) 个人的错排数。
问题在于 \(f\) 能够快速计算，如何通过 \(f\) 反求 \(g\)。
有组合恒等式
说一句废话：
把 \([n - m = 0]\) 用上面的恒等式带掉：
公式
可以理解为 \(g(S)\) 只与 \(\vert S\vert\) 相关的子集反演。
实际应用中一般用第二种形式，\(f(n)\) 表示钦定 \(n\) 个的方案数，\(g(n)\) 表示恰好 \(n\) 个的方案数。
莫比乌斯反演
引入
周期问题：求长度为 \(n\) 的字符串且周期（最小循环节）恰为 \(n\) 的字符串个数，仅包含小写字母。
定义 \(f(n)\) 为长度为 \(n\) 的字符串个数，\(g(n)\) 为长度为 \(n\) 且周期恰为 \(n\) 的方案数。
显然有 \(f(n) = 26^n\)，怎么反求 \(g\)？
设函数 \(\mu\) 满足
构造一句废话然后代入：
公式
从子集反演的角度理解这个公式。
把每个数 \(x\) 映射成一个无限长的向量，第 \(i\) 为表示正整数中第 \(i\) 个质数在 \(x\) 中的次数。
整除关系即集合之间的包含关系。
现在目的是从 \(f(n)\) 里面减掉没有顶满（因子）的方案数。
只容斥与原数高度相差 \(1\) 的因子，减掉所有的 \(f(\dfrac{n}{p_i})\)，加上所有 \(f(\dfrac{n}{p_ip_j})\)，以此类推。
这同时也与 \(\mu\) 函数对应：存在平方因子（差两格）则为 \(0\)；否则为 \(-1\) 的质因子个数次方。
第二类斯特林数
\(\begin{Bmatrix}n\\m\end{Bmatrix}\) 表示把 \(n\) 元集划分为 \(m\) 个互不区分的非空集合的方案数。
通项公式
先假定 \(m\) 个集合互相区分，最后除以 \(m!\)。
钦定部分集合为空，然后容斥。
递推式
考虑最后一个元素 \(n\) 扔到哪里。
选一个现有集合扔进去（虽然集合互不区分，但是元素互不相同）；新增一个集合。
普通幂转下降幂
\(x^n\) 表示 \(n\) 个元素分配给互相区分的 \(x\) 个集合的方案数。
选出 \(i\) 个集合，\(n\) 个元素分出 \(i\) 个非空集合的方案是 \(s(n, i)\)，由于集合不区分，再乘一个 \(i!\)。
单位根反演
单位根：\(x^n = 1\) 在复平面上的 \(n\) 个解，其中 \(w_{n}^k = e^{i\frac{2k\pi}{n}}\)。
当 \(n \mid k\) 时，\(w_{n}^{ik} = 1\)，右式等于 \(1\)。
否则右边是一个等比数列，等于 \(\dfrac{1}{n}\times \dfrac{1 - w_{n}^{nk}}{1 - w_{n}^k} = 0\)。
用于模意义下的原根也是对的。
min-max 容斥
以第一种形式为例，第 \(k\) 小的元素被计算的次数等于：
实际应用一般结合期望，也就是如果一个集合的期望最小不好求，可以去求他的期望最大。
高维前缀和
二维前缀和：
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= n; ++ j) {a[i][j] += a[i - 1][j];}
}
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= n; ++ j) {a[i][j] += a[i][j - 1];}
}
三维前缀和：
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= n; ++ j) {for(int k = 1; k <= n; ++ k) {a[i][j][k] += a[i - 1][j][k];}}
}
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= n; ++ j) {for(int k = 1; k <= n; ++ k) {a[i][j][k] += a[i][j - 1][k];}}
}
for(int i = 1; i <= n; ++ i) {for(int j = 1; j <= n; ++ j) {for(int k = 1; k <= n; ++ k) {a[i][j][k] += a[i][j][k - 1];}}
}
子集和：
用偏序的形式表示子集和，可以发现他就是一个 \(n\) 维，每个维度只有 01 的前缀和。
for(int i = 0; i < n; ++ i) { // 枚举维度，1011 用数组表示为 a[1][1][0][1]for(int s = 0; s < 1 << n; ++ s) {if(s >> i & 1) a[s] += a[s ^ 1 << i];}
}
子集和还有分治做法。
对于一个 \([0, 2^n)\) 的序列，每次把他分成两部分 \([0, 2^{n - 1})[2^{n - 1}, 2^n)\)。
递归处理每个数在各自分治区间的子集和。
考虑合并两部分信息。
右边部分的第 \(n - 1\) 位都是 \(1\)，左边部分的第 \(n - 1\) 位都是 \(0\)，对应位呈现包含关系（\(x\) 对应 \(x + 2^{n - 1}\)）。
因此右边再加上左半边对应的贡献就可求得当前分治区间的子集和。
时间复杂度 \(T(2^n) = 2T(2^{n - 1}) + O(2^n) = O(n2^n)\)。
快速莫比乌斯变换
集合幂级数 \(F(x)\) 的莫比乌斯变换 \(\hat{F}(x)\) 满足：
莫比乌斯变换即高维前缀和。
莫比乌斯逆变换即高维差分，都可以按维 dp 做到 \(O(\vert U\vert2^{\vert U\vert})\)。
集合并卷积（或卷积）
求集合幂级数 \(H(x) = F(x)G(x)\)，满足
先求出 \(\hat{H}(x)\)，再做逆变换。
推广：集合交卷积（与卷积）
同样令 \(\hat H(x)\) 表示 \(H\) 的变换：
类似的，只不过是高维前缀和换成高维后缀和。
集合无交并卷积（子集卷积）
考虑在集合幂级数中引入未定元 \(y\)，指数代表集合大小。
对 \(x\) 做集合并卷积，\(y\) 做乘法卷积，求得 \(H^\prime(x, y) = F^\prime(x, y) G^\prime(x, y)\)，其中 \([x^Sy^{\vert S\vert}]F^\prime(x, y) = [x^S]F(x)\)。
两个集合无交当且仅当 \(\vert S\cup T\vert = \vert S\vert + \vert T\vert\)。
因此有 \([x^S]H(x) = [x^Sy^{\vert S\vert}]H^\prime(x, y)\)。
我们把形式幂集数 \(F^\prime(x, y)\) 看作一个 \(\vert U\vert\) 行 \(2^{\vert U\vert}\) 的二维矩阵。
每一行保留大小为 \(i\) 的集合系数，其余全为 \(0\)。
\(\vert U\vert^2\) 枚举 \(F^\prime\) 和 \(G^\prime\) 的行，然后做两行的集合并卷积，时间复杂度 \(\vert U\vert^32^{\vert U\vert}\)。
考虑 \(\vert U\vert^22^{\vert U\vert}\) 预处理出每一行的莫比乌斯变换，暴力算 \(y\) 卷积时只要 \(O(\vert U\vert)\) 对应系数相乘。
莫比乌斯变换是线性变换，不需要每做一次卷积就要逆变换，系数可以累加。
最后对每一行做莫比乌斯逆变换，时间复杂度 \(O(\vert U\vert^22^{\vert U\vert})\)。
快速沃尔什变换
- 注意 \(T\) 的范围是所有集合。
考虑分治。
对于 \([0, 2^n)\) 的区间，划分为 \([0, 2^{n - 1})[2^{n - 1}, 2^n)\) 两个子问题。
设 \(x\) 原来的系数为 \(f(x)\)，考虑跨块贡献后的新系数为 \(f^\prime(x)\)。
对于一个右侧元素 \(x + 2^{n + 1}\)，左侧对他的贡献怎么算？
发现左侧对 \(x + 2^{n + 1}\) 的贡献和原来对 \(x\) 的贡献（即 \(f(x)\)）是一样的，因为左边第 \(n - 1\) 位都为 \(0\)。
右侧元素对 \(x + 2^{n + 1}\) 是否还是 \(f(x + 2^{n + 1})\)？
在 \([2^{n - 1}, 2^n)\) 里做 FWT 时没有考虑第 \(n - 1\) 位的贡献，因此 \(f^{\prime}(x + 2^{n - 1}) = f(x) - f(x + 2^{n - 1})\)。
类似地考虑左半边，\(f^{\prime}(x) = f(x) + f(x + 2^{n - 1})\)。
沃尔什逆变换
试着对 \(\hat F(x)\) 再做一遍沃尔什变换。
第二步中 \(\oplus\) 表示对称差。\(S\) 和 \(R\) 的公共元素会对 \(-1\) 产生偶数次贡献。
我们发现只要将 \(\hat{\hat F}(x)\) 的各项系数乘上 \(\dfrac{1}{2^{\vert U\vert}}\) 即可还原 \(F(x)\)，即沃尔什逆变换。
集合对称差卷积（异或卷积）
设 \(H(x) = F(x)G(x)\)。
burnside 引理
对于一个群 \((G, \times)\)，里面的元素都是作用于集合 \(X\) 的置换。
\(h = f \times g\implies \forall x \in X,\ h(x) = g(f(x))\)。
\((G, \times)\) 是群需要满足：
- \(\forall a, b \in G,\ a \times b \in G\)。
- \(\forall a, b, c \in G,\ (a\times b) \times c = a\times (b \times c)\)。
- \(\exists e \in G,\ \forall a \in G,\ e \times a = a \times e = a\)。
- \(\forall a \in G,\exists b \in G,\ a \times b = e\)，把 \(b\) 称作 \(a\) 的逆元。
如果 \(X\) 中两个元素可以通过 \(G\) 中置换变得相等，那么称他们等价，同属一个等价类。
\(X\) 中的等价类个数等于
拉格朗日插值
假设已知多项式 \(f(x)\) 的 \(n\) 处点值 \((x_i, y_i)\)，可以构造出满足这些点值限制的多项式：
如果 \(f(x)\) 次数小于 \(n\)，根据代数基本定理可知 \(f(x) = g(x)\)（我不会证）。
这意味着我们只需 \(n\) 个点值就能确定 \(f(x)\)。
点值表示做乘法时只有 \(O(n)\) 而非卷积的 \(O(n^2)\)。
通过点值还原 \(f(x)\) 可以先 \(O(n^2)\) 求出 \(\prod {x - x_j}\)，然后对于求和的每一项 \(O(n)\) 除一个一次多项式即可。
CF722E Research Rover
题意：\(n \times m\) 的网格，图上 \(k\) 个关键点。给定初始权值 \(s\)，每经过一个关键点权值减半（上取整）。
每次只能向右或向下走，求从 \((1, 1)\) 走到 \((n, m)\) 的期望权值。
将关键点排序。
最终权值只与经过的关键点数有关， \(f_{i, j}\) 表示走到第 \(i\) 个关键点恰好选了 \(j\) 个的方案数。
不怎么好转移，定义 \(g_{i, j}\) 表示走到 \(i\) 个关键点至少走了 \(j\) 个的方案数。
由于我们将方案根据恰好经过的第 \(j - 1\) 个关键点进行分类，因此求得的 \(g\) 是不重不漏的。
当 \(j > 20\) 时权值一定削减为 \(1\)，因此只需算到 \(j = 20\)，剩下的贡献用总方案减掉即可。
submission
CF1097G Vladislav and a Great Legend
题意：给定一颗 \(n\) 个节点的树 \(T\)，对应任意非空顶点集 \(X\)，\(f(X)\) 定义为它在原图的极小连通子图中的边数，求：
其中 \(n \le 10^5,\ k \le 200\)，极小连通子图可认为是保留所有边的虚树。
\(\begin{pmatrix}f(X)\\i\end{pmatrix}\) 的组合意义是从 \(X\) 的虚树中选 \(i\) 条边的方案数。
枚举虚树根 \(x\) 统计贡献。现在加入一颗子树 \(v\)。
肯定是 \(v\) 里的点集与已经访问过子树中的点集（红色）进行配对，考虑一对点集产生多少方案。
我们需要考虑 \(1\) 选不选，\(2\) 选不选，\(3\) 选不选。
虽然他们都不是红色子树中的边，但是与 \(v\) 中点集配对后都会被经过。
设 \(f_{x, i}\) 表示以 \(x\) 为根的子树内选中 \(i\) 条边的生成树个数（方案不一定合法）。
注意这里选中的边不一定是生成树内部边，也有可能是生成树的根到 \(x\) 之间的边。
现在考虑 \(v\) 子树中的一棵生成树。
生成树内部以及生成树的根到 \(v\) 之间的边都已经决策过了，只要决策 \((x, v)\) 选还是不选。
其中 \(f^\prime\) 表示加入 \(v\) 后的 \(f\) 值。
注意这一部分的答案是要计入最终贡献的，因为统计的都是合法方案。
假设 \(v\) 与右边结合的方案已经计算完了。
现在要把一些只在 \(v\) 子树的点集加入 \(f\)，为下一棵子树的转移做准备。
点集的根到 \(v\) 都决策过了，还是考虑选不选 \((x, y)\)。
复杂度据说转移时对 \(k\) 和子树大小取 \(\min\) 就能做到 \(O(nk)\)，很神秘。submission
CF1750G Doping
题意：疑似有点太难了。
CF1967E1 Again Counting Arrays (Easy Version)
题意：给定 \(n, m, b_0\)，求长度为 \(n\) 的序列 \(a\) 个数，\(1 \le a_i \le m\) 且存在一个非负序列 \(b\) 满足 \(\forall i \in [1, n], a_i \ne b_i\land\vert b_i - b_{i - 1} \vert = 1\)。
\(n, m, b_0 \le 2\times 10^5\)。
由于要保证 \(b_i\) 非负，贪心的使 \(b_i\) 尽可能大：
- \(b_{i - 1} + 1 \ne a_i \to b_i = b_{i - 1} + 1\)。
- \(b_{i - 1} + 1 = a_i \to b_i = b_{i - 1} - 1\)。
如果其中出现 \(b_i\) 为负，则序列 \(a\) 并不存在一个合法的 \(b\)。
显然每个 \(a\) 可以按照这种方式唯一生成一个 \(b\)，考虑对 \(b\) 计数。
\(f_{i, j}\) 表示满足 \(b_i = j\) 的序列 \(a\) 个数。
第一种转移 \((m - 1)f_{i, j} \to f_{i + 1, j + 1}\)。第二种转移 \([j < m]f_{i, j} \to f_{i + 1, j - 1}\)。
如果第 \(i\) 个数已经到 \(m\) 了，后面随便怎么填都合法，不妨就用 \(f_{i, m}\) 记录 \(j \ge m\) 的所有情况：\(mf_{i, m} \to f_{i + 1, m}\)。
时间复杂度 \(O(nm)\)，不能通过。
从另一个角度考虑这个问题，把 \(b\) 的生成看作一个点从 \((0, b_0)\) 开始的游走，碰到 \(y = m\) 或 \(x = n\) 则结束游走。
如果第 \(i\) 步往右上走，说明 \(a_i\) 有 \(m - 1\) 种取值；否则 \(a_i\) 只有一种取值。
枚举 \(O(n)\) 种终点 \((i, m)\) 或 \((n, j)\)，求从 \((0, b_0)\) 不经过 \(y = -1\) 和 \(y = m\) 到达终点的路径数。
终点确定向右上和右下的步数也确定，往右上走对应 \(m - 1\) 种 \(a\) 的取值，往右下走对应唯一一种取值。
由于最后一步是确定的，反射容斥的终点设为 \((i - 1, m - 1)\) 可以规避一些边界。反射容斥做到单次 \(O(\dfrac{n}{m})\)。
取阈值 \(B = \sqrt n\)，按照 \(m\) 的大小分两种做法，时间复杂度 \(O(nB + \dfrac{n^2}{B})\)。submission
P4221 [WC2018] 州区划分
题意：\(n\) 个城市划分为若干州。一个州合法当且仅当其生成子图不存在欧拉回路。求所有合法划分的满意度之和。
一个划分的满意度等于所有州的满意度之积。
第 \(i\) 个州的满意度定义为第 \(i\) 个州的人口在前 \(i\) 个州的人口中所占比例的 \(p\) 次幂，即
给出每个城市的人口 \(w_i\) 以及常数 \(p\)，保证 \(n \le 21\) 且无重边无自环。
\(O(m2^n)\) 预处理每个州 \(S\) 是否合法，\(S\) 中存在欧拉回路当且仅当子图连通且所有点度数为偶。
记 \(W(S) = (\sum_{x \in S} w_x)^p\)，\(f(S)\) 表示全集为 \(S\) 时的答案。
枚举 \(S\) 中最后一个州 \(T\)：
把 \(W(S)\) 提出来，记 \(g(T) = \text{legal}(T) \times {W(T)}\)，中间的 \(f(S\setminus T) \times g(T)\) 实际就是一个子集卷积（集合无交并）。
令 \([x^Sy^{\vert S\vert}]g^{\prime}(x, y) = [x^S]g(x)\)，\(x\) 做或卷积，\(y\) 做乘法卷积。
把幂级数看作 \(n \times 2^n\) 的矩阵，每次枚举 \(f^{\prime}\) 的行 \(i\)，和 \(g\) 的每行（除第 \(0\) 行）做或卷积，把答案累计到 \(j > i\) 的 \(f^{\prime}\) 上（乘法卷积使 \(y\) 的指数变大）。
时间复杂度 \(O(n^22^n)\)。submission
NFLSOJ 3392. 计算
题意：定义 \(F(x, a, b) = \gcd(x^a - 1, x^b - 1) + 1\)，如果 \(a, b\) 其一为零则值为零。
给出 \(m, a, b, c, d\)，令 \(L = F(m, a, b) + 1, R = F(m, c, d)\)，保证 \(L < R \le 10^{18}, m \le 10^7\)。
求集合 \(\{L, L + 1, \cdots, R - 1, R\}\) 有多少个子集和能被 \(m\) 整除。
观察 \(F\) 的定义，把他放在 \(x\) 进制下考虑，不难发现 \(F(x, a, b) = x^{\gcd(a, b)}\)，举个十进制的例子：\(\gcd(9999, 99) = \gcd(9999 - 9900, 99) = 10^{\gcd(4, 2)} - 1\)。
由于 \(L \equiv 1 \pmod m\) 且 \(R \equiv 0\pmod m\)，因此每种余数出现的次数都是 \(n = \dfrac{R - L + 1}{m}\)。
枚举子集和：
考虑如果 \(w_m^{ti} = w_m^{tj}\) 也就是 \(ti \equiv tj \pmod m\)。
那么有 \(m \mid t(i - j)\)，因此指数循环的最小正周期为 \(m/d\)，且 \(0, d, 2d, \cdots, (m/d - 1)d\) 每个恰好出现一次，\(d = \gcd(t, m)\)。
（最小正周期内两两不同余是显然的，\(tj \equiv x \pmod m\) 的必要条件是 \(d \mid x\)）
因此：
说明这个乘积与 \(t\) 无关，不妨直接枚举 \(d\)：
根据分圆多项式 \(x^m - 1 = \prod_{i = 0}^{m - 1} (x - w_{m}^i)\)：
暴力枚举因子，时间复杂度 \(O(\sqrt m + d(m)\log n)\)。submission
NFLSOJ 5005. 礼物
题意：计算有多少个不同的有 \(n\) 个珠子的手环，满足有 \(m\) 个珠子是金色的，且金色珠子的最长连续段长度不超过 \(k\)。
两个手环相同当且仅当它们可以通过旋转变得一模一样。\(1 \le n \le 10^6 , 0 \le k \le m \le n\)。
一共 \(n\) 种旋转置换，第 \(i\) 个表示顺时针转 \(i\) 格，计算每种置换对应的不动点个数，最后除以 \(n\)。
考虑一种染色方案的最小正周期 \(T \mid n\)，不妨破环成无限长的链，\(f(p) = f(p + T)\)。
如果存在 \(i\) 使得 \(f(p) = f(p + i)\)，一定有 \(T \mid i\)，即所有 \(T \mid \gcd(i, n)\) 的方案会被 \(i\) 计算到。
考虑枚举 \(d = \gcd(i, n)\) 作为周期，使每种最小正周期 \(T\mid d\) 被恰好算一次，有 \(\varphi(\frac{n}{d})\) 种置换满足 \(d = \gcd(i, n)\)。
假设已经特判掉 \(d = n\) 的情况，现在可以把环拆成 \(\frac{n}{d}\) 个完全相同的部分（已经变成链了），对这部分计数。
\(n \gets d, m \gets \frac{md}{n}\)。不妨把 \(n - m\) 个白子先排列好，然后插空，满足任意间隔不插超过 \(k\) 个。
最右边的间隔不能填，因为和下一循环节的最左间隔等闲。那么问题转化为求不定方程 \(\sum_{i = 1}^{n - m} x_i = m,\ 0 \le x \le k\) 的解的数量。
钦定 \(z\) 个超过 \(k\)，总和可以减掉 \((k + 1)z\)，等价于 \(\sum_{i = 1}^{n - m} x_i = m - kz\) 的非负整数解数 \(\begin{pmatrix}n - (k + 1)z - 1\\ n - m - 1\end{pmatrix}\)，因此可以 \(O(d)\) 容斥。
时间复杂度 \(\sum_{d \mid n} d = \sigma(n)\)，即 \(O(n\log\log n)\)。submission
