数学

基础知识

求和符号

\[ \sum_{i=1}^{n}=a_1+a_2+a_3+...+a_n \]

求和符号的性质

结合律

\[ \sum_{i=1}^{n} \sum_{j=1}^{n} a_i b_j = \sum_{j=1}^{n} \sum_{i=1}^{n} a_i b_j \]

分配率

\[ \sum_{i=1}^{n} a_i \cdot k = (\sum_{i=1}^{n}a_i) \cdot k= k\sum_{i=1}^{n}a_i \\ \sum_{i=1}^{n}\sum_{j=1}^{n}a_i b_j = \sum_{i=1}^n (a_i\sum_{j=1}^n b_j) = (\sum_{j=1}^{n}b_j)\cdot(\sum_{i=1}^{n}a_i) = (\sum_{i=1}^{n}a_i)\cdot(\sum_{j=1}^{n}b_j) \]

改变枚举对象

令 \(z=x+y\) \[ \sum_{x=0}^a\sum_{y=0}^b f(x,y) = \sum_{z=0}^{a+b}\sum_{y=0}^zf(z-y,y) \]

改枚举边界

令 \(y=x-a\) \[ \sum_{x=a}^b f(x) = \sum_{y=0}^{b-a}f(y+a) \]

其他性质

求不同的点配对，就是求所有的，然后减去相同的，然后再除以 \(2\) \[ \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}a_ib_j = \frac{1}{2}(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} a_i b_j- \sum_{i=1}^{n}a_ib_i) \]

二项式定理

\[ (x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{k} y^{n-k} \\ = \sum_{k=0}^{n} \frac{n!}{k!\cdot(n-k)!} x^{k} y^{n-k} = n!\sum_{k=0}^{n} \frac{x^{k} y^{n-k}}{k!\cdot(n-k)!} = n!\sum_{k=0}^{n}(\frac{x^{k}}{k!}) \cdot(\frac{ y^{n-k}}{(n-k)!} ) \]

二项式反演

链接

容斥原理

符号表示

设 \(S\) 是一个有限集，\(a_1, a_2, ..., a_n\) 是 \(n\) 种性质

• \(N(a_i)\) 是 \(S\) 中 \(a_i\) 性质的个数
• 则 \(N(1-a_i)\) 是没有 \(a_i\) 性质的个数
• \(N(a_{i_1}a_{i_2}...a_{i_k})\) 是同时有这些性质的个数
• \(N(a + b)=N(a)+N(b)\)

则容斥原理是 \[ N((1-a_1)(1-a_2)...(1-a_n))=\sum_{i=0}^n(-1)^i\sum_{1\le j_1<j_2<...<j_i\le n} N(a_{j_1}a_{j_2}...a_{j_i}) \]

最大公因数

最大公因数(Greatest Common Divisor). 简称 gcd

gcd的性质 \[ gcd(a,b)=gcd(a,b-a) = gcd(a, b \bmod a) \\ gcd(a,b) = gcd(b,a) \\ gcd(gcd(a,b),c) =gcd(a,gcd(b,c)) \\ \]

通过gcd确定余数

想知道 \(a \bmod b = r\) 可以转换成gcd, 若 \[ gcd(a-r,b) = b \\ gcd(a-r + k*b, b) = b \] 那么 \(a \bmod b = r\)

更加广义 \[ gcd(a-r,t*b) = k*b \\ b | gcd(a-r, t*b) \] 则 \(a \bmod b = r\)

CF1665D(2000)

若 \(x \bmod y = r\) 则 $x ky = {r+ty| ty+r < ky } $

则 \(x \bmod (y+k) \equiv -\lfloor \frac{x}{y} \rfloor \cdot k + r\)

\(x \bmod 1 = 0\)

欧几里得算法 \(O(logn)\)

欧几里得算法也叫辗转相除法, 它可以用来求两个数的最大公因数 它基于一个事实 \[ gcd(a,b)=gcd(b, a \bmod b) \] 代码实现：

int gcd(int a,int b) {
    return b == 0 ? a : gcd(b, a % b);
}

不过在C++的STL中内置了gcd函数 __gcd

排列组合

组合数

性质：

递推： \[ \left(\begin{array}{c} n \\ m \end{array}\right)=\left(\begin{array}{c} n-1 \\ m \end{array}\right)+\left(\begin{array}{c} n-1 \\ m-1 \end{array}\right) \]

互补： \[ \left(\begin{array}{c} n \\ m \end{array}\right)=\left(\begin{array}{c} n \\ n-m \end{array}\right) \]

\[ \sum_{i=0}^{n} i\left(\begin{array}{l} n \\ i \end{array}\right)=n 2^{n-1} \]

\[ \sum_{i=0}^{m}\left(\begin{array}{c} n \\ i \end{array}\right)\left(\begin{array}{c} m \\ m-i \end{array}\right)=\left(\begin{array}{c} m+n \\ m \end{array}\right) \quad(n \geq m) \]

查阅oiwiki有更多

隔板法：

\(n\) 个无法区分的物品分给 \(k\) 个可区分的人, 每个人至少有1 个 \[ \left(\begin{array}{c} n-1 \\ k-1 \end{array}\right) \] 若不限制个数 \[ \left(\begin{array}{c} n + k-1 \\ k-1 \end{array}\right) \]

Hockey Stick Identity

\[ \sum_{i=r}^{n}\left(\begin{array}{l} i \\ r \end{array}\right)=\left(\begin{array}{l} n+1 \\ r+1 \end{array}\right) \]

\[ \sum_{i=0}^k\left(\begin{array}{c} n+i \\ n \end{array}\right)=\left(\begin{array}{c} n+k+1 \\ n+1 \end{array}\right) \]

卡特兰数

公式 \[ H_{n}=\frac{\left(\begin{array}{c} 2 n \\ n \end{array}\right)}{n+1}\left(n \geq 2, n \in \mathbf{N}_{+}\right) \]

递推公式 \[ \begin{gathered} H_{n}= \begin{cases}\sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N}_{+} \\ 1 & n=0,1\end{cases} \\ H_{n}=\frac{H_{n-1}(4 n-2)}{n+1} \\ H_{n}=\left(\begin{array}{c} 2 n \\ n \end{array}\right)-\left(\begin{array}{c} 2 n \\ n-1 \end{array}\right) \end{gathered} \] 括号匹配序列

隔板法

第二类斯特林数

把 \(n\) 个互不相同的球放到 \(k\) 个互不区分的盒子里，每个盒子里至少1个球，的方案数。 \[ f(n,k)=kf(n-1,k)+f(n-1,k-1) \\S_2(n,k)=f(n,k) \] 容斥的公式 \[ S_2(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i C(k,i)(k-i)^n \]

唯一分解定理

任意一个正整数可以分解为若干素数乘积的形式

\[ x= p_1^{a_1}p_2^{a_2}p_3^{a_3}... \]

最小公倍数

最小公倍数(Least Common Multiples) 简称 lcm, 求最小公倍数可以用下面的定理, 一直数 \(a,b\) 的唯一分解式为： \[ a = p_1^{e_1}p_2^{e_2}...p_r^{e_r} \\ b = p_1^{f_1}p_2^{f_2}...p_r^{f_r} \\ \] 那么他们的最大公因数和最小公倍数满足： \[ gcd(a,b)=p_1^{min(e_1,f_1)}p_1^{min(e_2,f_2)}...p_1^{min(e_r,f_r)} \\ lcm(a,b)=p_1^{max(e_1,f_1)}p_1^{max(e_2,f_2)}...p_1^{max(e_r,f_r)} \] 因此 \[ gcd(a,b)\cdot lcm(a,b)=a \cdot b \\ \Rightarrow lcm(a,b) = a\cdot b/gcd(a,b) = a/gcd(a,b)\cdot b \] 注意在计算的时候先做除法，避免溢出

线性筛 \(O(n)\)

线性筛可以快速得到 \([1,n]\) 的素数表 \(n \le 10^6\)。

首先开始情况: \(1\) 不是素数, 假设所有数都是素数(初始化 isprime[i] = 1 )

我们从 \(2\) 开始看。 对于一个数 \(i\) 如果 \(isprime[i] = 1\) 那么他就是素数。然后我们用这一个数乘上我们已经有的素数，去筛掉所有它的倍数。就是对于当前 \(i\) ，用我们已经找到的所有 \(prime[j]\), 筛去 \(i \cdot prime[j]\) . 如果 \(i\) 是 \(prime[j]\) 的倍数，那么我们就不用继续筛了，因为它会被后面的数筛掉。

由于唯一分解定理，我们可以把数 \(x\) 拆解成 \(p_{min}\cdot rest = x\) 也就是把 \(x\) 拆解成最小的素数和其他某个数的乘积。我们枚举到 \(i=rest\) 的时候，用 \(p_{min} \cdot i\) 会把 \(x\) 删掉, 其他情况我们不筛，这样保证每个数只被筛一次，保证了线性的复杂度。如果筛的时候碰到一个素数 \(prime[j]\) 它是 \(i\) 的因子，那么后面的数 \(i \cdot prime[j+k] = rest \cdot prime[j]\) 其中 \(rest > i\) 所以它一定会被后面的数用 \(prime[j]\) 筛去.

具体代码：

tot = 0; // total素数的总数
fill(isprime+1, isprime+n+1, true); // 初始化
isprime[1] = false;
for (int i = 2;i <= n; ++i) {
    if (isprime[i] == true) prime[++tot] = i; // 没被筛掉的是素数
    for (int j = 1;j <= tot && i*prime[j] <= n; ++j) {
        isp[i*prime[j]] = false;
        if (i % prime[j] == 0) break;
    }
}
  

素数个数： \[ n\le 4\cdot 10^7 : 2433655(2\cdot 10^6) 个 \\ n\le 10^7: 664580 (6 \cdot 10^5)个 \\ n\le 10^6: 78499 (<10^5)个 \\ n \le 2\cdot 10^5: 17985(10^4) 个 \]

扩展欧几里得算法

求解同余方程 \[ ax+by=gcd(a,b) \] 的一组解

假设我们有一组解 \(x',y'\) 满足 \[ bx'+(a \ mod \ b)y'=gcd(a,b) \] 那么我们联立这2个式子 \[ ax+by=bx'+(a \ mod \ b)y' \\ ax+by=bx'+(a-(a/b)*b)y' \\ ax+by=bx'+ay'-(a/b)*by' \\ ax+by=ay'+b(x'-(a/b)y') \] 那么显然可见 \(x = y', y=x'-(a/b)y'\) 是原方程的一组解

所以我们可以把 \(a,b\) 由此转化成 \(b,a \mod \ b\) 的子问题来解决，根据欧几里得算法，他会在 \(O(logn)\) 中结束。也就是当式子转化为

\(gcd(a,b)x + k*y\) 的时候，显然有一组 \(x=1,y=0\) 的解。那么就可以一直返回迭代，把原方程的解求出来。

通解

加入我们有2组解 \(x_0,y_0\) 和 \(x_1, y_1\)，那么有 \[ ax_0+by_0=gcd(a,b) \\ ax_1+by_1=gcd(a,b) \] 那么两式相减得到 \[ a(x_0-x_1) + b(y_0 - y_1 ) = 0 \\ a(x_0-x_1) = b(y_1 - y_0) \] 然后两边同时除以 \(gcd(a,b)\) 得到 \[ \frac{a}{gcd(a,b)}(x_0-x_1) =\frac{b}{gcd(a,b)}(y_1-y_0) \] 由于 $ $ 和 $ $ 互质（应该不难证明），那么 \((x_0-x_1)\) 是 $ $ 的倍数，\((y_1-y_0)\) 是 $ $ 的倍数。由此我们就得出了两个解的最小间隔。所以我们就知道 \(x\) 的通解就是 \[ x=x_0 + \frac{b*k}{gcd(a,b)}, k\in \Z \\ y=y_0 - \frac{a*k}{gcd(a,b)}, k\in \Z \]

最小正整数解

根据通解，我们可以得出若\(x\) 是一个解，那么 \(x \ mod \ \frac{b}{gcd(a,b)}\) 也是一组解，那么最小正整数解就是 \((x_0 \ mod \ \frac{b}{gcd(a,b)} + \frac{b}{gcd(a,b)}) \ mod \ \frac{b}{gcd(a,b)}\), 其中 \(x_0\) 是任意一个解。这个通解以及最小正整数解的结论也适用于下面的一般同余方程

同余方程

求解同余方程 \[ ax+by=c \] 的一组解

根据裴蜀定理，当前仅当 \(c\) 是 \(gcd(a,b)\) 的倍数时，该方程有解

我们先根据扩展欧几里得求出一组解 \(x',y'\) 满足 \(ax'+by'=gcd(a,b)\) ，然后在在两边乘以 \(\frac{c}{gcd(a,b)}\) 得出 \[ a(x'*\frac{c}{gcd(a,b)}) + b(y'*\frac{c}{gcd(a,b)}) = c \] 那么我们就得到了这个同余方程的一组解 \(x=x'*\frac{c}{gcd(a,b)},y=y'*\frac{c}{gcd(a,b)}\) 了。

通解

类似于上面的扩展欧几里得的通解，我们可以得出 \[ x=x_0 + \frac{b*k}{gcd(a,b)}, k\in \Z \\ y=y_0 - \frac{a*k}{gcd(a,b)}, k\in \Z \] 其中 \(x_0,y_0\) 是该方程的一组解(不是扩展欧几里得的解，要转化一下)

社 \(m=b/gcd(a,b)\)

最小正整数解是 \[ x_0 +k\cdot m >0 \\ k\cdot m > -x_0 \] 分类讨论

• \(m>0\) : \[ k> \frac{-x_0}{m} \\ k = \lfloor \frac{-x_0}{m} \rfloor + 1 \]

• \(m<0\): \[ k< \frac{-x_0}{m} \\ k = \lceil \frac{-x_0}{m} \rceil -1 \]

求出 \(k\) 之后, 最小正整数解为 \[ x_{positive} = x_0 + k \cdot m \]

同余与模算术

基本取模公式 \[ (a+b) \ mod \ n = ((a\ mod \ n)+(b\ mod\ n))\ mod \ n \\ (a-b) \ mod \ n = ((a\ mod \ n)-(b\ mod\ n)+n)\ mod \ n \\ a\cdot b \ mod \ n = (a\ mod \ n)\cdot(b\ mod\ n)\ mod \ n \\ \]

inline ll add(ll a, ll b) { // 带减法
    return ((a + b) % MOD + MOD) % MOD;
}

inline ll mul(ll a, ll b) {
    return (a * b) % MOD;
}

快速幂 \(O(logn)\)

求 \(a^n\) 的值

我们利用这个性质(这里除法是整除):

• 若 \(n\) 是偶数 \(a^n = a^{n/2}\cdot a^{n/2}\)
• 若 \(n\) 是奇数 \(a^n = a\cdot a^{n/2}\cdot a^{n/2}\)

ll fpow(ll a, ll n) {
    a %= MOD;
    ll ret = 1;
    for (; n; n >>= 1, a = mul(a, a) )
    	if (n & 1) ret = mul(ret, a);
    return ret;
}

扩展中国剩余定理

求解同余方程组 \[ \left\{\begin{array}{ll} x & \equiv a_{1}\left(\bmod n_{1}\right) \\ x & \equiv a_{2}\left(\bmod n_{2}\right) \\ & \vdots \\ x & \equiv a_{k}\left(\bmod n_{k}\right) \end{array}\right. \] 其中的模数 \(n_i\) 不一定是素数

我们通过合并式子来解决这个问题。

比如这2个式子 \[ x \equiv a_1 (\bmod n_1) \\ x \equiv a_2 (\bmod n_2) \] 也就是 \[ x=a_1+n_1*k_1 = a_2 +n_2*k_2 \] 所以 \[ n_1*k_1-n_2*k_2=a_2-a_1 \] 因为正负号对于 \(k_1,k_2\) 不影响，所以就可以当成 \[ n_1*k_1+n_2*k_2=a_2-a_1 \]

其中只有 \(k_1,k_2\) 是未知数。我们可以求解这个同余方程，得到一组解\(k_1', k_2'\) ，（如果无解的话，那么整个无解）

那么根据通解我们知道 \[ k_1=k_1'+\frac{n_2*t}{gcd(n_1,n_2)} \] 然后我们把 \(k_1\)往回代入 \[ x=a_1+n_1*(k_1'+\frac{n_2*t}{gcd(n_1,n_2)}) \\ x=a_1+n_1*k_1'+\frac{n_1*n_2*t}{gcd(n_1,n_2)} \\ x=a_1+n_1*k_1'+lcm(n_1,n_2)*t \\ x \equiv a_1+n_1*k_1' (\bmod lcm(n_1,n_2)) \] 这样我们就把两个方程缩小成1个方程了。我们就这样两两合并，最后就只剩下1个方程了。设这个方程是 \[ x\equiv a (\bmod M) \] 那么就可以自然解出来 \[ x=a+M*k \] 最小非负解就是 \((x_0 \bmod M + M) \bmod M\) 其中 \(x_0\) 是一组可行解

有用的结论 \[ \{23,19,17,13,11,9,7,5,4\} \] 互质且乘积 \(lcm > 10^9\)

欧拉函数

欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\) 且和 \(n\) 互质的数的个数。

当 \(n\) 是质数时， \(\varphi(n)=n-1\)

欧拉函数是积性函数: \[ \varphi(a\times b)=\varphi(a)\times \varphi(b) \] 欧拉函数的公式 \[ \begin{aligned} \varphi(n) &=\prod_{i=1}^{s} \varphi\left(p_{i}^{k_{i}}\right) \\ &=\prod_{i=1}^{s}\left(p_{i}-1\right) \times p_{i} k_{i}-1 \\ &=\prod_{i=1}^{s} p_{i}^{k_{i}} \times\left(1-\frac{1}{p_{i}}\right) \\ &=n \prod_{i=1}^{s}\left(1-\frac{1}{p_{i}}\right) \end{aligned} \]

欧拉降幂

\[ a^{b} \equiv \begin{cases}a^{b \ \bmod \ \varphi(p)}, & \operatorname{gcd}(a, p)=1 \\ a^{b}, & \operatorname{gcd}(a, p) \neq 1, b<\varphi(p) \quad(\bmod p) \\ a^{b \ \bmod \ \varphi(p)+\varphi(p)}, & \operatorname{gcd}(a, p) \neq 1, b \geq \varphi(p)\end{cases} \]

莫比乌斯反演

数论分块

可以计算 \[ \sum_{i=1}^n f(i) g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \] 的式子

数论分块结论

使得式子 \[ \left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{j}\right\rfloor \] 成立的右端点是 \[ \left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor \]

狄利克雷卷积

\[ (f * g)(n):=\sum_{d \mid n} f(d) g\left(\frac{n}{d}\right) \]

计算性质

数论函数

单位函数

恒等函数 Id

sigma

欧拉函数

欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数。

莫比乌斯函数

\[ \mu(n)= \begin{cases}1 & n=1 \\ 0 & n \text { 含有平方因子 } \\ (-1)^k & k \text { 为 } n \text { 的本质不同质因子个数 }\end{cases} \]

莫比乌斯函数是积性函数, 并且 \[ \sum_{d \mid n} \mu(d)=\varepsilon(n), \quad \mu * 1=\varepsilon \] 所以有 \[ [\operatorname{gcd}(i, j)=1]=\sum_{d \mid \operatorname{gcd}(i, j)} \mu(d) \] 另一个结论 \[ \varphi * 1=\mathrm{id} \]

计算 gcd(i,j) = 1 的个数， 计算 gcd(i,j)=k 的个数

计算 gcd(ai,bi) = 1 的个数

计算 gcd(a,b) 的和

莫比乌斯变换

形式一，\(d\) 是 \(n\) 的因子 \[ f(n)=\sum_{d \mid n} g(d) \Leftrightarrow g(n)=\sum_{d | n} \mu(d) f\left(\frac{n}{d}\right) \] 形式二，\(n\) 是 \(d\) 的倍数 \[ f(n)=\sum_{n \mid d} g(d) \Leftrightarrow g(n)=\sum_{n \mid d} \mu\left(\frac{d}{n}\right) f(d) \]

多项式

FFT快速傅里叶变换

它可以用来求卷积。下面是离散卷积的定义 \[ (f*g)(x) = \sum_{i=-\infin}^{\infin} f(i)g(x-i) \] 求卷积的过程可以等价于求两个多项式相乘

对于一个多项式： \[ P(x)=a_0+a_1x+a_2x^{2}+...+a_{n-1}x^{n-1} = \sum_{i=0}^{n-1}a_ix^{i} \] 我们可以用系数来表示它 \[ P(x)=\{a_0,a_1,a_2,a_3,...a_{n-1}\} \] 我们也可以用一个函数来表示这个多项式 \[ f_P(x)=a_x, x\in[0,n-1] \] 也就是说，我们把系数作为函数值来表示多项式，其实本质上还算是用系数来表示多项式。

设另一个多项式 \(Q(x)\) 为 \[ Q(x)=\sum_{i=0}^{m-1}b_ix^{i} \] 那么计算两个多项式相乘，也就是 \[ P(x)*Q(x)=(\sum_{i=0}^{n-1}a_ix^{i})(\sum_{i=0}^{m-1}b_ix^{i}) \\ =\sum_{i=0}^{n+m-2}\sum_{j=0}^{min(n-1,i)}a_jb_{i-j}x^{i} \] 那么我们在把\(P(x)*Q(x)\) 表示成函数，那就是 \[ (f_P*f_Q)(x)= \sum_{j=0}^{min(n-1,x)} a_jb_{x-j} \] 这就和卷积的定义相符合了。

如何求2个多项式的乘积

首先，我们讨论多项式的表示方法。根据代数基本定理，我们知道，2个点确定一条直线(1次多项式) \(n\) 个点可以确定 \(n-1\) 次多项式( \(n\) 阶多项式).

所以我们可以用 \(n\) 个坐标来表示 \[ P(x)=\sum_{i=0}^{n-1}a_ix^{i} \] 那么要完成相乘的操作，我们可以这样子：

1. 先把两个多项式转化成坐标的形式
2. 然后把坐标相乘
3. 然后再转化成系数表示法

这3步骤就是通过傅里叶变换，计算多项式相乘的步骤。第1步成为傅里叶变换，第3步成为傅里叶逆变换。由于我们的点是离散的，所以第1不也叫离散傅里叶变换(DFT), 第3步也就离散傅里叶逆变换(IDFT).

DFT离散傅里叶变换

现在的问题是，我们需要选择哪些点来表示多项式呢。我们在复数域中选取 \[ (x,y) = (w_n^k, P(w_n^k)),k \in [0,n-1] \] 这 \(n\) 个点来表示, 其中 \(w_n\) 是 \(n\) 次单位根。我们先不管为什么这么选，它的原因后面会解释。下面先介绍一下 \(n\) 次单位根

n次单位根

对于方程 \[ x^{n}=1 \] 在复平面中一共有 \(n\) 个解。其中辐角最小的那个解，就是\(n\) 次单位根，记为 \(w_n\)

显然，它满足下面2个性质 \[ w_n^0 =1 \\ w_n^n = 1 \] 我们知道欧拉公式是

对于复平面中的任意值 \(x\) ，满足下列等式。 \[ e^{i x}=\cos x+i \sin x \] 所以，我们可以根据欧拉公式写出 \(n\)次单位根的具体解：

令欧拉公式中 \(x =2k\pi\) ，则 \[ e^{i2k\pi}=cos(2k\pi)+isin(2k\pi) \] 我们知道 \(cos(2k\pi)=1,sin(2k\pi)=0\)

所以 \[ e^{i2k\pi}=1+i*0=1 \\ (e^{\frac{2k\pi}{n}})^n=1 \] 所以

\(x=e^{\frac{i2k\pi}{n}}\) 是 \(x^{n}=1\) 的解，其中辐角最小的解是 \(k=1\) 时，也就是 \(e^{\frac{i2\pi}{n}}\)

所以 \[ w_n=e^{\frac{i2\pi}{n}} \\ w_n^{k}=(e^{\frac{i2\pi}{n}})^k=e^{\frac{i2k\pi}{n}} \] 此外， \(n\) 次单位根还有2个性质，待会要用到的

性质1： \[ w_{2n}^{2k}=w_{n}^{k} \] 证明 \[ w_{2n}^{2k}=e^{\frac{i2*2k\pi}{2n}}=e^{\frac{i2k\pi}{n}}=w_n^{k} \] 性质2： \[ w_{2n}^{k+n}=-w_{2n}^{k} \] 证明 \[ w_{2n}^{n}=e^{\frac{i2n\pi}{2n}} =e^{i\pi}=cos\pi+isin\pi=-1+i*0=-1 \\ w_{2n}^{k+n}=w_{2n}^n*w_{2n}^k=-1*w_{2n}^{k}=-w_{2n}^{k} \] 下面我们就开始进行傅里叶变换的步骤了

我们我们想知道傅里叶变换的具体输入输出是什么

输入：多项式的系数列表

输出：多项式在n个点的函数值 \(P(w_n^k)\) 的列表

我们首先观察一下这个多项式, 我们假设 n 是 \(2\) 的一个次幂(其他情况可以向上扩展到2的次幂的形式),我们可以分为奇数和偶数2个部分 \[ P(x)=\sum_{i=0}^{n-1}a_ix^i=\sum_{i=0}^{n/2-1}a_{2i}x^{2i}+\sum_{i=0}^{n/2-1}a_{2i+1}x^{2i+1} \] 其中的级数部分还可以提出来一个 \(x\) \[ P(x)=\sum_{i=0}^{n/2-1}a_{2i}x^{2i}+x\sum_{i=0}^{n/2-1}a_{2i+1}x^{2i} \] 那么现在把分出来的2个步骤看成多项式，那么就有 \[ P(x)=P_e(x^2)+xP_o(x^2) \] 这样一来，我们就把问题分为了一般，通过解决 \(P_e(x^2)\) 和 \(P_o(x^2)\) ，然后合并就得到了我们当前的解。没错，就是分治的思想。

但是我们的子问题有一个 \(x^2\) 它还需要处理一下。首先我们递归解决子问题 \(P_e(x)\) 和 \(P_o(x)\) 也就是没有平方的版本，然后我们获得了一个输出也就是2个数组 \(P_e(w_{n/2}^k)\) 和 \(P_o(w_{n/2}^k)\), 而我们想要的是 \(P_e(w_n^{2k})\) 和 \(P_o(w_n^{2k})\)

根据单位根的性质，我们知道, 对于 \(k<n/2\) \[ w_{n}^{2k}=w_{n/2}^{k} \] 所以 \(w_n^{2k}=(w_{n/2}^k)^2\) 就可以通过子问题得到了，也就是 \[ P(w_n^{k})=P_e(w_{n}^{2k}) + w_n^{k}P_o(w_n^{2k}) \\ = P_e(w_{n/2}^{k}) + w_n^{k}P_o(w_{n/2}^{k}) \] 而对于剩下的 \(n/2\) 部分来说 \[ w_{n}^{k+n/2}=-w_{n}^{k}=-(w_{n/2}^k) \] 也可以通过子问题得到，我们就得出了完整的 \(w_n^k\) ,那么由此就可以计算 \(w_n^{2k}\) ，也就是 \[ P(w_n^{k+n/2})=P_e(w_{n}^{2k+n}) + w_n^{k+n/2}P_o(w_n^{2k+n}) \\ = P_e(w_{n}^{2k}) - w_n^{k}P_o(w_{n}^{2k}) \\ = P_e(w_{n/2}^{k}) - w_n^{k}P_o(w_{n/2}^{k}) \] 也就可以合并子问题了。所以现在就知道为什么要用单位根来作为点了。因为有这样的递归性质，可以方便我们合并子问题。

IDFT离散傅里叶逆变换

傅里叶的逆变换其实可以转换为傅里叶变换来求。先说结论：

我们需要把 \(n\) 个点的函数值表示的多项式，转换成系数表示。我们只需要把这 \(n\) 个点的函数值当成系数来看，进行一次傅里叶变换。在变换的过程中，把 \(\pi\) 的值用 \(-\pi\) 来代替。最后算出来的输出列表，再全部除以 \(n\) 即可得到系数。

下面是推导。

设我们有一组DFT的输出 \(P(w_n^k)\) 的值，求原来多项式的系数 \(a_i\)

我们构造一个多项式 \[ Q(x)=\sum_{i=0}^{n-1}P(w_n^i)x^i \] 也就是把输出当做系数构造一个多项式。然后我们求这个多项式在 \(x=w_n^{-k}\) 的值 \(Q(w_n^{-k})\) \[ Q(w_n^{-k})=\sum_{i=0}^{n-1}P(w_n^i)(w_n^{-k})^i \\ = \sum_{i=0}^{n-1} (\sum_{j=0}^{n-1}a_j(w_n^{i})^j) (w_n^{-ki})\\ = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_jw_n^{i(j-k)} \\ = \sum_{j=0}^{n-1}\sum_{i=0}^{n-1}a_jw_n^{i(j-k)} \\ = \sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}(w_n^{(j-k)})^i \] 然后设 \(S(w_n^a)=\sum_{i=0}^{n-1}(w_n^a)^i\)

若 \(a=0\) , 则 \(S(w_n^a)=n\)

若 \(a \ne 0\) ,用错位相减法 \[ S(w_n^a)=\sum_{i=0}^{n-1}(w_n^a)^i \\ w_n^aS(w_n^a)=(\sum_{i=0}^{n-1}(w_n^a)^i)*(w_n^a)=\sum_{i=1}^{n}(w_n^a)^i \] 下式子减去上面的式子 \[ (w_n^a-1)S(w_n^a)=(w_n^a)^n-(w_n^a)^0 \\ S(w_n^a)=\frac{(w_n^a)^n-(w_n^a)^0}{(w_n^a-1)}=0 \] 所以 \[ S\left(\omega_{n}^{a}\right)=\left\{\begin{array}{l} n, a=0 \\ 0, a \neq 0 \end{array}\right. \] 然后再带入原来的式子 \[ Q(w_n^{-k})=\sum_{j=0}^{n-1}a_jS(w_n^{(j-k)})=a_k * n \] 所以 \(Q(x)\) 的再 \(x=w_n^{-k}\) 的 \(n\) 个函数值为 \(a_k * n\)

所以我们把 \(P(w_n^k)\) 作为输入，用快速傅里叶计算以它为系数的多项式在 \(x=w_n^{-k}\) 的函数值，就得到了 \(a_k*n\) 的，那么在除以 \(n\) 就得到了 \(a_k\) 也就是原来系数的值。在实现的时候，我们只要令 \(\pi=-\pi\) 就可计算 \(x=w_n^{-k}\) 的快速傅里叶变换。

递推的FFT

由于递归版的FFT常数会很大，所以我们下面再进行一些优化

我们在递归的时候，把一个多项式拆成了奇数和偶数的两个部分。这种拆分其实是有规律可循的 \[ (0,1,2,3,4,5,6,7) \\ (0,2,4,6),(1,3,5,7) \\ (0,4),(2,6),(1,5),(3,7) \] 我们把第1行和最后一行的数转换成二进制，就会得到 \[ 000,001,010,011,100,101,110,111 \\ 000,100,010,110,001,101,011,111 \] 于是我们发现，最后一行的数，正好是第一行的数的二进制倒过来写的数。

所以我们用这个性质，可以快速计算递归结尾的情况，然后直接向上合并。这样省去了递归的过程会更加快。

我们可以用递推的方法计算翻转后的数。

设 \(R(x)\) 是 \(x\) 二进制翻转后的数，设 \(len=2^{k}\)

首先 \(R(0)=0\),

假如我们知道 \(R(x/2)\) 的值，那么我们可以先利用这个结果。首先，我们把 \(x\) 右移 \(1\) 位就得到了 \(x/2\) ，然后把\(x/2\) 翻转，再右移。现在就只有最高位不知道了。那么最高位可以用 \(x\) 的最低位来算。如果 \(x\) 最低位是 \(1\) 那么最高位就是 \(1\) ，如果是 \(0\) 那么最高位就是 \(0\). \[ R(x)=R(x/2)/2 + (x \& 1)*(len/2) \] 这个就是我们的递推式子了。

NTT快速数论变换

为什么有了FFT后还需要NTT呢，因为FFT是浮点运算，会有精度的问题。而用数论方法可以实现精度的0损失。而且还可以取模。

我们需要在数论中找到一个概念，来代替FFT中的 \(w_n\) 这个东西就是原根

原根

设 \(p\) 是素数，\(n\) 是 \(p-1\) 的因子。同时 \(p\) 也是我们用来取模的素数。现在我们得到了原根的定义。 \[ g_n=g^{\frac{p-1}{n}} \] 其中的 \(g\) 是模 \(p\) 意义下的原根。求原根的步骤会在后面提到，现在我们假设已经得到了原根 \(g\) ，我们先来看它的一些性质

我们发现 \(g_n\)它其实是方程 \[ x^{n} \equiv 1 \bmod p \] 的其中一个解。

证明

根据费尔马小定理 \[ a^{p-1} \equiv 1 \bmod p \] 所以代入得到 \[ (g^{\frac{1}{n}})^{p-1} \equiv 1 \bmod p \\ (g^{\frac{p-1}{n}})^n \equiv 1^n \equiv 1 \bmod p \] 那么 \[ g_n^k=g^{\frac{k(p-1)}{n}} \] 性质1 \[ g_n^n=g^{n(p-1)/n}=g^{p-1}=1 \\ g_n^{n/2}=g^{(p-1)/2}=-1 \]

性质2 \[ g_{2n}^{2k} =g_n^{k} \\ (g_n^{k+n/2})^2=g_n^{2k+n} \equiv g_n^{2k}=g_{n/2}^k \] 证明 \[ g_{2n}^{2k}=g^{\frac{2k(p-1)}{2n}}=g^{\frac{k(p-1)}{n}}=g_n^k \]

所以我们用 \(g_n\) 来代替FFT 中的 \(w_n\)

NTT逆变换

类似IDFT，我们在计算 \(g_n\) 的时候用逆元代替。然后计算完答案时候在\(a_i/n\) 也就是乘上\(n\) 的逆元。

线性代数

矩阵快速幂

矩阵加速

https://www.luogu.com.cn/blog/gkxx-is-here/what-the-hell-is-ddp

https://zhuanlan.zhihu.com/p/107709816

题目

https://codeforces.com/contest/750/problem/E

https://codeforces.com/problemset/problem/1252/K

http://acm.hdu.edu.cn/showproblem.php?pid=6155

https://codeforces.com/gym/102500/problem/J

题目

数论

SRM661div1Easy: MissingLCM

唯一分解定理，线性筛

题目

给定 \(N \le 10^6\) , 求最小的 \(M > N\) ，使得 \(LCM(1,...,M) = LCM(N+1, ...,M)\)

分析

如果把 \(LCM\) 用唯一分解定理表示，那么就是每一个相关的素数 \(p\) , 设 \(e_p(x)\) 是 \(x\) 分解后素数 \(p\) 的次幂。都有 \(max(e_p(1),...,e_p(M))=max(e_p(N+1),...,e_p(M))\) 成立。首先发现 \([1,M]\) 是包含 \([N+1,M]\) 的，也就是 \([N+1,M]\) 里面有的数，\([1,M]\) 里面都有。那么只要 \([1,N]\) 里面的最大值出现在 \([N+1,M]\) 里面就可以了。假如说一个在\([1,N]\) 中的素数的最大值是 \(p^{e_{max}}\) , 那么，\(p^{e_{max}}\cdot p > N\) （否则最大值就会更大）.所以出现在 \([N+1,M]\) 中可以分解出 \(p^{e_{max}}\) 的数，它一定是这个形式的 \(c\cdot p^{e_{max}}\) ，那我们要给每一个素数求一个最小的 \(c\) 使得 \(c\cdot p^{e_{max}}\) 刚好大于 \(N\).

我们先用线性筛算出 \([1,N]\) 的所有素数。然后我们枚举(可以二分，但是枚举这道题能过，最多枚举 \(\sqrt(N)\) 次)每一个素数, 从小到大枚举 \(c\) 求出 \(c\cdot p^{e_{max}}\) , 然后求出所有素数的这个值取最大值 就是 \(M = max(c_i\cdot p_i^{e_{max}})\)。这个就是答案了。特殊情况: 当 \(N=1\) 时候，\(M=2\)

复杂度 \(O(N+logN*\sqrt(N)) = O(N)\)

SRM509div1Easy: LuckyRemainder

同余，取模

题目

给定一个字符串 \(X, |X| \le 50\) , 字符都是 \(1-9\). 集合 \(S\) 是包含位置的集合，比如 \(S=\{1,2\}\) 表示\(X\) 的第一个和第二个字符。你可以从 \(X\) 删除 \(S\) 中的位置得到一个新的数。比如 \(X=12345,S=\{2,4\}\) 那么删除后的数是 \(135\). 定义 \(super(X)\) 所有删除 \(S\) 的子数的和，如 \(super(123)=123+12+23+13+1+2+3=177\)。求 \(super(X)\) 除以 \(9\) 的余数

分析

根据同余的性质，我们显然可以把答案写成 \[ sup(123)\ mod \ 9= (123 + 12 + 13 + 23 + 1 + 2 + 3) \ mod\ 9 \\ = (123 \ mod \ 9) + (12 \ mod \ 9) + (13 \ mod \ 9) + (23 \ mod \ 9) + (1 \ mod \ 9) + (2 \ mod \ 9) + (3 \ mod \ 9) \] 我们发现，同一个数字出现了很多次。那么我们也许可以进一步拆分，都拆成单个数的形式： \[ 123=1 \cdot 100+2 \cdot 10+3 \\ 123 \ mod \ 9 = (1\cdot 100) \ mod \ 9 + (2\cdot 10) \ mod \ 9 +3 \ mod \ 9 \\ = 1 \cdot(100 \ mod \ 9) +2\cdot(10\ mod\ 9) + 3\cdot(1\ mod\ 9) \] 然后我们考虑 \(10^n \ mod \ 9\) 的值 \[ 10^n \ mod\ 9=(10\ mod \ 9)^n = 1 \] 所以上述可以变换成 \[ sup(123)\ mod\ 9= 4\cdot(1\ mod \ 9) + 4\cdot(2\ mod \ 9) + 4\cdot(3\ mod \ 9) \\ = 4 \cdot(1+2+3) \ mod\ 9 \] 那么答案就是其中的每一个数字 \(mod\ 9\) 然后求和再乘上它出现的次数。那么第 \(i\) 个数可以出现在集合长度为 \(1,2,..n\) 的集合里，我们用排列组合算一下，发现次数是 \[ C^{0}_{n-1}+C^{1}_{n-1}+C^{2}_{n-1}+...+C^{n-1}_{n-1}=2^{n-1} \] 所以答案就是 \[ 2^{n-1}\cdot \sum_{i=0}^{n-1}{x_i} \ mod\ 9 \] 所以我们之间算一下这个简单的式子就好了

代码

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 5e5 + 5;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
    cout << "{";
    if (sz(v)) print(v[0]);
    for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
    cout << "}\n";
}

class LuckyRemainder {
public:
    int getLuckyRemainder(string x) {
        ll sum = 0; int n = x.length();
        for (int i = 0;i < n; ++i) {
            sum += x[i] - '0';
        }
        ll p = 1;
        p <<= n-1;
        return ((sum % 9) * (p % 9)) % 9;
    }
};

二项式定理

ARC106D - Powers

题意

给定 \(N \le 10^5\) 个数 \(A_i\) 和一个整数 \(K\) ,对于每个 \(1\le X\le K\) 求出 \[ \left(\sum_{L=1}^{N-1} \sum_{R=L+1}^{N}\left(A_{L}+A_{R}\right)^{X}\right) \bmod 998244353 \] 的值

分析

高次方不好下手，我们用二项式定理展开. 不过为了方便处理，我们可以先把下标都改成从 \(1\) 到 \(N\) 的形式 \[ \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X = \frac{1}{2}(\sum_{L=1}^{N} \sum_{R=1}^{N} (A_L+A_R)^X - \sum_{i=1}^{N}(A_i+A_i)^X) \] 那么对于中间那个复杂的式子，我们用二项式定理展开 \[ \begin{aligned} \sum_{i=1}^{N} \sum_{j=1}^{N}\left(A_{i}+A_{j}\right)^{X} &=\sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=0}^{X}\left(\begin{array}{l} X \\ k \end{array}\right) A_{i}^{k} A_{j}^{X-k} \\ &=\sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=0}^{X} X ! \cdot \frac{A_{i}^{k}}{k !} \cdot \frac{A_{j}^{X-k}}{(X-k) !} \\ &=X ! \sum_{k=0}^{X}\left(\sum_{i=1}^{N} \frac{A_{i}^{k}}{k !}\right)\left(\sum_{j=1}^{N} \frac{A_{j}^{X-k}}{(X-k) !}\right) \end{aligned} \] 这样我们先预处理出所有的 \(\sum_{i=1}^{N} \frac{A_{i}^{k}}{k !}\) 就可以快速求出来了

博弈论

GameGame