单位根反演
恒等式
$$
[d|n]=\frac{1}{d} \sum_{i=0}^{d-1} \omega_d^{i\times n}
$$
其中 $\omega_d$ 是 $d$ 次单位根
当 $d|n$，右边和式中每一项都为 $1$
当 $d\nmid n$，容易得到右边为 $0$
例题
PYXFIB
题意
令数列 $f_0=f_1=1,f_n=f_{n-1}+f_{n-2}$
给出 $n,k,p$
求
$$
\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{n}{i\times k}\times f_{i\times k}
$$
模质数 $p$ 的值，且 $p \equiv 1 \pmod{k}$
不超过 $20$ 组数据
$n\le 10^{18}, p\le 10^9, k\le 20000$
做法
所求转化为
$$
\sum_{i=0}^n [k|i] \binom{n}{i}\times f_{i}
$$
考虑用递推矩阵代替 $f$ 数列
令
$$
A=
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}
$$
所求即为
$$
\sum_{i=0}^n [k|i] \binom{n}{i}\times A^i
$$
第一行第一列的元素
把恒等式代入得到
$$
\begin{aligned}
& \frac{1}{k}\sum_{i=0}^n \binom{n}{i}\times A^i
\sum_{j=0}^{k-1} \omega_k^{i\times j} \
= & \frac{1}{k} \sum_{j=0}^{k-1} \sum_{i=1}^n \binom{n}{i}\times A^i \times \omega_{k}^{i\times j} \
= & \frac{1}{k} \sum_{j=0}^{k-1}\left(\omega_k^jA+I \right)^n
\end{aligned}
$$
最后一步用了二项式定理，其中 $I=\begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix}$
由于保证了 $p \equiv 1 \pmod{k}$，直接在模意义下计算 $\omega_k$ 即可
复杂度 $\mathcal O(k\log n)$
代码
1 |
|
LJJ 学二项式定理
题意
$T$ 组数据，给出 $n,s,a_0,a_1,a_2,a_3$
求
$$
\left(\sum_{i=0}^n \binom{n}{i}\times s^i\times a_{i\bmod 4}\right) \bmod 998244353
$$
$T\le 10^5,n\le 10^{18}$
$s,a_0,a_1,a_2,a_3\le 10^8$
做法
考虑计算 $i$ 是 $4$ 的倍数情况
$$
\begin{aligned}
& \sum_{i=0}^n [4|i] \binom{n}{i}\times s^i\times a_0 \
= & \frac{1}{4} \sum_{i=0}^n \binom{n}{i}\times s^i\times a_0 \sum_{j=0}^3 \omega_4^{i\times j} \
= & \frac{a_0}{4}\sum_{j=0}^3 \sum_{i=0}^n \omega_4^{i\times j} \times \binom{n}{i}\times s^i \
= & \frac{a_0}{4}\sum_{j=0}^3 (\omega_4^j\times s +1)^n
\end{aligned}
$$
其他 $3$ 种情况也类似，以 $i\equiv 1\pmod 4$ 为例
$$
\begin{aligned}
& \sum_{i=0}^n [4|(i-1)] \binom{n}{i}\times s^i\times a_1 \
= & \frac{1}{4} \sum_{i=0}^n \binom{n}{i}\times s^i\times a_1 \sum_{j=0}^3 \omega_4^{(i-1)\times j} \
= & \frac{a_1}{4}\sum_{j=0}^3 \sum_{i=0}^n \omega_4^{(i-1)\times j} \times \binom{n}{i}\times s^i \
= & \frac{a_1}{4}\sum_{j=0}^3 \omega_4^{-j} (\omega_4^j\times s +1)^n
\end{aligned}
$$
复杂度 $\mathcal O(\log n)$
代码
1 |
|
复读机
题意
有 $k$ 个不同的复读机，接下来 $n$ 秒中每秒都会挑一个复读机复读，一个复读机复读了 $d$ 的倍数次才会感到快乐
求有多少种方案使得所有复读机都感到快乐，模 $19491001$
三种子任务
- $k\le 500000,d=1$
- $k\le 500000,d=2$
- $k\le 1000,d=3$
$n\le 10^9$
做法
当 $d=1$ 时，答案即为 $k^n$
$d>1$ 时考虑 dp
令 $f_{i,j}$ 表示 $i$ 个复读机，一共复读了 $j$ 次的方案数（方案不同当且仅当存在第 $x$ 次复读的复读机不同）
于是
$$
\begin{aligned}
f_{i,j} & = \sum_{x=0}^{j} [d|x] f_{i-1,j-x}\binom{j}{x} \
& = \frac{1}{d} \sum_{x=0}^j f_{i-1,j-x} \binom{j}{x} \sum_{t=0}^{d-1} \omega_d^{tx} \
\frac{f_{i,j}}{j!} &= \frac{1}{d} \sum_{x=0}^j \frac{f_{i-1,j-x}}{(j-x)!} \times \frac{\sum_{t=0}^{d-1} \omega_d^{tx}}{x!}
\end{aligned}
$$
用生成函数表示第二维的转移即
$$
\begin{aligned}
f_i(x) & = \sum_{j=0}^{\infty} f_{i,j}x^j \
f_i(x) & = f_{i-1}(x)\times \left(\frac{\sum_{j=0}^{\infty} \sum_{t=0}^{d-1} \frac{\omega_d^{tj}}{j!}x^j }{d}\right) \
f_k(x) & = \left(\frac{\sum_{j=0}^{\infty} \sum_{t=0}^{d-1} \frac{\omega_d^{tj}}{j!}x^j }{d}\right) ^k \
& = \left(\frac{\sum_{t=0}^{d-1} \sum_{j=0}^{\infty} \frac{\omega_d^{tj}}{j!}x^j }{d}\right) ^k
\end{aligned}
$$
当 $d=2$ 时，展开 $t$ 的枚举，得到
$$
\left(\sum_{j=0}^{\infty} \frac{x^j}{j!}\right)+\left(\sum_{j=0}^{\infty} \frac{\omega_2^j x^j}{j!}\right) = e^x+e^{\omega_2x}
$$
其中 $\omega_2=-1$
所求
$$
\begin{aligned}
f_{k,n} & = n![x^n]f_k(x) \
& = n![x^n]\left(\frac{e^x+e^{-x}}{2}\right)^k \
& = \frac{n![x^n]\left(\sum_{i=0}^k e^{ix} \times e^{-(k-i)x}\times \binom{k}{i}\right)}{2^k}
\end{aligned}
$$
复杂度 $\mathcal O(k\log n)$
$d=3$ 同理，展开
$$
\left( \frac{e^x+e^{\omega_3 x}+e^{\omega_3^2 x}}{3}\right)^k
$$
枚举其中两项，复杂度 $\mathcal O(k^2\log n)$
代码
1 |
|
倍数？倍数！
题意
求从 $0,1,\dotsc,n-1$ 选出 $k$ 个互不相同的数和为 $n$ 的倍数的方案数，模 $10^9+7$
$n\le 10^9, k\le 1000$
做法
神仙题
先不考虑 $k$ 的限制，求从 $0,1,\dotsc,n-1$ 中选出任意个数和为 $n$ 的倍数的方案数
考虑生成函数，答案为
$$
f(x) = \prod_{i=0}^{n-1} (x^i+1) = \sum_{i=0}^\infty f_ix^i
$$
的所有 $n$ 的倍数次项系数的和，即
$$
\begin{aligned}
& \sum_{i=0}^\infty [n|i]\times f_i \
= & \frac{1}{n} \sum_{i=0}^\infty f_i \sum_{j=0}^{n-1} \omega_n^{i\times j} \
= & \frac{1}{n} \sum_{j=0}^{n-1} \sum_{i=0}^\infty f_i(\omega_n^j)^i \
= & \frac{1}{n} \sum_{j=0}^{n-1} f(\omega_n^j) \
= & \frac{1}{n} \sum_{j=0}^{n-1} \prod_{i=0}^{n-1} (\omega_n^{i\times j}+1)
\end{aligned}
$$
枚举 $g=\gcd(j,n)$，由单位根的性质，上式等于
$$
\begin{aligned}
& \frac{1}{n} \sum_{g|n} \sum_{j=0}^{\frac{n}{g} -1} [j \perp \frac{n}{g}] \prod_{i=0}^{n-1} (\omega_{\frac{n}{g}}^{i\times j}+1) \
= & \frac{1}{n} \sum_{g|n} \sum_{j=0}^{\frac{n}{g} -1} [j \perp \frac{n}{g}] \left( \prod_{i=0}^{\frac{n}{g}-1} (\omega_{\frac{n}{g}}^{i\times j}+1)\right)^g \
\end{aligned}
$$
由于 $j$ 与 $\frac{n}{g}$ 互质，上式等于
$$
\begin{aligned}
& \frac{1}{n} \sum_{g|n} \sum_{j=0}^{\frac{n}{g} -1} [j \perp \frac{n}{g}] \left( \prod_{i=0}^{\frac{n}{g}-1} (\omega_{\frac{n}{g}}^{i}+1)\right)^g \
= & \frac{1}{n} \sum_{g|n} \varphi(\frac{n}{g}) \left( \prod_{i=0}^{\frac{n}{g}-1} (\omega_{\frac{n}{g}}^{i}+1)\right)^g
\end{aligned}
$$
考虑单位根的意义 $x^n-1=0=\prod_{i=0}^{n-1} (x-\omega_n^i)$
代入 $x=-1$ 得到 $(-1)^n-1=(-1)^n \prod_{i=0}^{n-1} (\omega_n^i+1)$
因此 $\prod_{i=0}^{n-1} (\omega_n^i+1)=1-(-1)^n$
答案等于
$$
\frac{1}{n} \sum_{g|n} \varphi(\frac{n}{g}) \left(1-(-1)^{\frac{n}{g}}\right)^g
$$
考虑有了选 $k$ 个的限制
答案为
$$
[y^k]\prod_{i=0}^{n-1} (x^iy+1)
$$
的所有 $n$ 的倍数次项系数的和
大致过程与上面相同，把 $y$ 保留，在代入时代入 $-\frac{1}{y}$，最后得到
$$
\frac{1}{n} \sum_{g|n} \varphi(\frac{n}{g}) \left(1-(-y)^{\frac{n}{g}}\right)^g
$$
求第 $k$ 项系数
要对答案有贡献，记 $d=\frac{n}{g}$
必须满足 $d|k$，因此 $\varphi(d)$ 的部分可以做到 $\mathcal O(k)$
另外还要求 $\binom{g}{\frac{k}{d}}$，单次 $\mathcal O(\frac{k}{d})$，总复杂度 $\mathcal O(\sigma_1(k))\approx \mathcal O(k\log \log k)$
所以 $k$ 还可以放大一点
代码
1 |
|