返回「邏輯與算法」主頁
本页面仅收录 Useful Formulas & Theorems in CP。对于知识点,另见 邏輯與算法:雜項 。 略去繁杂的证明和算法流程,多写柿子少废话。基本是看到什么有用的好吃的柿子就会塞进来。 文中可能出现中英文混用的情况,因为作者会优先使用更便于表达的语言(x。
恒等式 极值对偶恒等式 x + y = max ( x , y ) + min ( x , y ) ∣ x − y ∣ = max ( x , y ) − min ( x , y ) 2 max ( x , y ) = ( x + y ) + ∣ x − y ∣ 2 min ( x , y ) = ( x + y ) − ∣ x − y ∣ ∣ x − y ∣ = ∣ max ( x , y ) − min ( x , y ) ∣ x + y = ( x ∨ y ) + ( x ∧ y ) x ⊕ y = ( x ∨ y ) − ( x ∧ y ) 2 ( x ∨ y ) = ( x + y ) + ( x ⊕ y ) 2 ( x ∧ y ) = ( x + y ) − ( x ⊕ y ) x ⊕ y = ( x ∨ y ) ⊕ ( x ∧ y ) \begin{aligned} x + y & = \max(x, y) + \min(x, y) \\ |x-y| & = \max(x, y) - \min(x, y) \\ 2 \max(x, y) & = (x + y)+ |x-y| \\ 2 \min(x, y) & = (x + y) - |x-y| \\ \lvert x - y \rvert & = \lvert \max(x, y) - \min(x, y) \rvert \\ \\ x+y & = (x \vee y) + (x \wedge y) \\ x \oplus y & = (x \vee y) - (x \wedge y) \\ 2 (x \vee y) & = (x + y) + (x \oplus y) \\ 2 (x \wedge y) & = (x + y) - (x \oplus y) \\ x \oplus y & = (x \lor y) \oplus (x \land y) \end{aligned} x + y ∣ x − y ∣ 2 max ( x , y ) 2 min ( x , y ) ∣ x − y ∣ x + y x ⊕ y 2 ( x ∨ y ) 2 ( x ∧ y ) x ⊕ y = max ( x , y ) + min ( x , y ) = max ( x , y ) − min ( x , y ) = ( x + y ) + ∣ x − y ∣ = ( x + y ) − ∣ x − y ∣ = ∣ max ( x , y ) − min ( x , y )∣ = ( x ∨ y ) + ( x ∧ y ) = ( x ∨ y ) − ( x ∧ y ) = ( x + y ) + ( x ⊕ y ) = ( x + y ) − ( x ⊕ y ) = ( x ∨ y ) ⊕ ( x ∧ y )
Combinatorial Counting 组合数 定义
( n r ) = n ( n − 1 ) ⋯ ( n − r + 1 ) r ( r − 1 ) ⋯ 1 = n ! r ! ( n − r ) ! \displaystyle \binom{n}{r} = \frac{n (n - 1) \cdots (n - r + 1)}{r (r - 1) \cdots 1} = \frac{n!}{r! (n - r)!} ( r n ) = r ( r − 1 ) ⋯ 1 n ( n − 1 ) ⋯ ( n − r + 1 ) = r ! ( n − r )! n ! ( − n r ) = ( − n ) ( − n − 1 ) ⋯ ( − n − r + 1 ) r ! = ( − 1 ) r ( n + r − 1 r ) \displaystyle \binom{-n}{r} = \dfrac{(-n) (-n - 1) \cdots (-n - r + 1)}{r!} = (-1)^{r} \binom{n + r - 1}{r} ( r − n ) = r ! ( − n ) ( − n − 1 ) ⋯ ( − n − r + 1 ) = ( − 1 ) r ( r n + r − 1 ) (Upper Negation)( n n 1 n 2 … n k ) = ( n n 1 ) ( n − n 1 n 2 ) ⋯ ( n − n 1 − ⋯ − n k − 1 n k ) = n ! n 1 ! n 2 ! … n k ! , \dbinom{n}{n_{1}\ n_2\ \dots\ n_k}=\dbinom{n}{n_{1} }\dbinom{n-n_{1} }{n_2}\cdots \dbinom{n-n_{1}-\dots -n_{k-1} }{n_k}=\dfrac{n!}{n_{1}!\ n_2!\ \dots\ n_k!}, ( n 1 n 2 … n k n ) = ( n 1 n ) ( n 2 n − n 1 ) ⋯ ( n k n − n 1 − ⋯ − n k − 1 ) = n 1 ! n 2 ! … n k ! n ! , 递推定义
( n r ) = n − r + 1 r ( n r − 1 ) = n r ( n − 1 r − 1 ) \displaystyle \binom{n}{r} = \frac{n - r + 1}{r} \binom{n}{r - 1} = \frac{n}{r} \binom{n - 1}{r - 1} ( r n ) = r n − r + 1 ( r − 1 n ) = r n ( r − 1 n − 1 ) ( n r ) = ( n − 1 r − 1 ) + ( n − 1 r ) \displaystyle \binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r} ( r n ) = ( r − 1 n − 1 ) + ( r n − 1 ) 常用求和式
∑ ℓ = 0 N ( ℓ M ) = ( N + 1 M + 1 ) \displaystyle \sum_{\ell = 0}^{N} \binom{\ell}{M} = \binom{N + 1}{M + 1} ℓ = 0 ∑ N ( M ℓ ) = ( M + 1 N + 1 ) (Hockey-stick Identity)∑ k = 0 n ( n k ) = 2 n \displaystyle \sum_{k = 0}^{n} \binom{n}{k} = 2^{n} k = 0 ∑ n ( k n ) = 2 n ∑ k = 0 n ( − 1 ) k ( n k ) = { 1 , n = 0 0 , n > 0 \displaystyle \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} = \begin{cases} 1, & n = 0 \\ 0, & n > 0 \end{cases} k = 0 ∑ n ( − 1 ) k ( k n ) = { 1 , 0 , n = 0 n > 0 ∑ k = 0 n k ( n k ) = n ⋅ 2 n − 1 \displaystyle \sum_{k = 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1} k = 0 ∑ n k ( k n ) = n ⋅ 2 n − 1 ∑ k = 0 ⌊ n / 2 ⌋ ( n − k k ) = Fibonacci ( N + 1 ) \displaystyle \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n - k}{k} = \text{Fibonacci}(N + 1) k = 0 ∑ ⌊ n /2 ⌋ ( k n − k ) = Fibonacci ( N + 1 ) ( n k ) ( k m ) = ( n m ) ( n − m k − m ) \displaystyle \binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n - m}{k - m} ( k n ) ( m k ) = ( m n ) ( k − m n − m ) ∑ k = m n ( n k ) ( k m ) = ( n m ) 2 n − m \displaystyle \sum_{k = m}^{n} \binom{n}{k} \binom{k}{m} = \binom{n}{m} 2^{n - m} k = m ∑ n ( k n ) ( m k ) = ( m n ) 2 n − m ∑ m = 0 n ∑ k = m n ( n k ) ( k m ) = 3 n \displaystyle \sum_{m = 0}^{n} \sum_{k = m}^{n} \binom{n}{k} \binom{k}{m} = 3^{n} m = 0 ∑ n k = m ∑ n ( k n ) ( m k ) = 3 n Binomial Theorem
( 1 + x ) n = ∑ k = 0 n ( n k ) x k \displaystyle (1+x)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} ( 1 + x ) n = k = 0 ∑ n ( k n ) x k ( 1 − x ) − n = ∑ k = 0 ∞ ( − n k ) ( − x ) k = ∑ k = 0 ∞ ( n + k − 1 k ) x k \displaystyle (1-x)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} (-x)^{k} = \sum_{k=0}^{\infty} \binom{n + k - 1}{k} x^{k} ( 1 − x ) − n = k = 0 ∑ ∞ ( k − n ) ( − x ) k = k = 0 ∑ ∞ ( k n + k − 1 ) x k ( x 1 + x 2 + ⋯ + x m ) n = ∑ k 1 + k 2 + ⋯ + k m = n ( n k 1 , k 2 , … , k m ) x 1 k 1 x 2 k 2 … x m k m \displaystyle (x_{1}+x_2+\dots +x_m)^n = \sum_{k_1 + k_2 + \dots + k_m = n} \binom{n}{k_{1}, k_2, \dots, k_m} x_{1}^{k_{1} } x_2^{k_2} \dots x_m^{k_m} ( x 1 + x 2 + ⋯ + x m ) n = k 1 + k 2 + ⋯ + k m = n ∑ ( k 1 , k 2 , … , k m n ) x 1 k 1 x 2 k 2 … x m k m Vandermonde’s Convolution
∑ r = 0 R ( N r ) ( M R − r ) = ( N + M R ) ⇕ ∑ r = 0 R ( − N r ) ( − M R − r ) = ( − N − M R ) ⇕ ∑ r = 0 R ( N + r − 1 r ) ( M + R − r − 1 R − r ) = ( N + M + R − 1 R ) \begin{aligned} \sum_{r=0}^{R} \binom{N}{r} \binom{M}{R-r} &= \binom{N+M}{R} \\ &\Updownarrow \\ \sum_{r=0}^{R} \binom{-N}{r} \binom{-M}{R-r} &= \binom{-N-M}{R} \\ &\Updownarrow \\ \sum_{r=0}^{R} \binom{N+r-1}{r} \binom{M+R-r-1}{R-r} &= \binom{N+M+R-1}{R} \end{aligned} r = 0 ∑ R ( r N ) ( R − r M ) r = 0 ∑ R ( r − N ) ( R − r − M ) r = 0 ∑ R ( r N + r − 1 ) ( R − r M + R − r − 1 ) = ( R N + M ) ⇕ = ( R − N − M ) ⇕ = ( R N + M + R − 1 )
求组合数
m o d \bmod mod N N N 时空 杨辉三角二维递推 任意 较小 O ( N 2 + Q ) O(N^2 + Q) O ( N 2 + Q ) 预处理阶乘 素数 较大且不超过素数 O ( N + log p + Q ) O(N+\log p + Q) O ( N + log p + Q ) 普通 Lucas: 较小的素数 无限制 O ( p + Q log n ) O(p + Q \log n) O ( p + Q log n ) 预处理非素数阶乘 + Legendre 修正 素数幂 较大 O ( N + log p + Q log n ) O(N+\log p + Q \log n) O ( N + log p + Q log n ) 扩展 Lucas 较小的素数幂 无限制 O ( p α + Q log n + Q log p ) O(p^{\alpha} + Q \log n + Q \log p) O ( p α + Q log n + Q log p )
利用 CRT 将素数幂合并,实现任意模数。
球盒模型的四种可能形式 已知将 i i i 个有 / 无标号的小球放入一个盒子里有 a i a_{i} a i 种方案,问将 n n n 个小球放入 k k k 个有 / 无标号的允许为空的盒子,有多少种方案。
设 A ( z ) A(z) A ( z ) 代表单个盒子装小球的方案,具体地,如果小球无标号,使用 OGF A ( z ) = ∑ n = 0 ∞ a n z n \displaystyle A(z) = \sum_{n=0}^{\infty} a_{n} z^{n} A ( z ) = n = 0 ∑ ∞ a n z n ;如果小球有标号,使用 EGF A ( z ) = ∑ n = 0 ∞ a n n ! z n \displaystyle A(z) = \sum_{n=0}^{\infty} \dfrac{a_{n} }{n!}z^{n} A ( z ) = n = 0 ∑ ∞ n ! a n z n 。
根据小球和盒子是否有标号(即是否可区分),分为四种可能形式。
有标号球有标号盒——乘法原理 已知将 i i i 个有标号的小球放入一个盒子里有 a i a_{i} a i 种方案,那么将 n n n 个小球放入 k k k 个有标号的允许为空的盒子的方案数为
n ! [ z n ] ( ∑ n = 0 ∞ a n n ! z n ) k n! [z^{n}] \Bigg(\sum_{n=0}^{\infty} \dfrac{a_{n} }{n!}z^{n} \Bigg)^{k} n ! [ z n ] ( n = 0 ∑ ∞ n ! a n z n ) k
特别地,若 a i = 1 a_{i} = 1 a i = 1 ,方案数是我们熟知的乘法原理 k n k^n k n 。
无标号球有标号盒——插板法 已知将 i i i 个无标号的小球放入一个盒子里有 a i a_{i} a i 种方案,那么将 n n n 个小球放入 k k k 个有标号的允许为空的盒子的方案数为
[ z n ] ( ∑ n = 0 ∞ z n a n ) k [z^{n}] \Bigg(\sum_{n=0}^{\infty} z^{n} a_{n} \Bigg)^{k} [ z n ] ( n = 0 ∑ ∞ z n a n ) k
特别地,若 a i = 1 a_{i} = 1 a i = 1 ,问题化为 x 1 + x 2 + ⋯ + x k = n x_1+x_2+\cdots+x_k=n x 1 + x 2 + ⋯ + x k = n 的非负整数解组数
= [ z n ] 1 ( 1 − z ) k = ( n + k − 1 k − 1 ) = [z^{n}] \frac{1}{(1-z)^{k} } = \binom{n + k - 1}{k - 1} = [ z n ] ( 1 − z ) k 1 = ( k − 1 n + k − 1 )
如果盒子不允许为空,方案数为
[ z n ] ( ∑ n = 1 ∞ z n a n ) k [z^{n}] \Bigg(\sum_{n=1}^{\infty} z^{n} a_{n} \Bigg)^{k} [ z n ] ( n = 1 ∑ ∞ z n a n ) k
特别地,若 a i = 1 a_{i} = 1 a i = 1 ,问题化为 x 1 + x 2 + ⋯ + x k = n x_1+x_2+\cdots+x_k=n x 1 + x 2 + ⋯ + x k = n 的正整数解组数
= [ z n ] z k ( 1 − z ) k = [ z n − k ] 1 ( 1 − z ) k = ( n − 1 k − 1 ) = [z^{n}] \frac{z^{k} }{(1-z)^{k} } = [z^{n - k}] \frac{1}{(1-z)^{k} } = \binom{n - 1}{k - 1} = [ z n ] ( 1 − z ) k z k = [ z n − k ] ( 1 − z ) k 1 = ( k − 1 n − 1 )
无标号球无标号盒——背包问题 / 整数分拆 给定 N N N 种物品,体积分别为 V i V_i V i ,都有无限件。给定 M M M ,对于 m ∈ [ 1 , M ] m\in [1,M] m ∈ [ 1 , M ] ,求用这些物品恰好装 m m m 体积的方案数 m o d 998244353 \bmod 998244353 mod 998244353 。N ⩽ 10 5 , V i ⩽ M ⩽ 10 5 N \leqslant 10^5,V_{i} \leqslant M \leqslant 10^5 N ⩽ 1 0 5 , V i ⩽ M ⩽ 1 0 5 。
设 a i a_{i} a i 表示体积为 i i i 的物品种类数。一个体积为 V i V_{i} V i 的物品可以看作一个能且仅能装 V i V_{i} V i 个无标号小球的盒子。问题化为,已知将 i i i 个无标号的小球放入一个盒子里有 a i a_{i} a i 种方案,问将 n n n 个小球放入任意个无标号的盒子,有多少种方案。
设商品类型构成集合 A \mathcal{A} A ,其 OGF
A ( z ) = ∑ i = 1 N z V i = ∑ k = 1 ∞ z k a k A(z) = \sum_{i=1}^{N} z^{V_{i} } = \sum_{k=1}^{\infty} z^{k} a_{k} A ( z ) = i = 1 ∑ N z V i = k = 1 ∑ ∞ z k a k
问题要求对集合 A \mathcal{A} A 中的对象进行无标号的多重集构造 (Multiset Construction, MSET),其 OGF
B ( z ) = exp ∑ n = 1 ∞ A ( z n ) n B(z) = \exp \sum_{n=1}^{\infty} \frac{A(z^{n})}{n} B ( z ) = exp n = 1 ∑ ∞ n A ( z n )
答案便是 [ z m ] B ( z ) [z^{m}]B(z) [ z m ] B ( z ) ,计算复杂度 O ( M log M ) \mathcal{O}(M\log M) O ( M log M ) 。
如果不了解 MSET 的公式,也可按如下过程推导,
∏ k = 1 M ( ∑ n = 0 ∞ z n k ) f k = ∏ k = 1 M 1 ( 1 − z k ) f k = exp ∑ k = 1 M f k log 1 1 − z k = exp ∑ k = 1 M f k ∑ n = 1 ∞ z n k n = exp ∑ n = 1 ∞ F ( z n ) n \prod_{k=1}^{M} \Bigg(\sum_{n=0}^{\infty} z^{n k} \Bigg)^{f_{k} } = \prod_{k=1}^{M} \frac{1}{(1 - z^{k})^{f_{k} } } = \exp \sum_{k=1}^{M} f_{k} \log \frac{1}{1 - z^{k} } = \exp \sum_{k=1}^{M} f_{k} \sum_{n=1}^{\infty} \frac{z^{n k} }{n} = \exp \sum_{n=1}^{\infty} \frac{F(z^{n})}{n} k = 1 ∏ M ( n = 0 ∑ ∞ z nk ) f k = k = 1 ∏ M ( 1 − z k ) f k 1 = exp k = 1 ∑ M f k log 1 − z k 1 = exp k = 1 ∑ M f k n = 1 ∑ ∞ n z nk = exp n = 1 ∑ ∞ n F ( z n )
特别地,若 a i = 1 a_{i} = 1 a i = 1 ,这就是整数分拆问题。将正整数 n n n 分拆成若干正整数之和的方案数为
p ( n ) = [ z n ] exp ∑ n = 1 ∞ z n n ( 1 − z n ) p(n) = [z^{n}] \exp \sum_{n=1}^{\infty} \frac{z^{n} }{n (1 - z^{n})} p ( n ) = [ z n ] exp n = 1 ∑ ∞ n ( 1 − z n ) z n
设 p ( n , k ) p(n, k) p ( n , k ) 表示将正整数 n n n 分拆成正好 k k k 个正整数之和的方案数,则将正整数 n n n 分拆成正好 k k k 个非负整数之和的方案数为 p ( n + k , k ) p(n + k, k) p ( n + k , k ) 。
这 p ( n , k ) p(n, k) p ( n , k ) 无显式计算公式,但有递归方程
p ( n , k ) = p ( n − 1 , k − 1 ) + p ( n − k , k ) p(n, k) = p(n - 1, k - 1) + p(n - k, k) p ( n , k ) = p ( n − 1 , k − 1 ) + p ( n − k , k )
递归终点 p ( 0 , 0 ) = 1 , p ( n , 0 ) = 0 p(0, 0) = 1, \ p(n, 0) = 0 p ( 0 , 0 ) = 1 , p ( n , 0 ) = 0 。
p ( n , k ) = [ z n ] z k ∑ n = 1 k 1 1 − z n p(n, k) = [z^{n}] z^{k} \sum_{n=1}^{k} \frac{1}{1 - z^{n} } p ( n , k ) = [ z n ] z k n = 1 ∑ k 1 − z n 1
有标号球无标号盒——Second Stirling Numbers 已知将 i i i 个有标号的小球放入一个盒子里有 a i a_{i} a i 种方案,那么将 n n n 个小球放入 k k k 个无标号的不允许为空的盒子(即非空子集)的方案数为
n ! [ z n ] 1 k ! ( ∑ n = 1 ∞ a n n ! z n ) k n! [z^{n}] \dfrac{1}{k!} \Bigg(\sum_{n=1}^{\infty} \dfrac{a_{n} }{n!}z^{n} \Bigg)^{k} n ! [ z n ] k ! 1 ( n = 1 ∑ ∞ n ! a n z n ) k
特别地,若 a i = 1 a_{i} = 1 a i = 1 ,
n ! [ z n ] 1 k ! ( e z − 1 ) k n! [z^{n}] \dfrac{1}{k!} (\mathrm e^{z} - 1 )^{k} n ! [ z n ] k ! 1 ( e z − 1 ) k
这就是第二类斯特林数 S ( n , k ) S(n, k) S ( n , k ) ,其递归方程
S ( n , k ) = S ( n − 1 , k − 1 ) + k ⋅ S ( n − 1 , k ) S(n, k) = S(n - 1, k - 1) + k\cdot S(n - 1, k) S ( n , k ) = S ( n − 1 , k − 1 ) + k ⋅ S ( n − 1 , k )
如果不限制 k k k 的大小,即把 n n n 个球分到任意多个无标号的不允许为空的盒子(即非空子集)中,方案数有非常简洁的形式
n ! [ z n ] ∑ k = 0 ∞ 1 k ! ( e z − 1 ) k = n ! [ z n ] exp ( e z − 1 ) n! [z^{n}] \sum_{k=0}^{\infty} \dfrac{1}{k!} (\mathrm e^{z} - 1 )^{k} = n! [z^{n}] \exp(\mathrm e^{z} - 1) n ! [ z n ] k = 0 ∑ ∞ k ! 1 ( e z − 1 ) k = n ! [ z n ] exp ( e z − 1 )
这就是贝尔数 B n = ∑ k = 0 n S ( n , k ) \displaystyle B_{n} = \sum_{k=0}^{n}S(n, k) B n = k = 0 ∑ n S ( n , k ) 。
设基本组合结构 A \mathcal{A} A 的 EGF A ( z ) A(z) A ( z ) ,那么由这些基本结构 A \mathcal{A} A 组成的集合 B \mathcal{B} B 的 EGF B ( z ) B(z) B ( z ) 满足
B ( z ) = exp A ( z ) B(z) = \exp A(z) B ( z ) = exp A ( z )
第一类无符号斯特林数 s u ( n , k ) s_{u}(n, k) s u ( n , k ) 表示将一个长为 n n n 置换划分为 k k k 个轮换的方法数,递归方程
s u ( n , k ) = s u ( n − 1 , k − 1 ) + ( n − 1 ) ⋅ s u ( n − 1 , k ) s_{u}(n, k) = s_{u}(n - 1, k - 1) + (n - 1) \cdot s_{u}(n - 1, k) s u ( n , k ) = s u ( n − 1 , k − 1 ) + ( n − 1 ) ⋅ s u ( n − 1 , k )
OGF
x n ↑ = ∑ k = 0 n s u ( n , k ) x k x^{n \uparrow} = \sum_{k=0}^{n} s_{u}(n, k) x^{k} x n ↑ = k = 0 ∑ n s u ( n , k ) x k
第一类有符号斯特林数 s s ( n , k ) = ( − 1 ) n − k s u ( n , k ) s_{s}(n, k) = (-1)^{n-k} s_{u}(n, k) s s ( n , k ) = ( − 1 ) n − k s u ( n , k ) 的 OGF
x n ↓ = ∑ k = 0 n s s ( n , k ) x k x^{n \downarrow} = \sum_{k=0}^{n} s_{s}(n, k) x^{k} x n ↓ = k = 0 ∑ n s s ( n , k ) x k
对于一个排列 p p p ,我们总是能构造出另一个排列 q q q ,使得 p p p 的置换环最大元素的集合,恰好等于 q q q 的前缀最大值的集合。反过来,对于一个排列 p p p ,我们也总能构造出另一个排列 q q q ,使得 p p p 的前缀最大值的集合,恰好等于 q q q 的置换环最大元素的集合。
给定 N , K N,K N , K 和集合 T = ( T 1 , T 2 , … , T K ) T = (T_{1}, T_{2}, \dots, T_{K}) T = ( T 1 , T 2 , … , T K ) ,满足集合 S S S 内的元素恰为排列 q ∈ S N q \in S_{N} q ∈ S N 的前缀最大值的排列 q ∈ S N q \in S_{N} q ∈ S N 的个数为
∏ j = 1 , j ∉ T K ( N − j ) \prod_{j = 1, j \notin T}^{K} (N - j) j = 1 , j ∈ / T ∏ K ( N − j )
若 T K ≠ N T_{K} \neq N T K = N ,上式自然为 0。
给定 N , K N,K N , K 和集合 T = ( T 1 = 1 , T 2 , … , T K ) T = (T_{1} = 1, T_{2}, \dots, T_{K}) T = ( T 1 = 1 , T 2 , … , T K ) ,满足排列 q q q 的前缀最大值的下标恰好构成集合 S S S 的排列 q ∈ S N q \in S_{N} q ∈ S N 的个数为
( N − 1 ) ! ∏ j = 2 K ( T j − 1 ) \dfrac{(N - 1)!}{\prod_{j=2}^{K}(T_{j} - 1)} ∏ j = 2 K ( T j − 1 ) ( N − 1 )!
Number Theory Lifting The Exponent Lemma (LTE) Let p ≠ 2 p \neq 2 p = 2 ,
p ∣ x − y , p ∤ x ⟹ ν p ( x n − y n ) = ν p ( x − y ) + ν p ( n ) 2 ∤ n , p ∣ x + y , p ∤ x ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n ) \begin{aligned} p \mid x - y, \ p \nmid x & \implies \nu_p(x^n-y^n)=\nu_p(x-y) + \nu_{p}(n) \\ 2 \nmid n, \ p \mid x + y, \ p \nmid x & \implies \nu_p(x^n+y^n)=\nu_p(x+y) + \nu_{p}(n) \end{aligned} p ∣ x − y , p ∤ x 2 ∤ n , p ∣ x + y , p ∤ x ⟹ ν p ( x n − y n ) = ν p ( x − y ) + ν p ( n ) ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n )
Let p = 2 p = 2 p = 2 ,
2 ∤ n , 2 ∤ x , 2 ∤ y ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) 2 ∣ n , 2 ∤ x , 2 ∤ y ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ν 2 ( n ) − 1 2 ∤ n , 2 ∤ x , 2 ∤ y ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n ) \begin{aligned} 2 \nmid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_2(x^n-y^n)=\nu_2(x-y) \\ 2 \mid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1 \\ 2 \nmid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_p(x^n+y^n)=\nu_p(x+y) + \nu_{p}(n) \end{aligned} 2 ∤ n , 2 ∤ x , 2 ∤ y 2 ∣ n , 2 ∤ x , 2 ∤ y 2 ∤ n , 2 ∤ x , 2 ∤ y ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) ⟹ ν 2 ( x n − y n ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ν 2 ( n ) − 1 ⟹ ν p ( x n + y n ) = ν p ( x + y ) + ν p ( n )
Proof. 设 n = 2 k m n=2^k m n = 2 k m ,其中 k = ν 2 ( n ) ≥ 1 k = \nu_2(n)\ge1 k = ν 2 ( n ) ≥ 1 ,m m m 为奇数。 令 A = x 2 k , B = y 2 k A=x^{2^k},B=y^{2^k} A = x 2 k , B = y 2 k ,由 A m − B m = ( A − B ) ( A m − 1 + A m − 2 B + ⋯ + B m − 1 ) A^m-B^m=(A-B)(A^{m-1}+A^{m-2}B+\cdots+B^{m-1}) A m − B m = ( A − B ) ( A m − 1 + A m − 2 B + ⋯ + B m − 1 ) ,括号内是 m m m 个奇数之和,故为奇数。因此 ν 2 ( x n − y n ) = ν 2 ( x 2 k − y 2 k ) \nu_2(x^n-y^n)=\nu_2(x^{2^k}-y^{2^k}) ν 2 ( x n − y n ) = ν 2 ( x 2 k − y 2 k ) 。 用平方差公式 x 2 k − y 2 k = ( x − y ) ( x + y ) ∏ j = 1 k − 1 ( x 2 j + y 2 j ) x^{2^k}-y^{2^k}=(x-y)(x+y)\prod_{j=1}^{k-1}(x^{2^j}+y^{2^j}) x 2 k − y 2 k = ( x − y ) ( x + y ) ∏ j = 1 k − 1 ( x 2 j + y 2 j ) 展开,ν 2 ( x 2 k − y 2 k ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ∑ j = 1 k − 1 ν 2 ( x 2 j + y 2 j ) \nu_2(x^{2^k}-y^{2^k})=\nu_2(x-y) + \nu_2(x+y) + \sum_{j=1}^{k-1}\nu_2(x^{2^j}+y^{2^j}) ν 2 ( x 2 k − y 2 k ) = ν 2 ( x − y ) + ν 2 ( x + y ) + ∑ j = 1 k − 1 ν 2 ( x 2 j + y 2 j ) 。 考虑到奇数的平方模 8 8 8 余 1 1 1 ,所以对每个 j ≥ 1 j\ge1 j ≥ 1 ,都有 x 2 j + y 2 j ≡ 1 + 1 = 2 ( m o d 8 ) x^{2^j}+y^{2^j}\equiv 1+1=2\pmod8 x 2 j + y 2 j ≡ 1 + 1 = 2 ( mod 8 ) ,即 ν 2 ( x 2 j + y 2 j ) = 1 \nu_2 (x^{2^j}+y^{2^j})=1 ν 2 ( x 2 j + y 2 j ) = 1 ,代回原式即证。
Ex 求 M = ∑ i = 1 n v 5 ( i ! ) \displaystyle M=\sum_{i=1}^{n}v_5(i!) M = i = 1 ∑ n v 5 ( i !) 。([VJwin6H - 阶乘之乘](https: //www.luogu.com.cn/problem/P2388 ))
M = ∑ i = 1 n v 5 ( i ! ) = ∑ i = 1 n ∑ k = 1 5 k ≤ i ⌊ i 5 k ⌋ = ∑ k = 1 5 k ≤ n ∑ i = 1 n ⌊ i 5 k ⌋ = ∑ k = 1 5 k ≤ n [ 5 k + 2 ⋅ 5 k + ⋯ + ( ⌊ n 5 k ⌋ − 1 ) ⋅ 5 k + ⌊ n 5 k ⌋ ( n m o d 5 k + 1 ) ] = ∑ k = 1 5 k ≤ n [ 5 k 2 ⌊ n 5 k ⌋ ( ⌊ n 5 k ⌋ − 1 ) + ⌊ n 5 k ⌋ ( n m o d 5 k + 1 ) ] = ∑ 5 ≤ i = 5 k ≤ n [ i 2 ⌊ n i ⌋ ( ⌊ n i ⌋ − 1 ) + ⌊ n i ⌋ ( n m o d i + 1 ) ] \begin{align} M &= \sum_{i=1}^{n}v_5(i!) = \sum_{i=1}^{n}\sum_{k=1}^{5^k\le i}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor = \sum_{k=1}^{5^k\le n}\sum_{i=1}^{n}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor \\ &= \sum_{k=1}^{5^k\le n}\bigg[ 5^k +2\cdot5^k +\dots +\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg)\cdot5^k +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{k=1}^{5^k\le n}\bigg[\frac{5^k}{2}\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{5\le i=5^k\le n}^{}\bigg[\frac{i}{2}\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{i}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\Big(n\bmod{i}+1\Big) \bigg] \\ \end{align} M = i = 1 ∑ n v 5 ( i !) = i = 1 ∑ n k = 1 ∑ 5 k ≤ i ⌊ 5 k i ⌋ = k = 1 ∑ 5 k ≤ n i = 1 ∑ n ⌊ 5 k i ⌋ = k = 1 ∑ 5 k ≤ n [ 5 k + 2 ⋅ 5 k + ⋯ + ( ⌊ 5 k n ⌋ − 1 ) ⋅ 5 k + ⌊ 5 k n ⌋ ( n mod 5 k + 1 ) ] = k = 1 ∑ 5 k ≤ n [ 2 5 k ⌊ 5 k n ⌋ ( ⌊ 5 k n ⌋ − 1 ) + ⌊ 5 k n ⌋ ( n mod 5 k + 1 ) ] = 5 ≤ i = 5 k ≤ n ∑ [ 2 i ⌊ i n ⌋ ( ⌊ i n ⌋ − 1 ) + ⌊ i n ⌋ ( n mod i + 1 ) ]
Arithmetic Functions 通俗地讲,input 是 integer 的 function,即 Arithmetic Function。
Completely Multiplicative For all x , y x, y x , y , f ( x y ) = f ( x ) f ( y ) f(x y) = f(x) f(y) f ( x y ) = f ( x ) f ( y ) . f ( n ) = ∏ p ∣ n [ f ( p ) ] ν p ( n ) \displaystyle f(n) = \prod_{p \mid n} [f(p)]^{\nu_{p}(n)} f ( n ) = p ∣ n ∏ [ f ( p ) ] ν p ( n ) .If f f f and g g g are completely multiplicative, then so are f ( n k ) f(n^{k}) f ( n k ) , [ f ( n ) ] k [f(n)]^{k} [ f ( n ) ] k , ( f ⋅ g ) ( n ) = f ( n ) g ( n ) (f \cdot g)(n) = f(n)g(n) ( f ⋅ g ) ( n ) = f ( n ) g ( n ) , ( f ∗ g ) ( n ) (f \ast g)(n) ( f ∗ g ) ( n ) . Examples :
Unit Function I ( n ) = [ n = 1 ] I(n) = [n = 1] I ( n ) = [ n = 1 ] Identity for Dirichlet convolution, 类比单位矩阵 Power Function id k ( n ) = n k \operatorname{id}_{k}(n) = n^{k} id k ( n ) = n k Constant Function id 0 ( n ) = 1 ( n ) = 1 \operatorname{id}_{0}(n) = 1(n) = 1 id 0 ( n ) = 1 ( n ) = 1 Identity Function id 1 ( n ) = n \operatorname{id}_{1}(n) = n id 1 ( n ) = n Multiplicative For all x ⊥ y x \perp y x ⊥ y , f ( x y ) = f ( x ) f ( y ) f(x y) = f(x) f(y) f ( x y ) = f ( x ) f ( y ) . f ( n ) = ∏ p ∣ n f ( p ν p ( n ) ) \displaystyle f(n) = \prod_{p \mid n} f(p^{\nu_{p}(n)}) f ( n ) = p ∣ n ∏ f ( p ν p ( n ) ) .f ( p ν p ( n ) ) ≠ [ f ( p ) ] ν p ( n ) \displaystyle f(p^{\nu_{p}(n)}) \neq [f(p)]^{\nu_{p}(n)} f ( p ν p ( n ) ) = [ f ( p ) ] ν p ( n ) .If f f f and g g g are multiplicative, then so are f ( n k ) f(n^{k}) f ( n k ) , f k ( n ) f^{k}(n) f k ( n ) , ( f ⋅ g ) ( n ) = f ( n ) g ( n ) (f \cdot g)(n) = f(n)g(n) ( f ⋅ g ) ( n ) = f ( n ) g ( n ) , ( f ∗ g ) ( n ) (f \ast g)(n) ( f ∗ g ) ( n ) . Examples :
Divisor Function σ k ( n ) = ∑ d ∣ n d k \displaystyle \sigma_{k}(n) = \sum_{d \mid n} d^{k} σ k ( n ) = d ∣ n ∑ d k 约数个数 (Number of Divisors): τ ( n ) = σ 0 ( n ) = ∑ d ∣ n 1 = ∏ p ∣ n ( ν p ( n ) + 1 ) \displaystyle \tau(n) = \sigma_0(n) = \sum_{d \mid n} 1 = \prod_{p \mid n} \big(\nu_{p}(n) + 1\big) τ ( n ) = σ 0 ( n ) = d ∣ n ∑ 1 = p ∣ n ∏ ( ν p ( n ) + 1 ) 约数和 (Sum of Divisors): σ ( n ) = σ 1 ( n ) = ∑ d ∣ n d = ∏ p ∣ n p ν p ( n ) + 1 − 1 p − 1 \displaystyle \sigma(n) = \sigma_1(n) = \sum_{d \mid n} d = \prod_{p \mid n} \frac{p^{\nu_{p}(n)+1} - 1}{p - 1} σ ( n ) = σ 1 ( n ) = d ∣ n ∑ d = p ∣ n ∏ p − 1 p ν p ( n ) + 1 − 1 Möbius Function μ ( n ) = { 1 , n = 1 0 , ∃ d > 1 , d 2 ∣ n ( − 1 ) ω ( n ) , otherwise \mu(n) = \begin{cases} 1, & n = 1 \\ 0, & \exists d > 1, d^{2} \mid n \\ (-1)^{\omega(n)}, & \text{otherwise} \end{cases} μ ( n ) = ⎩ ⎨ ⎧ 1 , 0 , ( − 1 ) ω ( n ) , n = 1 ∃ d > 1 , d 2 ∣ n otherwise μ = 1 − 1 ⟺ μ ∗ 1 = I ⟺ ∑ d ∣ n μ ( d ) = [ n = 1 ] = I ( n ) \mu = 1^{-1} \iff \mu * 1 = I \iff \displaystyle \sum_{d \mid n} \mu(d) = [n = 1] = I(n) μ = 1 − 1 ⟺ μ ∗ 1 = I ⟺ d ∣ n ∑ μ ( d ) = [ n = 1 ] = I ( n ) ∑ d ∣ n , d ∣ m μ ( d ) = [ n ⊥ m ] \displaystyle \sum_{d \mid n, d \mid m} \mu(d) = [n \perp m] d ∣ n , d ∣ m ∑ μ ( d ) = [ n ⊥ m ] Ex . S = ∑ n = 1 M ∑ m = 1 M [ n ⊥ m ] = ∑ n = 1 M ∑ m = 1 M ∑ d ∣ gcd ( n , m ) μ ( d ) = ∑ n = 1 M ∑ m = 1 M ∑ d = 1 M [ d ∣ n ] [ d ∣ m ] μ ( d ) = ∑ d = 1 M μ ( d ) ∑ n = 1 M [ d ∣ n ] ∑ m = 1 M [ d ∣ m ] = ∑ d = 1 M μ ( d ) ⌊ M d ⌋ ⌊ M d ⌋ \displaystyle S = \sum_{n=1}^{M}\sum_{m=1}^{M}[n \perp m] = \sum_{n=1}^{M}\sum_{m=1}^{M}\sum_{d\mid\gcd(n, m)}\mu(d) = \sum_{n=1}^{M}\sum_{m=1}^{M}\sum_{d=1}^{M}[d \mid n][d \mid m]\mu(d) = \sum_{d=1}^{M}\mu(d)\sum_{n=1}^{M}[d \mid n]\sum_{m=1}^{M}[d \mid m] = \sum_{d=1}^{M}\mu(d)\Big\lfloor\frac{M}{d}\Big\rfloor\Big\lfloor\frac{M}{d}\Big\rfloor S = n = 1 ∑ M m = 1 ∑ M [ n ⊥ m ] = n = 1 ∑ M m = 1 ∑ M d ∣ g c d ( n , m ) ∑ μ ( d ) = n = 1 ∑ M m = 1 ∑ M d = 1 ∑ M [ d ∣ n ] [ d ∣ m ] μ ( d ) = d = 1 ∑ M μ ( d ) n = 1 ∑ M [ d ∣ n ] m = 1 ∑ M [ d ∣ m ] = d = 1 ∑ M μ ( d ) ⌊ d M ⌋ ⌊ d M ⌋ Euler’s Totient Function φ ( n ) = ∑ i = 1 n [ i ⊥ n ] = n ∏ p ∣ n ( 1 − 1 p ) \displaystyle \varphi(n) = \sum_{i=1}^n [i \perp n] = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) φ ( n ) = i = 1 ∑ n [ i ⊥ n ] = n p ∣ n ∏ ( 1 − p 1 ) — 1 ∼ n 1\sim n 1 ∼ n 中与 n n n 互素的数量∑ i = 1 n i [ i ⊥ n ] = n φ ( n ) 2 ( n > 1 ) \displaystyle \sum_{i=1}^{n} i \ [i \perp n] = \frac{n\varphi(n)}{2} \quad (n > 1) i = 1 ∑ n i [ i ⊥ n ] = 2 n φ ( n ) ( n > 1 ) — 1 ∼ n 1\sim n 1 ∼ n 中与 n n n 互素的数之和φ = id ∗ μ ⟺ φ ∗ 1 = id ⟺ ∑ d ∣ n φ ( d ) = n \displaystyle \varphi = \text{id} \ast \mu \iff \varphi \ast 1 = \text{id} \iff \sum_{d \mid n} \varphi(d) = n φ = id ∗ μ ⟺ φ ∗ 1 = id ⟺ d ∣ n ∑ φ ( d ) = n ∑ d ∣ n , d ∣ m φ ( d ) = ( n , m ) \displaystyle\sum_{d \mid n, d \mid m} \varphi(d) = (n, m) d ∣ n , d ∣ m ∑ φ ( d ) = ( n , m ) Ex . S = ∑ n = 1 N gcd ( n , N ) = ∑ n = 1 N ∑ d ∣ gcd ( n , N ) ϕ ( d ) = ∑ d = 1 N ∑ n = 1 N [ d ∣ n ] [ d ∣ N ] ϕ ( d ) = ∑ d = 1 N ⌊ N d ⌋ [ d ∣ N ] ϕ ( d ) = ∑ d ∣ N ⌊ N d ⌋ ϕ ( d ) \displaystyle S = \sum_{n=1}^{N} \gcd(n,N) = \sum_{n=1}^{N} \sum_{d\mid \gcd(n, N)} \phi(d) = \sum_{d=1}^{N} \sum_{n=1}^{N} [d\mid n][d\mid N]\phi(d) = \sum_{d=1}^{N} \left\lfloor \frac{N}{d} \right\rfloor [d\mid N]\phi(d) = \sum_{d\mid N} \left\lfloor \frac{N}{d} \right\rfloor \phi(d) S = n = 1 ∑ N g cd( n , N ) = n = 1 ∑ N d ∣ g c d ( n , N ) ∑ ϕ ( d ) = d = 1 ∑ N n = 1 ∑ N [ d ∣ n ] [ d ∣ N ] ϕ ( d ) = d = 1 ∑ N ⌊ d N ⌋ [ d ∣ N ] ϕ ( d ) = d ∣ N ∑ ⌊ d N ⌋ ϕ ( d ) Additive For all x ⊥ y x \perp y x ⊥ y , f ( x y ) = f ( x ) + f ( y ) f(x y) = f(x) + f(y) f ( x y ) = f ( x ) + f ( y ) . Example : 不同素因子个数 ω ( n ) \omega(n) ω ( n ) ,在 n ≤ 10 9 n \le 10^{9} n ≤ 1 0 9 的范围内,ω ( n ) \omega(n) ω ( n ) 的最大值为 9Completely Additive For all x , y x, y x , y , f ( x y ) = f ( x ) + f ( y ) f(x y) = f(x) + f(y) f ( x y ) = f ( x ) + f ( y ) . Example : 所有素因子个数 (计重) Ω ( n ) \Omega(n) Ω ( n ) Theorems Prime Number Prime Number Theorem. lim n → ∞ π ( n ) n / ln ( n ) = 1 \displaystyle \lim_{n \to \infty} \dfrac{\pi(n)}{n/\ln(n)} = 1 n → ∞ lim n / ln ( n ) π ( n ) = 1 Density of Square-free Integers. The number of square-free integers Q ( n ) Q(n) Q ( n ) up to n n n satisfies: lim n → ∞ Q ( n ) n = 6 π 2 = 1 ζ ( 2 ) \displaystyle \lim_{n \to \infty} \dfrac{Q(n)}{n} = \frac{6}{\pi^{2}} = \frac{1}{\zeta(2)} n → ∞ lim n Q ( n ) = π 2 6 = ζ ( 2 ) 1 Chebyshev’s Theorem. For every integer n > 1 n > 1 n > 1 , there exists at least one prime p p p such that n < p < 2 n n < p < 2n n < p < 2 n . (2025 Shenyang C)Twin Prime Conjecture. There are infinitely many pairs of primes ( p , p + 2 ) (p, p+2) ( p , p + 2 ) .Dirichlet’s Theorem on Arithmetic Progressions. For any two coprime positive integers a a a and d d d , the arithmetic progression a , a + d , a + 2 d , a + 3 d , … a, a+d, a+2d, a+3d, \dots a , a + d , a + 2 d , a + 3 d , … contains infinitely many prime numbers.Green-Tao Theorem. The set of prime numbers contains arbitrarily long arithmetic progressions a , a + d , a + 2 d , a + 3 d , … a, a+d, a+2d, a+3d, \dots a , a + d , a + 2 d , a + 3 d , …