单位根反演
恒等式
\[ [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 |
|