C/C++教程
《算法竞赛中的初等数论》（四）正文 0x40反演（ACM / OI / MO）（十五万字符数论书）
整理的算法模板合集： ACM模板
点我看算法全家桶系列！！！
实际上是一个全新的精炼模板整合计划
写在最前面：本文部分内容来自网上各大博客或是各类图书，由我个人整理，增加些许见解，仅做学习交流使用，无任何商业用途。因个人实力时间等原因，本文并非完全原创，请大家见谅。
目录
- 0x40 反演
- 0x41 整除分块
- 0x41.1 前置知识
- 0x41.2 整除分块
- 0x42 莫比乌斯反演
- 0x42.1 莫比乌斯反演公式
- 0x42.2 莫比乌斯反演证明
- 0x42.3 推导结论
- 0x42.4 竞赛例题选讲
- 0x42.5 莫比乌斯反演扩展
- 0x43 欧拉反演
- 0x44 二项式反演[^1]
- 0x45 斯特林反演
- 0x46 单位根反演
- 0x47 子集反演
- 0x48 最值反演 ( Min - Max 容斥)
- 0x49 拉格朗日反演
- 0x4A 反演常用技巧
- 0x4B. Dirichlet 前缀和
- 0x4B.1 Dirichlet 前缀和
- 0x4B.2 Dirichlet 后缀和
- 0x4B.2 倒推 Dirichlet 前缀和
- 0x4B.3 倒推 Dirichlet 后缀和
0x40 反演
0x41 整除分块
0x41.1 前置知识
引理 1
∀ a , b , c ∈ Z , ⌊ a b c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ \forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor ∀a,b,c∈Z,⌊bca⌋=⌊c⌊ba⌋⌋
证明
a b = ⌊ a b ⌋ + r ( 0 ≤ r < 1 ) ⟹ ⌊ a b c ⌋ = ⌊ a b ⋅ 1 c ⌋ = ⌊ 1 c ( ⌊ a b ⌋ + r ) ⌋ = ⌊ ⌊ a b ⌋ c + r c ⌋ = ⌊ ⌊ a b ⌋ c ⌋ □ \begin{aligned} &\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\\ \implies &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\\ &&\square \end{aligned} ⟹ba=⌊ba⌋+r(0≤r<1)⌊bca⌋=⌊ba⋅c1⌋=⌊c1(⌊ba⌋+r)⌋=⌊c⌊ba⌋+cr⌋=⌊c⌊ba⌋⌋□
引理 2
∀ n ∈ N + , ∣ { ⌊ n d ⌋ ∣ d ∈ N + , d ≤ n } ∣ ≤ ⌊ 2 n ⌋ \forall n \in \mathbb{N}_{+}, \left|\left\{ \left\lfloor \frac{n}{d} \right\rfloor \mid d \in \mathbb{N}_{+},d\leq n \right\}\right| \leq \left \lfloor 2\sqrt{n} \right\rfloor ∀n∈N+,∣∣∣{⌊dn⌋∣d∈N+,d≤n}∣∣∣≤⌊2n ⌋
∣ V ∣ |V| ∣V∣ 表示集合 V V V 的元素个数
证明
对于 0 ≤ d ≤ ⌊ n ⌋ 0\le d\leq \left\lfloor\sqrt{n}\right\rfloor 0≤d≤⌊n ⌋，显然一共最多只有 n \sqrt n n 种 d d d，显然 ⌊ n d ⌋ \left\lfloor\dfrac{n}{d}\right\rfloor ⌊dn⌋ 有 ⌊ n ⌋ \left\lfloor\sqrt{n}\right\rfloor ⌊n ⌋ 种取值。
对于 d > ⌊ n ⌋ d> \left\lfloor\sqrt{n}\right\rfloor d>⌊n ⌋，有 0 ≤ ⌊ n d ⌋ ≤ ⌊ n ⌋ 0\le \left\lfloor\dfrac{n}{d}\right\rfloor\leq\left\lfloor\sqrt{n}\right\rfloor 0≤⌊dn⌋≤⌊n ⌋，显然也只有 ⌊ n ⌋ \left\lfloor\sqrt{n}\right\rfloor ⌊n ⌋ 种取值
综上，得证 □ \ \square □
0x41.2 整除分块
我们在计算 ∑ i = 1 n ⌊ n i ⌋ \displaystyle \sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor i=1∑n⌊in⌋ 的时候，如果直接枚举的话，复杂度是 O ( n ) O(n) O(n) 的，在 n n n 很大的时候是很难计算的。但是当我们打表找规律的时候，发现序列 ⌊ n i ⌋ \left\lfloor\dfrac{n}{i}\right\rfloor ⌊in⌋ 中有很多是相同的！（因为我们这里是下取整的形式，会丢掉所有小数），我们考虑对于元素相同的段 O ( 1 ) O(1) O(1) 计算，即求出该段的长度，然后乘上该段的值显然就是该段的和。
因此我们考虑对于含有 ⌊ n i ⌋ \left\lfloor\dfrac{n}{i}\right\rfloor ⌊in⌋ 的求和式子（ n n n 为给定的常数）
对于任意一个 i ( i ≤ n ) i(i\leq n) i(i≤n)，我们需要找到一个最大的 j ( i ≤ j ≤ n ) j(i\leq j\leq n) j(i≤j≤n)，使得 ⌊ n i ⌋ = ⌊ n j ⌋ \left\lfloor\dfrac{n}{i}\right\rfloor = \left\lfloor\dfrac{n}{j}\right\rfloor ⌊in⌋=⌊jn⌋，显然此时的 i , j i,j i,j 就是这段值相等的序列。
由引理1显然可以得到 j = ⌊ n ⌊ n i ⌋ ⌋ j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor j=⌊⌊in⌋n⌋ （这里的除法都是下取整）
显然 j ≤ n j\leq n j≤n，考虑证明 j ≥ i j\geq i j≥i：
⌊ n i ⌋ ≤ n i ⟹ ⌊ n ⌊ n i ⌋ ⌋ ≥ ⌊ n n i ⌋ = ⌊ i ⌋ = i ⟹ i ≤ ⌊ n ⌊ n i ⌋ ⌋ = j □ \begin{aligned} &\left\lfloor\frac{n}{i}\right\rfloor \leq \frac{n}{i}\\ \implies &\left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \geq \left\lfloor\frac{n}{ \frac{n}{i} }\right\rfloor = \left\lfloor i \right\rfloor=i \\ \implies &i\leq \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor=j\\ &&\square \end{aligned} ⟹⟹⌊in⌋≤in⌊⌊in⌋n⌋≥⌊inn⌋=⌊i⌋=ii≤⌊⌊in⌋n⌋=j□
不妨设 k = ⌊ n i ⌋ k=\left\lfloor\dfrac{n}{i}\right\rfloor k=⌊in⌋，考虑证明当 ⌊ n j ⌋ = k \left\lfloor\dfrac{n}{j}\right\rfloor=k ⌊jn⌋=k 时， j j j 的最大值为 ⌊ n k ⌋ \left\lfloor\dfrac{n}{k}\right\rfloor ⌊kn⌋：
⌊ n j ⌋ = k ⟺ k ≤ n j < k + 1 ⟺ 1 k + 1 < j n ≤ 1 k ⟺ n k + 1 < j ≤ n k \left\lfloor\frac{n}{j}\right\rfloor=k \iff k\leq\frac{n}{j}<k+1 \iff \frac{1}{k+1}<\frac{j}{n}\leq\frac{1}{k} \iff \frac{n}{k+1}<j\leq\dfrac{n}{k} ⌊jn⌋=k⟺k≤jn<k+1⟺k+11<nj≤k1⟺k+1n<j≤kn
又因为 j j j 为整数 所以 j max = ⌊ n k ⌋ = ⌊ n ⌊ n i ⌋ ⌋ j_{\max}=\left\lfloor\dfrac{n}{k}\right\rfloor=\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor jmax=⌊kn⌋=⌊⌊in⌋n⌋
综上所诉，值相等的区间为 [ i , j ] = [ i , ⌊ n ⌊ n i ⌋ ⌋ ] [i,j]=[i,\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor] [i,j]=[i,⌊⌊in⌋n⌋]
综上所述，我们每次以 [ i , j ] [i,j] [i,j] 为一块，分块求和即可。
Code
for(ll l = 1, r;l <= n; l = r + 1){
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}
根据 引理2 ，显然该过程的时间复杂度为 O ( n ) O(\sqrt n) O(n )
二维数论分块
∑ i = 1 min ( n , m ) ⌊ n i ⌋ ⌊ m i ⌋ \sum_{i=1}^{\min (n,m)}\left\lfloor\frac{n}{i} \right\rfloor\left\lfloor\frac{m}{i} \right\rfloor i=1∑min(n,m)⌊in⌋⌊im⌋
每次右边界取 min ( ⌊ n ⌊ n i ⌋ ⌋ , ⌊ m ⌊ m i ⌋ ⌋ ) \displaystyle \min(\left\lfloor\cfrac{n}{\lfloor \frac{n}{i}\rfloor}\right\rfloor,\left\lfloor\frac{m}{\lfloor \frac{m}{i}\rfloor}\right\rfloor) min(⌊⌊in⌋n⌋,⌊⌊im⌋m⌋)，保证了两者分别相等，所以每两项的乘积相等。复杂度并没有变化。
Code
for(ll l = 1, r;l <= min(n, m); l = r + 1){
r = min(n / (n / i), m / (m / i));
ans += (r - l + 1) * (n / l);
}
Example A
计算
∑
i
=
1
n
i
⌊
n
i
⌋
\displaystyle \sum\limits_{i=1}^{n}i\left\lfloor\frac{n}{i}\right\rfloor
i=1∑ni⌊in⌋
Solution
对于每个块均有：
∑ i = l r i ⌊ n i ⌋ = ∑ i = l r i ⌊ n l ⌋ = ⌊ n l ⌋ ∑ i = l r i = ⌊ n l ⌋ × ( r − l + 1 ) ( l + r ) 2 \begin{aligned}\displaystyle \sum\limits_{i=l}^{r}i\left\lfloor \frac{n}{i}\right\rfloor&=\sum\limits_{i=l}^{r}i\left\lfloor \frac{n}{l}\right\rfloor&\\&=\left\lfloor \frac{n}{l}\right\rfloor\sum\limits_{i=l}^{r}i&\\&=\left\lfloor \frac{n}{l}\right\rfloor\times\frac{(r-l+1)(l+r)}{2}\end{aligned} i=l∑ri⌊in⌋=i=l∑ri⌊ln⌋=⌊ln⌋i=l∑ri=⌊ln⌋×2(r−l+1)(l+r)
Example B
计算
∑
i
=
1
n
i
2
⌊
n
i
⌋
\sum_{i=1}^{n}i^{2}\left \lfloor \frac{n}{i} \right \rfloor
i=1∑ni2⌊in⌋
Solution
同样可以整除分块，只不过把等差数列求和公式换成平方数列求和的公式
Code
int cal(int x){
return x * (x + 1) * (2 * x + 1) / 6;
}
int n, ans;
signed main(){
cin >> n;
for(int l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
ans += (cal(r) - cal(l - 1)) * (n / l);
}
printf("%lld\n", ans);
}
Example C
计算
∑
k
=
1
n
∑
k
∣
x
n
x
\sum^{n}_{k=1}\sum^{n}_{k|x}x
k=1∑nk∣x∑nx
Solution
显然它的实际意义就是求 k k k 在 [ 1 , n ] [1,n] [1,n] 内的所有倍数和。
即对于每个 k , n k,n k,n 里会存在 ⌊ n k ⌋ \left \lfloor \dfrac{n}{k} \right \rfloor ⌊kn⌋ 个 k k k 的倍数，而且是一个等差数列，公差为 k k k。所以式可以写成
∑ k = 1 n k ( ⌊ n k ⌋ + 1 ) ⌊ n k ⌋ 2 \sum^{n}_{k=1}\frac{k(\left \lfloor \frac{n}{k} \right \rfloor+1)\left \lfloor \frac{n}{k} \right \rfloor}{2} k=1∑n2k(⌊kn⌋+1)⌊kn⌋
显然可以直接整除分块：
int n, ans1, ans2;
signed main(){
cin >> n;
for(int k = 1;k <= n; ++ k)
for(int j = 1;j * k <= n; ++ j)
ans1 += j * k;
for(int l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
ans2 += (l + r) * (r - l + 1) / 2 * (1 + n / l) * (n / l) / 2;
}
printf("%lld %lld\n", ans1, ans2);
}
Example E
计算
∑
i
=
1
n
⌈
n
i
⌉
\displaystyle \sum\limits_{i=1}^{n}\left\lceil\frac{n}{i}\right\rceil
i=1∑n⌈in⌉
Solution
⌈ n i ⌉ = { ⌊ n i ⌋ i ∣ n ⌊ n i ⌋ + 1 i ∤ n \displaystyle \left\lceil\frac{n}{i}\right\rceil=\begin{cases}\left\lfloor\frac{n}{i}\right\rfloor&i\mid n\\\left\lfloor\frac{n}{i}\right\rfloor+1&i\nmid n\end{cases} ⌈in⌉={⌊in⌋⌊in⌋+1i∣ni∤n
一共有 d ( n ) d(n) d(n) （表示 n n n 的因数个数）个数满足 i ∣ n i\mid n i∣n ，我们计算全部都不能整除时的结果，最后减去因数个数。
∑ i = 1 n ⌈ n i ⌉ = ∑ i = 1 n ( ⌊ n i ⌋ + 1 ) − d ( n ) = n − d ( n ) + ∑ i = 1 n ⌊ n i ⌋ \begin{aligned}\sum\limits_{i=1}^{n}\left\lceil\frac{n}{i}\right\rceil&=\sum\limits_{i=1}^{n}(\left\lfloor\frac{n}{i}\right\rfloor+1)-d(n)&\\&=n-d(n)+\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor \end{aligned} i=1∑n⌈in⌉=i=1∑n(⌊in⌋+1)−d(n)=n−d(n)+i=1∑n⌊in⌋
Example F
计算
∑ i = 1 n ⌊ n i 2 ⌋ \displaystyle \sum\limits_{i=1}^{n}\left\lfloor\cfrac{n}{i^2}\right\rfloor i=1∑n⌊i2n⌋
Solution
令 l ′ = l 2 l'=l^2 l′=l2 ， r ′ = r 2 r'=r^2 r′=r2 ，由引理1可得 r ′ = ⌊ n ⌊ n l ′ ⌋ ⌋ \displaystyle r'=\left\lfloor\frac{n}{\lfloor \frac{n}{l'}\rfloor}\right\rfloor r′=⌊⌊l′n⌋n⌋ 。
故
r = ⌊ ⌊ n ⌊ n l 2 ⌋ ⌋ ⌋ \displaystyle r=\left\lfloor\sqrt{\left\lfloor\cfrac{n}{\left\lfloor \dfrac{n}{l^2}\right\rfloor}\right\rfloor}\right\rfloor r=⎣⎢⎢⎢⎢⎣⎢⎢⎢⌊l2n⌋n⎦⎥⎥⎥ ⎦⎥⎥⎥⎥
Example G
已知 n , a , b n,a,b n,a,b 为正整数，求 ∑ i = 1 n ⌊ n a i + b ⌋ \displaystyle \sum\limits_{i=1}^{n}\left\lfloor\frac{n}{ai+b}\right\rfloor i=1∑n⌊ai+bn⌋
Solution
令 l ′ = a l + b l'=al+b l′=al+b ， r ′ = a r + b r'=ar+b r′=ar+b ，由由引理1可得：
r ′ = ⌊ n ⌊ n l ′ ⌋ ⌋ \displaystyle r'=\left\lfloor\frac{n}{\left\lfloor \frac{n}{l'}\right\rfloor}\right\rfloor r′=⌊⌊l′n⌋n⌋
故
a r + b = ⌊ n ⌊ n l ′ ⌋ ⌋ \displaystyle ar+b=\left\lfloor\frac{n}{\left\lfloor \frac{n}{l'}\right\rfloor}\right\rfloor ar+b=⌊⌊l′n⌋n⌋
r = ⌊ ⌊ n ⌊ n l ′ ⌋ ⌋ − b a ⌋ \displaystyle r=\left\lfloor\dfrac{\left\lfloor\dfrac{n}{\left\lfloor \frac{n}{l'}\right\rfloor}\right\rfloor-b}{a}\right\rfloor r=⎣⎢⎢⎢⎢⎢⎢⎢a⌊⌊l′n⌋n⌋−b⎦⎥⎥⎥⎥⎥⎥⎥
Example H
一般地，对于和式： ∑ i = 1 n ⌊ k f ( i ) ⌋ m o d p \displaystyle \sum\limits_{i=1}^{n}\left\lfloor\frac{k}{f(i)}\right\rfloor\bmod p i=1∑n⌊f(i)k⌋modp
其中 n , p , k n,p,k n,p,k 是正整数， 1 ≤ n ≤ 1 0 12 1\le n\le10^{12} 1≤n≤1012，分块边界推导方法是：
⌊ k f ( l ) ⌋ = ⌊ k f ( r ) ⌋ \displaystyle \left\lfloor \frac{k}{f(l)}\right\rfloor=\left\lfloor \frac{k}{f(r)}\right\rfloor ⌊f(l)k⌋=⌊f(r)k⌋
由 引理1 可得
f ( r ) = ⌊ n ⌊ n f ( l ) ⌋ ⌋ f(r)=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{f(l)}\right\rfloor}\right\rfloor f(r)=⎣⎢⎢⎢⎢⎢⌊f(l)n⌋n⎦⎥⎥⎥⎥⎥
我们只需要求出 f ( l ) f(l) f(l) ，然后再解这个关于 r r r 的方程，最后向下取整，就得到了该块的右边界。
● 竞赛例题选讲
Problem A. 余数求和 (Luogu P2261[CQOI2007])
计算
a n s = ∑ i = 1 n ( k m o d i ) ans=\sum_{i=1}^n(k\bmod i) ans=i=1∑n(kmodi)
Solution
显然有：
a n s = ∑ i = 1 n ( k m o d i ) = ∑ i = 1 n k − i ⌊ k i ⌋ ans=\sum_{i=1}^n(k\bmod i)=\sum_{i=1}^nk-i\left\lfloor\frac{k}{i}\right\rfloor ans=i=1∑n(kmodi)=i=1∑nk−i⌊ik⌋
整除分块即可。
Code
typedef long long ll;
const int N = 20007, M = 50007, INF = 0x3f3f3f3f;
ll n, k;
int main()
{
scanf("%lld%lld", &n, &k);
ll ans = n * k;
for(ll l = 1, r; l <= n; l = r + 1){
if(k / l != 0)r = min((k / (k / l)) , n);
else r = n;
ans -= (r + l) * (k / l) * (r - l + 1) / 2;//先乘后除，因为中间除2可能不能整除
//区间内i的平均值 * (k / l) * 区间长度
}
printf("%lld\n", ans);
return 0;
}
Problem B 小G的约数（牛客练习赛77C）
小G定义了两个函数 F ( n ) F(n) F(n) 为 n n n 的约数和， G ( n ) G(n) G(n) 为 F ( 1 ) + F ( 2 ) + . . . + F ( n − 1 ) + F ( n ) F(1)+F(2)+...+F(n-1)+F(n) F(1)+F(2)+...+F(n−1)+F(n)
小G想知道 G ( G ( n ) ) G(G(n)) G(G(n)) 等于多少。
n ≤ 5 × 1 0 4 n\le 5\times 10^4 n≤5×104
Solution
我们知道对于
i
∈
[
1
,
n
]
i\in[1,n]
i∈[1,n]，约数为
i
i
i 的整数的个数为
⌊
n
i
⌋
\left\lfloor\dfrac{n}{i}\right\rfloor
⌊in⌋
显然
1
∼
n
1\sim n
1∼n 的约数和为：
G ( n ) = ∑ i = 1 n ⌊ n i ⌋ × i G(n)=\sum_{i=1}^n \left\lfloor\cfrac{n}{i}\right\rfloor\times i G(n)=i=1∑n⌊in⌋×i
显然前面的 ⌊ n i ⌋ \left\lfloor\dfrac{n}{i}\right\rfloor ⌊in⌋ 可以直接整除分块，后面的 i i i 相当于对于区间 [ l , r ] [l,r] [l,r]， ⌊ n i ⌋ × ( l + ( l + 1 ) + ⋯ + ( r − 1 ) + r ) = ⌊ n i ⌋ × l + r 2 \left\lfloor\dfrac{n}{i}\right\rfloor\times (l+(l+1)+\cdots+(r-1)+r)= \left\lfloor\dfrac{n}{i}\right\rfloor\times \cfrac{l+r}{2} ⌊in⌋×(l+(l+1)+⋯+(r−1)+r)=⌊in⌋×2l+r ， O ( n ) O(\sqrt{n}) O(n ) 的复杂度实现。
Code
#define int long long
const int N = 5e5 + 7, mod = 1e9 + 7;
const double PI = acos(-1.0);
int n, m;
int G(int n)
{
int res = 0;
for(int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
res += (r - l + 1) * (l + r) / 2 * (n / l);
}
return res;
}
signed main()
{
scanf("%lld", &n);
printf("%lld\n", G(G(n)));
return 0;
}
Problem C. Dividing（2020牛客多校 7 - H）
在 1 ≤ n ≤ N , 1 ≤ k ≤ K 1\leq n \leq N,1\le k\le K 1≤n≤N,1≤k≤K 范围内，有多少对 ( n , k ) (n,k) (n,k) 是传奇对。传奇对的条件是：
(
1
,
k
)
(1,k)
(1,k) 一定是传奇对；
若
(
n
,
k
)
(n,k)
(n,k) 是传奇对，
(
n
+
k
,
k
)
(n+k,k)
(n+k,k) 和
(
n
k
,
k
)
(nk,k)
(nk,k) 都是传奇对。
Solution
%https://blog.csdn.net/weixin_45630722/article/details/107772230
%https://blog.csdn.net/Luowaterbi/article/details/107733386
Problem D. Floor and Mod （CF1485C Floor and Mod）
Translation
定义一对数 ( a , b ) (a,b) (a,b) 是特殊的，当且仅当 ⌊ a b ⌋ = a m o d b \left\lfloor\dfrac{a}{b}\right\rfloor=a\mod b ⌊ba⌋=amodb
给定 x x x 和 y y y ，求一共有多少对特殊的数 ( a , b ) (a,b) (a,b) ，当 1 ≤ a ≤ x , 1 ≤ b ≤ y 1\le a\le x,1\le b\le y 1≤a≤x,1≤b≤y。
Solution
显然是一个结论题或者枚举题，我们根据题目中给定的柿子：
⌊ a b ⌋ = a m o d b ⌊ a b ⌋ = a − ⌊ a b ⌋ × b a = ⌊ a b ⌋ × ( b + 1 ) a b + 1 = ⌊ a b ⌋ \begin{aligned}&\left\lfloor\cfrac{a}{b}\right\rfloor=a\mod b &\\& \left \lfloor\cfrac{a}{b}\right\rfloor=a-\left\lfloor\cfrac{a}{b}\right\rfloor\times b&\\& a=\left\lfloor\cfrac{a}{b}\right\rfloor\times (b+1)&\\& \cfrac{a}{b+1}=\left\lfloor\cfrac{a}{b}\right\rfloor\end{aligned} ⌊ba⌋=amodb⌊ba⌋=a−⌊ba⌋×ba=⌊ba⌋×(b+1)b+1a=⌊ba⌋
因为 ⌊ a b ⌋ \left\lfloor\dfrac{a}{b}\right\rfloor ⌊ba⌋ 一定是整数，所以 a b + 1 \cfrac{a}{b+1} b+1a 一定是整数，所以 b + 1 ∣ a b+1\ |\ a b+1 ∣ a。
所以一个很直观的想法就是枚举 b b b ，对于每一个 b b b ， b + 1 b+1 b+1 的倍数 a a a 显然有 x b + 1 \cfrac{x}{b+1} b+1x 个，显然可以整除分块。
但是需要注意题目中的给定的条件为 ⌊ a b ⌋ = a m o d b \left\lfloor\dfrac{a}{b}\right\rfloor=a\mod b ⌊ba⌋=amodb
即： ⌊ a b ⌋ < b \left\lfloor\dfrac{a}{b}\right\rfloor<b ⌊ba⌋<b
即： a b + 1 < b ⇒ a < b 2 + b \cfrac{a}{b+1}<b\Rightarrow a<b^2+b b+1a<b⇒a<b2+b
即 a ∈ [ 0 , b 2 + b − 1 ] a\in [0,b^2+b-1] a∈[0,b2+b−1]。那么符合题意的 a a a 的个数就是： b 2 + b − 1 b + 1 \cfrac { b^2+b-1}{b+1} b+1b2+b−1
并且 a a a 的上限是 x x x，故最终的答案为：
∑ b = 1 y a n s = min { x , b 2 + b − 1 } b + 1 \sum\limits_{b=1}^{y} ans = \cfrac {\min\{x, b^2+b-1\}}{b+1} b=1∑yans=b+1min{x,b2+b−1}
我们可以先枚举 b < x b<\sqrt x b<x ，计算 b 2 + b − 1 b + 1 \cfrac { b^2+b-1}{b+1} b+1b2+b−1
剩余的 b = x ∼ y b=\sqrt x \sim y b=x ∼y，显然 min { x , b 2 + b − 1 } = x {\min\{x, b^2+b-1\}}=x min{x,b2+b−1}=x，直接整除分块即可，其中整除分块的时候，我们需要计算的是 ⌊ x b + 1 ⌋ \left\lfloor \dfrac{x}{b+1}\right\rfloor ⌊b+1x⌋，我们令 l , r l,r l,r 代表 b + 1 b+1 b+1 即可。
时间复杂度 O ( x ) O(\sqrt x) O(x )
Code
using ll = long long;
const int N = 1e5 + 7;
int n, m, t;
int x, y;
int main()
{
scanf("%d", &t);
while(t -- ) {
scanf("%d%d", &x, &y);
int a = 1, b = 1;
ll ans = 0;
for(; b * b + b - 1 < x && b <= y; ++ b)
ans += (b * b + b - 1) / (b + 1);
int l = b + 1, r;
for(; l <= x && l <= y + 1; l = r + 1) {
r = min(x / (x / l), y + 1);
ans += x / l * (r - l + 1);
if(r == y + 1) break;
}
cout << ans << endl;
}
return 0;
}
0x42 莫比乌斯反演
莫比乌斯函数
莫比乌斯函数已在 0x30 积性函数 一章做过详细讲解和性质证明，这里罗略一些常用的性质，在讲解莫比乌斯反演的时候将会用到它们。
定义
μ ( n ) = { 0 ∃ i ∈ [ 1 , m ] , C i > 1 ( − 1 ) m ∀ i ∈ [ 1 , m ] , C i = 1 \mu(n) = \left\{ \begin{matrix} 0 & \exists i \in [1,m],C_i>1 \\ (-1)^m & \forall i \in [1,m],C_i=1 \end{matrix} \right. μ(n)={0(−1)m∃i∈[1,m],Ci>1∀i∈[1,m],Ci=1
- 基本性质定理
性质32.1：
∑ d ∣ n μ ( d ) = { 1 n = 1 0 n ≠ 1 \sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases} d∣n∑μ(d)={10n=1n=1
即 ∑ d ∣ n μ ( d ) = ε ( n ) \sum_{d\mid n}\mu(d)=\varepsilon(n) ∑d∣nμ(d)=ε(n)， μ ∗ 1 = ε \mu * 1 =\varepsilon μ∗1=ε，其中 ∗ * ∗ 是指 D i r i c h l e t Dirichlet Dirichlet 卷积。
性质32.2：
[ gcd ( i , j ) = 1 ] = ∑ d ∣ gcd ( i , j ) μ ( d ) \displaystyle [\gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d) [gcd(i,j)=1]=d∣gcd(i,j)∑μ(d)
0x42.1 莫比乌斯反演公式
设 F ( n ) , f ( n ) F(n),f(n) F(n),f(n) 为两个数论函数。
形式一：
如果有 F ( n ) = ∑ d ∣ n f ( d ) \displaystyle F(n)=\sum_{d\mid n}f(d) F(n)=d∣n∑f(d)，那么有 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) \displaystyle f(n)=\sum_{d\mid n}\mu(d)F(\cfrac{n}{d}) f(n)=d∣n∑μ(d)F(dn)。
形式二：
如果有 F ( n ) = ∑ n ∣ d f ( d ) \displaystyle F(n)=\sum_{n|d}f(d) F(n)=n∣d∑f(d)，那么有 f ( n ) = ∑ n ∣ d μ ( d n ) F ( d ) \displaystyle f(n)=\sum_{n|d}\mu(\cfrac{d}{n})F(d) f(n)=n∣d∑μ(nd)F(d)。
一般在求解数论函数 f f f 无法直接求解的时候，就可以构造 F ( n ) = ∑ d ∣ n f ( d ) \displaystyle F(n)=\sum\limits_{d\mid n}^{}f(d) F(n)=d∣n∑f(d) 或 F ( n ) = ∑ n ∣ d f ( d ) \displaystyle F(n)=\sum_{n|d}f(d) F(n)=n∣d∑f(d)，求出更好求解的 F ( n ) F(n) F(n) ，此时利用枚举倍数的技巧在 O ( n log n ) O(n\log n) O(nlogn) 的复杂度下利用反演公式求解出待求的 f f f 即可。
0x42.2 莫比乌斯反演证明
建议掌握反演的证明，因为我们在写莫比乌斯反演题目的时候，大多数都是直接推式子而不是使用反演公式。
形式一证明
证明一： 对原式做数论变换。
∑ d ∣ n μ ( d ) F ( n d ) = ∑ d ∣ n μ ( d ) ∑ k ∣ n d f ( k ) = ∑ k ∣ n f ( k ) ∑ d ∣ n k μ ( d ) = f ( n ) \begin{aligned}\sum_{d\mid n}\mu(d)F(\frac{n}{d})&=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}f(k)&\\&=\sum_{k\mid n}f(k)\sum_{d\mid \frac{n}{k}}\mu(d)&\\&=f(n)\end{aligned} d∣n∑μ(d)F(dn)=d∣n∑μ(d)k∣dn∑f(k)=k∣n∑f(k)d∣kn∑μ(d)=f(n)
解释： 根据定义 F ( n ) = ∑ d ∣ n f ( d ) \displaystyle F(n)=\sum_{d\mid n}f(d) F(n)=d∣n∑f(d) ，我们使用 ∑ d ∣ n f ( d ) \displaystyle\sum_{d\mid n}f(d) d∣n∑f(d) 来替换 F ( n d ) F(\cfrac{n}{d}) F(dn)，再交换求和顺序（ n d \dfrac n d dn 意味着 n n n 的所有因子， k ∣ n d k\mid \dfrac n d k∣dn 则 k k k 也是 n n n 的所有因子，即单独枚举 k ∣ n k\mid n k∣n，此时 d ∣ n = d ∣ n k d\mid n=d\mid \cfrac n k d∣n=d∣kn，我们可以将 d ∣ n d\mid n d∣n 换成 n k \cfrac n k kn ，是完全等价的）。最后根据莫比乌斯函数的 性质32.1 ： ∑ d ∣ n μ ( d ) = [ n = 1 ] \displaystyle\sum_{d\mid n}\mu(d)=[n=1] d∣n∑μ(d)=[n=1]，因此在 n k = 1 \dfrac{n}{k}=1 kn=1 时第二个和式的值才为 1 1 1，否则全是 0 0 0 。此时 n = k n=k n=k，故原式等价于
∑ k ∣ n [ n = k ] ⋅ f ( k ) = f ( n ) \displaystyle\sum_{k\mid n}[n=k]\cdot f(k)=f(n) k∣n∑[n=k]⋅f(k)=f(n)
反演公式得证 □ \ \square □
证明二： 利用 Dirichlet \text{Dirichlet} Dirichlet 卷积。
反演公式
设 F ( n ) , f ( n ) F(n),f(n) F(n),f(n) 为两个数论函数。
如果有 F ( n ) = ∑ d ∣ n f ( d ) \displaystyle F(n)=\sum_{d\mid n}f(d) F(n)=d∣n∑f(d)，那么有 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) \displaystyle f(n)=\sum_{d\mid n}\mu(d)F(\cfrac{n}{d}) f(n)=d∣n∑μ(d)F(dn)。
显然可以转化为 Dirichlet \text{Dirichlet} Dirichlet 卷积下的 ，已知 F = f ∗ 1 F=f\ast1 F=f∗1，证明 f = F ∗ μ f=F\ast\mu f=F∗μ
显然有：
F
∗
μ
=
f
∗
1
∗
μ
=
f
∗
ε
(
1
∗
μ
=
ε
,
ε
∗
f
=
f
)
=
f
\begin{aligned}F\ast\mu&=f*1*\mu &\\&= f*\varepsilon\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ( 1\ast\mu=\varepsilon,\varepsilon*f=f) &\\&= f \end{aligned}
F∗μ=f∗1∗μ=f∗ε (1∗μ=ε,ε∗f=f)=f
反演公式得证
□
\ \square
□
形式二证明
证明一： 我们考虑逆推这个式子。
∑ n ∣ d μ ( d n ) F ( d ) = ∑ k = 1 + ∞ μ ( k ) F ( k n ) = ∑ k = 1 + ∞ μ ( k ) ∑ k n ∣ d f ( d ) = ∑ n ∣ d f ( d ) ∑ k ∣ d n μ ( k ) = ∑ n ∣ d f ( d ) ϵ ( d n ) = ∑ n ∣ d f ( d ) [ d n = 1 ] = ∑ n ∣ d f ( d ) [ n = d ] = f ( n ) \begin{aligned} \sum_{n|d}{\mu(\frac{d}{n})F(d)} &= \sum_{k=1}^{+\infty}{\mu(k)F(kn)}&\\& = \sum_{k=1}^{+\infty}{\mu(k)\sum_{kn|d}{f(d)}}&\\& = \sum_{n|d}{f(d)\sum_{k|\frac{d}{n}}{\mu(k)}}&\\& = \sum_{n|d}{f(d)\epsilon(\frac{d}{n})}&\\& = \sum_{n|d}{f(d)[\frac{d}{n}=1]}&\\& = \sum_{n|d}{f(d)[n=d]}&\\& = f(n) \end{aligned} n∣d∑μ(nd)F(d)=k=1∑+∞μ(k)F(kn)=k=1∑+∞μ(k)kn∣d∑f(d)=n∣d∑f(d)k∣nd∑μ(k)=n∣d∑f(d)ϵ(nd)=n∣d∑f(d)[nd=1]=n∣d∑f(d)[n=d]=f(n)
我们把 d d d 表示为 k n kn kn 的形式，然后把 F ( n ) = ∑ n ∣ d f ( d ) \displaystyle F(n)=\sum_{n\mid d}f(d) F(n)=n∣d∑f(d) 代入式子。
发现枚举 k k k 再枚举 k n kn kn 的倍数可以转换为直接枚举 n n n 的倍数再求出 k k k，发现后面那一块其实就是 ϵ \epsilon ϵ，式子只有在 d = n d=n d=n 的时候才不为 0 0 0。
0x42.3 推导结论
一些常用结论
（1）GCD与LCM
结论42.1.1： [ gcd ( i , j ) = 1 ] = ∑ d ∣ i , d ∣ j μ ( d ) \displaystyle [\gcd(i,j)=1]=\sum_{d|i,d|j} \mu(d) [gcd(i,j)=1]=d∣i,d∣j∑μ(d)
结论42.1.2： ∑ i = 1 n ∑ i = 1 m [ gcd ( i , j ) = k ] = \displaystyle \sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)=k]= i=1∑ni=1∑m[gcd(i,j)=k]= ∑ d = 1 ⌊ n k ⌋ μ ( d ) ⌊ n d k ⌋ ⌊ m d k ⌋ \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\lfloor\dfrac{n}{d k}\rfloor\lfloor\dfrac{m}{d k}\rfloor ∑d=1⌊kn⌋μ(d)⌊dkn⌋⌊dkm⌋（例题）
结论42.1.3： ∑ i = 1 n ∑ i = 1 m [ gcd ( i , j ) ∈ { Prime } ] = \displaystyle \sum_{i=1}^{n}\sum_{i=1}^{m}[\gcd(i,j)\in \{\text{Prime}\}]= i=1∑ni=1∑m[gcd(i,j)∈{Prime}]= ∑ d = 1 n ( ⌊ n d ⌋ ⌊ m d ⌋ ∑ p ∣ d & p ∈ { P r i m e } μ ( d p ) ) \sum_{d=1}^{n}\left(\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor\sum_{p | d\ \&\ p\in\{Prime\}} \mu(\dfrac{d}{p})\right) ∑d=1n(⌊dn⌋⌊dm⌋∑p∣d & p∈{Prime}μ(pd))（例题）
结论42.1.4： ∑ i = 1 n ∑ j = 1 m lcm ( i , j ) = \displaystyle \sum_{i=1}^{n} \sum_{j=1}^{m} \operatorname{lcm}(i,j)= i=1∑nj=1∑mlcm(i,j)= ∑ d = 1 n d ( ∑ x = 1 ⌊ n d ⌋ x 2 μ ( x ) ∑ i = 1 ⌊ n d x ⌋ i ∑ i = 1 ⌊ m d x ⌋ j ) \sum_{d=1}^{n} d\left(\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor} x^{2} \mu(x) \sum_{i=1}^{\lfloor\frac{n}{dx}\rfloor} i\sum_{i=1}^{\lfloor\frac{m}{dx}\rfloor} j \right) ∑d=1nd(∑x=1⌊dn⌋x2μ(x)∑i=1⌊dxn⌋i∑i=1⌊dxm⌋j)（例题）
（2）除数函数
结论42.2.1： σ k = ∑ d ∣ n i d k \displaystyle \sigma_{k}=\sum_{d|n}id^{k} σk=d∣n∑idk，即 σ k = id k ∗ 1 \sigma_{k}=\operatorname{id}_{k}\ast1 σk=idk∗1
σ 0 ( x ) \sigma_0(x) σ0(x) 表示 x x x 的约数个数
结论42.2.2： σ 0 ( x y ) = ∑ i ∣ x ∑ j ∣ y [ gcd ( i , j ) = 1 ] \displaystyle \sigma_0(xy)=\sum_{i|x} \sum_{j|y}[\operatorname{gcd}(i,j)=1] σ0(xy)=i∣x∑j∣y∑[gcd(i,j)=1]
结论42.2.3： ∑ i = 1 n σ 0 ( i ) = \displaystyle \sum_{i=1}^{n}\sigma_0(i)= i=1∑nσ0(i)=（例题）
结论42.2.4： ∑ i = 1 n ∑ j = 1 m σ 0 ( i j ) = \displaystyle \sum_{i=1}^{n} \sum_{j=1}^{m} \sigma_0(ij)= i=1∑nj=1∑mσ0(ij)= ∑ k = 1 n μ ( k ) ( ∑ i = 1 ⌊ n k ⌋ ⌊ n i k ⌋ ) ( ∑ i = 1 ⌊ m k ⌋ ⌊ m i k ⌋ ) \sum_{k=1}^{n}\mu(k)\left(\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor{\dfrac{n}{ik}}\rfloor\right)\left(\sum_{i=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\dfrac{m}{i k}\rfloor\right) ∑k=1nμ(k)(∑i=1⌊kn⌋⌊ikn⌋)(∑i=1⌊km⌋⌊ikm⌋)（例题）
σ 1 ( x ) \sigma_1(x) σ1(x) 表示 x x x 的约数和
结论42.2.5： d ( x y ) = ∑ i ∣ x ∑ j ∣ y i y j [ gcd ( i , j ) = 1 ] \displaystyle d(xy)=\sum_{i\mid x}\sum_{j\mid y} \frac{iy}{j}[\gcd(i,j)=1] d(xy)=i∣x∑j∣y∑jiy[gcd(i,j)=1]
结论42.2.6： ∑ i = 1 n ∑ j = 1 n σ 1 ( i j ) = \displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n}\sigma_1(ij)= i=1∑nj=1∑nσ1(ij)= ∑ d = 1 n μ ( d ) d ( ∑ i = 1 ⌊ n d ⌋ σ 1 ( i ) ) 2 \sum_{d=1}^{n}\mu(d)d \left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sigma_1(i)\right)^{2} ∑d=1nμ(d)d(∑i=1⌊dn⌋σ1(i))2（例题）
结论42.2.7： ∑ i = 1 n ∑ j = 1 m σ 1 ( gcd ( i , j ) ) = \displaystyle \sum_{i=1}^{n}\sum_{j=1}^{m} \sigma_1(\gcd(i,j))= i=1∑nj=1∑mσ1(gcd(i,j))= ∑ d = 1 n ⌊ n d ⌋ ⌊ m d ⌋ ( ∑ i ∣ d μ ( d i ) σ 1 ( i ) ) \sum_{d=1}^{n}\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor\left(\sum_{i\mid d}\mu(\dfrac{d}{i}) \sigma_1(i)\right) ∑d=1n⌊dn⌋⌊dm⌋(∑i∣dμ(id)σ1(i))（例题）
（3）莫比乌斯函数
结论42.3.1： ∑ k = 1 n μ 2 ( k ) = ∑ d = 1 n μ ( d ) ⌊ n d 2 ⌋ \displaystyle \sum_{k=1}^{n}\mu^{2}(k)=\sum_{d=1}^{\sqrt{n}}\mu(d)\lfloor \frac{n}{d^{2}}\rfloor k=1∑nμ2(k)=d=1∑n μ(d)⌊d2n⌋（例题）
结论42.3.2： ∑ i = 1 n μ 2 ( i ) n i = n \displaystyle \sum_{i=1}^{n}\mu^2(i)\sqrt{\frac{n}{i}}=n i=1∑nμ2(i)in =n（例题）
0x42.4 竞赛例题选讲
Problem A. problem b（P2522 [HAOI2011]）
对于给出的 n n n 个询问，每次求有多少个数对 ( x , y ) (x,y) (x,y)，满足 a ≤ x ≤ b a \le x \le b a≤x≤b ， c ≤ y ≤ d c \le y \le d c≤y≤d，且 gcd ( x , y ) = k \gcd(x,y) = k gcd(x,y)=k， gcd ( x , y ) \gcd(x,y) gcd(x,y) 函数为 x x x 和 y y y 的最大公约数。
1 ≤ n , k ≤ 5 × 1 0 4 1 \le n,k \le 5 \times 10^4 1≤n,k≤5×104 ， 1 ≤ a ≤ b ≤ 5 × 1 0 4 1 \le a \le b \le 5 \times 10^4 1≤a≤b≤5×104， 1 ≤ c ≤ d ≤ 5 × 1 0 4 1 \le c \le d \le 5 \times 10^4 1≤c≤d≤5×104
Solution
方法一：直接推导公式
显然问题可以抽象成等式：
∑
i
=
a
b
∑
j
=
c
d
[
gcd
(
i
,
j
)
=
k
]
\sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k]\qquad
i=a∑bj=c∑d[gcd(i,j)=k]
枚举的范围从 a , c a,c a,c 出发，不好处理，我们考虑转换成从 1 1 1 出发的形式。
根据容斥原理，原式可以分成 4 4 4 块来处理：
a n s = solve ( 1 ∼ b , 1 ∼ d ) − solve ( 1 ∼ a − 1 , 1 ∼ d ) − solve ( 1 ∼ b , 1 ∼ c − 1 ) + solve ( 1 ∼ a − 1 , 1 ∼ c − 1 ) ans=\text{solve}(1\sim b,1\sim d)-\text{solve}(1\sim a-1,1\sim d)-\text{solve}(1\sim b,1\sim c-1)+\text{solve}(1\sim a-1,1\sim c-1) ans=solve(1∼b,1∼d)−solve(1∼a−1,1∼d)−solve(1∼b,1∼c−1)+solve(1∼a−1,1∼c−1)
（减去一个不合法的部分，加上两个都不合法的部分）
其中
solve
\text{solve}
solve 中要处理的式子都为：
∑
i
=
1
n
∑
j
=
1
m
[
gcd
(
i
,
j
)
=
k
]
=
∑
i
=
1
n
∑
j
=
1
m
[
gcd
(
i
k
,
j
k
)
=
1
]
只
有
k
的
倍
数
才
有
贡
献
，
而
[
1
,
n
]
中
k
的
倍
数
显
然
有
⌊
n
k
⌋
个
所
以
令
i
=
i
k
即
仅
枚
举
k
的
倍
数
即
可
=
∑
i
=
1
⌊
n
k
⌋
∑
j
=
1
⌊
m
k
⌋
[
gcd
(
i
,
j
)
=
1
]
(
所
有
k
的
倍
数
，
除
去
k
后
互
质
才
有
贡
献
)
=
∑
i
=
1
⌊
n
k
⌋
∑
j
=
1
⌊
m
k
⌋
ε
(
gcd
(
i
,
j
)
)
=
∑
i
=
1
⌊
n
k
⌋
∑
j
=
1
⌊
m
k
⌋
∑
d
∣
gcd
(
i
,
j
)
μ
(
d
)
=
∑
d
=
1
min
{
⌊
n
k
⌋
,
⌊
m
k
⌋
}
μ
(
d
)
∑
i
=
1
⌊
n
k
⌋
[
d
∣
i
]
∑
j
=
1
⌊
m
k
⌋
[
d
∣
j
]
=
∑
d
=
1
min
{
⌊
n
k
⌋
,
⌊
m
k
⌋
}
}
μ
(
d
)
⌊
n
k
d
⌋
⌊
m
k
d
⌋
\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] &=\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(\frac i k,\frac j k) =1]\ &\\&只有 k 的倍数才有贡献，而[1,n]中k的倍数显然有\left\lfloor\frac{n}{k}\right\rfloor 个&\\&所以令\ i=ik\ 即仅枚举k的倍数即可 &\\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)=1]&\\&(所有k的倍数，除去k后互质才有贡献) &\\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\varepsilon(\gcd(i,j)) &\\&=\displaystyle\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d) &\\&=\displaystyle\sum_{d=1}^{\min\{\left\lfloor\frac n k\right\rfloor,\left\lfloor\frac m k\right\rfloor\}}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}[d\mid i]\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[d\mid j] &\\&=\displaystyle\sum_{d=1}^{\min\{\left\lfloor\frac n k\right\rfloor,\left\lfloor\frac m k\right\rfloor\}\}}\mu(d)\left \lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor \end{aligned}
i=1∑nj=1∑m[gcd(i,j)=k]=i=1∑nj=1∑m[gcd(ki,kj)=1] 只有k的倍数才有贡献，而[1,n]中k的倍数显然有⌊kn⌋个所以令 i=ik 即仅枚举k的倍数即可=i=1∑⌊kn⌋j=1∑⌊km⌋[gcd(i,j)=1](所有k的倍数，除去k后互质才有贡献)=i=1∑⌊kn⌋j=1∑⌊km⌋ε(gcd(i,j))=i=1∑⌊kn⌋j=1∑⌊km⌋d∣gcd(i,j)∑μ(d)=d=1∑min{⌊kn⌋,⌊km⌋}μ(d)i=1∑⌊kn⌋[d∣i]j=1∑⌊km⌋[d∣j]=d=1∑min{⌊kn⌋,⌊km⌋}}μ(d)⌊kdn⌋⌊kdm⌋
显然可以整除分块，时间复杂度为 O ( N + T n ) O(N+T\sqrt n) O(N+Tn )
方法二：利用反演公式：
Code
const int N = 500007, M = 500007,INF = 0x3f3f3f3f;
typedef long long ll;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-')f = -1; ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int a, b, c, d, k;
int mu[N];
int primes[N], cnt;
bool vis[N];
void get_mu(int n)
{
memset(vis, 0, sizeof vis);
memset(mu, 0, sizeof mu);
cnt = 0, mu[1] = 1;
for(int i = 2; i <= n; ++ i)
{
if(vis[i] == 0){
primes[ ++ cnt] = i;
mu[i] = -1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j){
vis[primes[j] * i] = 1;
if(i % primes[j] == 0) break;
mu[i * primes[j]] -= mu[i];
}
}
for(int i = 1; i <= n; ++ i)
mu[i] += mu[i - 1];
}
int solve(int n, int m)
{
n /= k, m /= k;
int res = 0;
for(int i = 1, j; i <= min(n, m); i = j + 1){
j = min(n / (n / i), m / ( m / i));//j是右边界，这里的值都是i
res += (mu[j] - mu[i - 1]) * (n / i) * (m / i);
}
return res;
}
int n, m;
int main()
{
get_mu(N - 1);
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
a = read(), b = read(), c = read(), d = read(), k = read();
int ans = solve(b, d) - solve(b, c - 1) - solve(a - 1, d) + solve(a - 1, c - 1);
printf("%d\n", ans);
}
return 0;
}
Problem B. LCMSUM （Luogu SP5971）
计算
∑ i = 1 n lcm ( i , n ) \sum_{i=1}^n \operatorname{lcm}(i,n) i=1∑nlcm(i,n)
多组数据
1 ⩽ T ⩽ 3 × 1 0 5 , 1 ⩽ n ⩽ 1 0 6 \ 1\leqslant T\leqslant 3\times 10^5,1\leqslant n\leqslant 10^6 1⩽T⩽3×105,1⩽n⩽106
Solution
方法一：
a n s = ∑ i = 1 n lcm ( i , n ) = ∑ i = 1 n i ⋅ n gcd ( i , n ) = n × ∑ i = 1 n i gcd ( i , n ) = n × ∑ d ∣ n ∑ i = 1 n i d [ gcd ( i , n ) = d ] = n × ∑ d ∣ n ∑ i = 1 n i d [ gcd ( i d , n d ) ] = n × ∑ d ∣ n ∑ i = 1 ⌊ n d ⌋ i ⋅ [ gcd ( i , n d ) ] ( i = i d ) \begin{aligned}ans&=\sum_{i=1}^n \operatorname{lcm}(i,n)&\\&=\sum_{i=1}^n \frac{i\cdot n}{\gcd(i,n)} &\\&=n\times \sum_{i=1}^n \frac{i }{\gcd(i,n)} &\\&=n\times \sum_{d\mid n}\sum_{i=1}^n \frac{i }{d}[\gcd(i,n)=d] &\\&=n\times \sum_{d\mid n}\sum_{i=1}^n \frac{i }{d}[\gcd(\frac i d,\frac n d)] &\\&=n\times \sum_{d\mid n}\sum_{i=1}^{ \lfloor\frac n d \rfloor} i\cdot [\gcd(i,\frac n d)]&(i=id) \end{aligned} ans=i=1∑nlcm(i,n)=i=1∑ngcd(i,n)i⋅n=n×i=1∑ngcd(i,n)i=n×d∣n∑i=1∑ndi[gcd(i,n)=d]=n×d∣n∑i=1∑ndi[gcd(di,dn)]=n×d∣n∑i=1∑⌊dn⌋i⋅[gcd(i,dn)](i=id)
设 f ( n ) = ∑ i = 1 ⌊ n d ⌋ i ⋅ [ gcd ( i , n d ) ] \displaystyle f(n)= \sum_{i=1}^{ \lfloor\frac n d \rfloor} i\cdot [\gcd(i,\frac n d)] f(n)=i=1∑⌊dn⌋i⋅[gcd(i,dn)]
显然它的实际含义为： 1 ∼ n 1\sim n 1∼n 中所有与 n n n 互质的数的和。
显然和为 φ ( n ) ⋅ n 2 \cfrac{\varphi(n)\cdot n} 2 2φ(n)⋅n
即：
f
(
x
)
=
φ
(
n
)
⋅
n
2
f(x)=\cfrac{\varphi(n)\cdot n} 2
f(x)=2φ(n)⋅n
即：
a n s = n × ∑ d ∣ n ∑ i = 1 ⌊ n d ⌋ i ⋅ [ gcd ( i , n d ) ] = n × ∑ d ∣ n φ ( d ) ⋅ d 2 = n × ∑ d ∣ n f ( d ) \begin{aligned}\displaystyle ans&=n\times \sum_{d\mid n}\sum_{i=1}^{ \lfloor\frac n d \rfloor} i\cdot [\gcd(i,\frac n d)]&\\&=n\times \sum_{d\mid n}\cfrac{\varphi(d)\cdot d} 2&\\&=n\times \sum_{d\mid n}f(d)\end{aligned} ans=n×d∣n∑i=1∑⌊dn⌋i⋅[gcd(i,dn)]=n×d∣n∑2φ(d)⋅d=n×d∣n∑f(d)
显然可以先预处理出所有的 f ( n ) f(n) f(n) ，然后利用 Dirichlet \text{Dirichlet} Dirichlet 前缀和计算 ∑ d ∣ n f ( d ) \displaystyle \sum_{d\mid n}f(d) d∣n∑f(d) 即可。
时间复杂度 O ( n log n + T ) O(n\log n +T) O(nlogn+T)
方法二：
当然本题还有 O ( n ) O(n) O(n) 的做法。
我们重新推一遍：
∑ i = 1 n i ⋅ n gcd ( i , n ) \sum_{i=1}^n \frac{i\cdot n}{\gcd(i,n)} i=1∑ngcd(i,n)i⋅n
将原式复制一份并且颠倒顺序，然后将 n 一项单独提出，可得
1 2 ⋅ ( ∑ i = 1 n − 1 i ⋅ n gcd ( i , n ) + ∑ i = n − 1 1 i ⋅ n gcd ( i , n ) ) + n \frac{1}{2}\cdot \left(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(i,n)}\right)+n 21⋅(i=1∑n−1gcd(i,n)i⋅n+i=n−1∑1gcd(i,n)i⋅n)+n
根据 gcd ( i , n ) = gcd ( n − i , n ) \gcd(i,n)=\gcd(n-i,n) gcd(i,n)=gcd(n−i,n)，可将原式化为
1 2 ⋅ ( ∑ i = 1 n − 1 i ⋅ n gcd ( i , n ) + ∑ i = n − 1 1 i ⋅ n gcd ( n − i , n ) ) + n \frac{1}{2}\cdot \left(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(n-i,n)}\right)+n 21⋅(i=1∑n−1gcd(i,n)i⋅n+i=n−1∑1gcd(n−i,n)i⋅n)+n
两个求和式中分母相同的项可以合并。
1 2 ⋅ ∑ i = 1 n − 1 n 2 gcd ( i , n ) + n \frac{1}{2}\cdot \sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,n)}+n 21⋅i=1∑n−1gcd(i,n)n2+n
即
1 2 ⋅ ∑ i = 1 n n 2 gcd ( i , n ) + n 2 \frac{1}{2}\cdot \sum_{i=1}^{n}\frac{n^2}{\gcd(i,n)}+\frac{n}{2} 21⋅i=1∑ngcd(i,n)n2+2n
可以将相同的 gcd ( i , n ) \gcd(i,n) gcd(i,n) 合并在一起计算，故只需要统计 gcd ( i , n ) = d \gcd(i,n)=d gcd(i,n)=d 的个数。当 gcd ( i , n ) = d \gcd(i,n)=d gcd(i,n)=d 时， gcd ( i d , n d ) = 1 \displaystyle\gcd(\frac{i}{d},\frac{n}{d})=1 gcd(di,dn)=1，所以 gcd ( i , n ) = d \gcd(i,n)=d gcd(i,n)=d 的个数有 φ ( n d ) \displaystyle\varphi(\frac{n}{d}) φ(dn) 个。
故答案为
1 2 ⋅ ∑ d ∣ n n 2 ⋅ φ ( n d ) d + n 2 \frac{1}{2}\cdot\sum_{d\mid n}\frac{n^2\cdot\varphi(\frac{n}{d})}{d}+\frac{n}{2} 21⋅d∣n∑dn2⋅φ(dn)+2n
变换求和顺序，设 d ′ = n d \displaystyle d'=\frac{n}{d} d′=dn，合并公因式，式子化为
1 2 n ⋅ ( ∑ d ′ ∣ n d ′ ⋅ φ ( d ′ ) + 1 ) \frac{1}{2}n\cdot\left(\sum_{d'\mid n}d'\cdot\varphi(d')+1\right) 21n⋅⎝⎛d′∣n∑d′⋅φ(d′)+1⎠⎞
我们可以设 g ( n ) = ∑ d ∣ n d × φ ( d ) \displaystyle \text g(n)=\sum_{d\mid n}d\times \varphi(d) g(n)=d∣n∑d×φ(d)
显然函数 g g g 是一个积性函数，我们可以利用线性筛 O ( n ) O(n) O(n) 筛出 g g g ：
1. 考虑 g ( p j k ) \operatorname g(p_j^k) g(pjk)
显然它的约数只有
p
j
0
,
p
j
1
,
⋯
,
p
j
k
p_j^0,p_j^1,\cdots,p_j^k
pj0,pj1,⋯,pjk，因此
g
(
p
j
k
)
=
∑
c
=
0
k
p
j
c
×
φ
(
p
j
c
)
\operatorname g(p_j^k)=\sum_{c=0}^{k}p_j^c\times \varphi(p_j^c)
g(pjk)=c=0∑kpjc×φ(pjc)
又有 φ ( p j c ) = p j c − 1 ⋅ ( p j − 1 ) \varphi(p_j^c)=p_j^{c-1}\cdot(p_j-1) φ(pjc)=pjc−1⋅(pj−1)，则原式可化为
∑ c = 0 k p j 2 c − 1 × ( p j − 1 ) \sum_{c=0}^{k}p_j^{2c-1}\times (p_j-1) c=0∑kpj2c−1×(pj−1)
于是有
g ( p j k + 1 ) = g ( p j k ) + p j 2 k + 1 × ( p j − 1 ) \operatorname g(p_j^{k+1})=\operatorname g(p_j^k)+p_j^{2k+1}\times (p_j-1) g(pjk+1)=g(pjk)+pj2k+1×(pj−1)
2. 考虑 g ( i × p j ) \operatorname g(i\times p_j) g(i×pj)，当 p j ∣ i p_j\mid i pj∣i
令
i
=
a
×
p
j
c
(
gcd
(
a
,
p
j
)
=
1
)
i=a\times p_j^c(\operatorname{gcd}(a,p_j)=1)
i=a×pjc(gcd(a,pj)=1)，可得
g
(
i
×
p
j
)
=
g
(
a
)
×
g
(
p
j
c
+
1
)
\operatorname g(i\times p_j)=\operatorname g(a)\times \operatorname g(p_j^{c+1})
g(i×pj)=g(a)×g(pjc+1)
g ( i ) = g ( a ) × g ( p j c ) \operatorname g(i)=\operatorname g(a)\times \operatorname g(p_j^c) g(i)=g(a)×g(pjc)
显然有：
g ( i × p j ) − g ( i ) = g ( a ) × g ( p j c + 1 ) − g ( a ) × g ( p j c ) = g ( a ) × ( g ( p j c ) + p j 2 c + 1 × ( p j − 1 ) ) − g ( a ) × g ( p j c ) = g ( a ) × p j 2 c + 1 × ( p j − 1 ) \begin{aligned}\operatorname g(i\times p_j)-\operatorname g(i)&=\text g(a)\times \text g(p_j^{c+1})-\text g(a)\times \text g(p_j^{c})&\\&=\text g(a)\times (\text g(p_j^c)+p_j^{2c+1}\times (p_j-1))-\text g(a)\times \text g(p_j^{c})&\\&=\operatorname g(a)\times p_j^{2c+1}\times (p_j-1)\end{aligned} g(i×pj)−g(i)=g(a)×g(pjc+1)−g(a)×g(pjc)=g(a)×(g(pjc)+pj2c+1×(pj−1))−g(a)×g(pjc)=g(a)×pj2c+1×(pj−1)
同理有
g ( i ) − g ( i p j ) = g ( a ) × p j 2 c − 1 × ( p j − 1 ) \operatorname g(i)-\operatorname g(\frac{i}{p_j})=\operatorname g(a)\times p_j^{2c-1}\times (p_j-1) g(i)−g(pji)=g(a)×pj2c−1×(pj−1)
因此
g
(
i
×
p
j
)
=
g
(
i
)
+
(
g
(
i
)
−
g
(
i
p
j
)
)
×
p
j
2
\operatorname g(i\times p_j)=\operatorname g(i)+\left (\operatorname g(i)-\operatorname g(\frac{i}{p_j})\right )\times p_j^2
g(i×pj)=g(i)+(g(i)−g(pji))×pj2
3. 考虑
g
(
i
×
p
j
)
\operatorname g(i\times p_j)
g(i×pj)，当
p
j
∤
i
p_j\nmid i
pj∤i
积性函数，显然 g ( i × p j ) = g ( i ) × g ( p j ) \operatorname g(i\times p_j)=\text{g}(i)\times \text{g}(p_j) g(i×pj)=g(i)×g(pj)
时间复杂度 O ( n + T ) O(n+T) O(n+T)
Code1
O ( n log n + T ) O(n\log n+T) O(nlogn+T)
typedef long long ll;
typedef pair<int , int> PII;
const int N = 5000007, M = 500007, T = 1000, Mod = 998244353, INF = 0x3f3f3f3f;
int phi[N];
bool vis[N];
ll f[N], g[N];
int primes[N], cnt;
void get_phi(int n)
{
phi[1] = 1;
f[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
phi[i] = i - 1;
}
f[i] = 1ll * phi[i] * i / 2;
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
for(int j = 1; j <= cnt; ++ j) {
for(int i = 1; i * primes[j] <= n; ++ i) {
f[i * primes[j]] += f[i];
}
}
}
int n, t;
void slove()
{
scanf("%d", &n);
printf("%lld\n", f[n] * n);
}
int main()
{
scanf("%d", &t);
get_phi(N - 1);
while(t -- ) {
slove();
}
}
Code2
O ( n + T ) O(n+T) O(n+T)
using ll = long long;
const int N = 1e6 + 7;
int n, m, s, t, k, ans, a[N];
int primes[N], cnt;
ll g[N];
bool vis[N];
void pre_work(int n)
{
vis[1] = 1;
g[1] = 1;
for (int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
g[i] = 1ll * i * (i - 1) + 1;
}
for (int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = 1;
if(i % primes[j] == 0) {
g[i * primes[j]] = g[i] + (g[i] - g[i / primes[j]]) * primes[j] * primes[j];
break;
}
g[i * primes[j]] = g[i] * g[primes[j]];
}
}
}
void solve()
{
scanf("%d", &n);
printf("%lld\n", (g[n] + 1) * n / 2ll);
}
int main()
{
pre_work(N - 7);
scanf("%d", &t);
while(t -- ) {
solve();
}
return 0;
}
Problem C. 约数个数和 （P3327 [SDOI2015]）
Solution
Code
const int N = 50007;
typedef long long ll;
int n, m, t;
int primes[N];
ll res;
bool vis[N];
int mu[N], sum[N], cnt, H[N];
int g(int k, int x) {return k / (k / x);}
void init(int n)
{
mu[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
mu[i] = -1;
}
for(int j = 1; j <= cnt && primes[j] * i <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) break;
mu[i * primes[j]] = -mu[i];
}
}
for(int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + mu[i];
for(int i = 1; i <= n; ++ i) {
for(int l = 1, r; l <= i; l = r + 1) {
r = min(i, g(i, l));
H[i] += (r - l + 1) * (i / l);
}
}
}
int main()
{
cin >> t;
init(N - 1);
while(t -- ) {
res = 0;
scanf("%d%d", &n, &m);
int k = min(n, m);
for(int l = 1, r; l <= k; l = r + 1) {
r = min(k, min(g(n, l), g(m, l)));
res += ((ll)sum[r] - sum[l - 1]) * H[n / l] * H[m / l];
}
printf("%lld\n", res);
}
return 0;
}
Problem D.Crash 的数字表格 （Luogu P1829）
计算（对 20101009 20101009 20101009 取模）
∑ i = 1 n ∑ j = 1 m lcm ( i , j ) ( n , m ⩽ 1 0 7 ) \sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\qquad (n,m\leqslant 10^7) i=1∑nj=1∑mlcm(i,j)(n,m⩽107)
Solution
Code
#define int long long
const int N = 10000007, mod = 20101009;
int n, m;
int primes[N], cnt, f[N], g[N];
bool vis[N];
void init(int n)
{
g[1] = f[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
f[i] = (1 - i % mod + mod) % mod;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) {
f[i * primes[j]] = f[i];
break;
}
f[i * primes[j]] = (f[i] * f[primes[j]]) % mod;
}
}
for(int i = 1; i <= n; ++ i) {
g[i] = (f[i] * i % mod + g[i - 1]) % mod;
}
}
int s(int x)
{
return (x * (x + 1) / 2) % mod;
}
int ans;
signed main()
{
init(N - 7);
scanf("%lld%lld", &n, &m);
if(n > m) swap(n, m);
ans = 0;
for(int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans = (ans + (s(n / l) * s(m / l) % mod) * (g[r] - g[l - 1] + mod) + mod % mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
Problem E. 简单的数学题 （luogu P3768）
前置知识：0x52 杜教筛
输入一个整数 n n n 和一个整数 p p p，你需要求出：
(
∑
i
=
1
n
∑
j
=
1
n
i
j
gcd
(
i
,
j
)
)
m
o
d
p
\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p
(i=1∑nj=1∑nijgcd(i,j))modp
其中
gcd
(
a
,
b
)
\gcd(a,b)
gcd(a,b) 表示
a
a
a 与
b
b
b 的最大公约数。
n ≤ 1 0 10 n \leq 10^{10} n≤1010 ， 5 × 1 0 8 ≤ p ≤ 1.1 × 1 0 9 5 \times 10^8 \leq p \leq 1.1 \times 10^9 5×108≤p≤1.1×109 且 p p p 为质数。
Solution
Hint
注意一点：这种需要输入模数mod的题，一定要等输入模数之后再初始化 init …不然会RE…膜0可不就RE了嘛…
Time
% %
O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32)
Code
#define int long long
typedef long long ll;
const int N = 4641589;// ⌈(10^10)^(2/3)⌉
int primes[N + 7], cnt;
ll phi[N + 7];
bool vis[N + 7];
unordered_map<ll, ll> sum_f;
int mod, n;
int inv4, inv6;
int qpow(int a, int b)
{
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res % mod;
}
void init(int n)
{
phi[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) {
phi[i * primes[j]] = 1ll * phi[i] * primes[j] % mod;
break;
}
phi[i * primes[j]] = 1ll * phi[i] * phi[primes[j]] % mod;
}
}
for(int i = 1; i <= n; ++ i) {
phi[i] = (1ll * phi[i - 1] + (1ll * phi[i] * i % mod * i % mod)) % mod;
}
}
inline int g_sum(int n) //i^2
{
n %= mod;
return 1ll * n * inv6 % mod * (n + 1) % mod * (2 * n + 1) % mod;
}
inline int h_sum(int n) //i^3
{
n %= mod;
return 1ll * n * inv4 % mod * n % mod * (n + 1) % mod * (n + 1) % mod;
}
inline int get_s_sum(int x)
{
if(x <= N - 7) return phi[x];
if(sum_f.find(x) != sum_f.end()) return sum_f[x];
ll ans = h_sum(x);
for(ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ans = (ans - 1ll * (g_sum(r) - g_sum(l - 1) + mod) % mod * get_s_sum(x / l) % mod) % mod ;
}
return sum_f[x] = ans / g_sum(1);
}
void solve(int n)
{
ll ans = 0;
for(int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = (ans + (1ll * h_sum(n / l) * (get_s_sum(r) - get_s_sum(l - 1) + mod) % mod)) % mod;
}
printf("%lld\n", ans);
return ;
}
signed main()
{
scanf("%lld%lld", &mod, &n);
init(N - 7);
inv4 = qpow(4, mod - 2);
inv6 = qpow(6, mod - 2);
solve(n);
//cout << "ok" << endl;
return 0;
}
趣味题目：
Problem F. Gcd Product（2020 ICPC 济南 F ）
Solution
Code
#define int long long
const int N = 5e5 + 7, mod = 998244353;
int n, m;
int a[N], b[N], c[N];
int primes[N], cnt, mu[N], phi[N];
bool vis[N];
int f[N], g[N], h[N];
void init(int n)
{
mu[1] = phi[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
phi[i] = i - 1;
mu[i] = -1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
mu[i * primes[j]] -= mu[i];
}
}
}
int ans = 0;
signed main()
{
init(N - 7);
scanf("%lld", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%lld", &a[i]);
}
for(int i = 1; i <= n; ++ i) {
scanf("%lld", &b[i]);
}
for(int i = 1; i <= n; ++ i) {
for(int j = i; j <= n; j += i) {
if(mu[i] == 0) continue;
f[j] = ((f[j] + mu[i] * a[j / i]) % mod + mod) % mod;
g[j] = ((g[j] + mu[i] * b[j / i]) % mod + mod) % mod;
}
}
for(int i = 1; i <= n; ++ i) {
for(int j = i; j <= n; j += i) {
if(phi[i] * phi[j / i] == phi[j]) {
//if(__gcd(i, j / i) == 1) {
h[j] = (h[j] + f[i] * g[j / i] % mod) % mod;
}
}
}
for(int i = 1; i <= n; ++ i) {
for(int j = i; j <= n; j += i) {
c[j] = (c[j] + h[i] * j / i % mod) % mod;
}
}
for(int i = 1; i <= n; ++ i) {
ans = (ans ^ c[i]);
}
printf("%lld\n", ans);
return 0;
}
0x42.5 莫比乌斯反演扩展
莫比乌斯反演的非卷积形式
对于数论函数 f , g f,g f,g 和完全积性函数 t t t 且 t ( 1 ) = 1 t(1)=1 t(1)=1：
f ( n ) = ∑ i = 1 n t ( i ) g ( ⌊ n i ⌋ ) ⟺ g ( n ) = ∑ i = 1 n μ ( i ) t ( i ) f ( ⌊ n i ⌋ ) f(n)=\sum_{i=1}^nt(i)\text g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \iff \\\text g(n)=\sum_{i=1}^n\mu(i)t(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right) f(n)=i=1∑nt(i)g(⌊in⌋)⟺g(n)=i=1∑nμ(i)t(i)f(⌊in⌋)
证明
g ( n ) = ∑ i = 1 n μ ( i ) t ( i ) f ( ⌊ n i ⌋ ) = ∑ i = 1 n μ ( i ) t ( i ) ∑ j = 1 ⌊ n i ⌋ t ( j ) g ( ⌊ ⌊ n i ⌋ j ⌋ ) = ∑ i = 1 n μ ( i ) t ( i ) ∑ j = 1 ⌊ n i ⌋ t ( j ) g ( ⌊ n i j ⌋ ) = ∑ T = 1 n ∑ i = 1 n μ ( i ) t ( i ) ∑ j = 1 ⌊ n i ⌋ [ i j = T ] t ( j ) g ( ⌊ n T ⌋ ) 【先枚举 ij 乘积】 = ∑ T = 1 n ∑ i ∣ T μ ( i ) t ( i ) t ( T i ) g ( ⌊ n T ⌋ ) 【 ∑ j = 1 ⌊ n i ⌋ [ i j = T ] 对答案的贡献为 1，于是省略】 = ∑ T = 1 n g ( ⌊ n T ⌋ ) ∑ i ∣ T μ ( i ) t ( i ) t ( T i ) = ∑ T = 1 n g ( ⌊ n T ⌋ ) ∑ i ∣ T μ ( i ) t ( T ) 【t 是完全积性函数】 = ∑ T = 1 n g ( ⌊ n T ⌋ ) t ( T ) ∑ i ∣ T μ ( i ) = ∑ T = 1 n g ( ⌊ n T ⌋ ) t ( T ) ε ( T ) 【 μ ∗ 1 = ε 】 = g ( n ) t ( 1 ) 【当且仅当 T=1, ε ( T ) = 1 时】 = g ( n ) □ \begin{aligned} \text g(n)&=\sum_{i=1}^n\mu(i)t(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &=\sum_{i=1}^n\mu(i)t(i) \sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}t(j) \text g\left(\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{j}\right\rfloor\right)\\ &=\sum_{i=1}^n\mu(i)t(i) \sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}t(j) \text g\left(\left\lfloor\frac{n}{ij}\right\rfloor\right)\\ &=\sum_{T=1}^n \sum_{i=1}^n\mu(i)t(i) \sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}[ij=T] t(j)\text g\left(\left\lfloor\frac{n}{T}\right\rfloor\right) &\text{【先枚举 ij 乘积】}\\ &=\sum_{T=1}^n \sum_{i \mid T}\mu(i)t(i) t\left(\frac{T}{i}\right)\text g\left(\left\lfloor\frac{n}{T}\right\rfloor\right) &\text{【}\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}[ij=T] \text{对答案的贡献为 1，于是省略】}\\ &=\sum_{T=1}^n\text g\left(\left\lfloor\frac{n}{T}\right\rfloor\right) \sum_{i \mid T}\mu(i)t(i)t\left(\frac{T}{i}\right)\\ &=\sum_{T=1}^n\text g\left(\left\lfloor\frac{n}{T}\right\rfloor\right) \sum_{i \mid T}\mu(i)t(T) &\text{【t 是完全积性函数】}\\ &=\sum_{T=1}^n\text g\left(\left\lfloor\frac{n}{T}\right\rfloor\right)t(T) \sum_{i \mid T}\mu(i)\\ &=\sum_{T=1}^n\text g\left(\left\lfloor\frac{n}{T}\right\rfloor\right)t(T) \varepsilon(T) &\text{【}\mu\ast 1= \varepsilon\text{】}\\ &=\text g(n)t(1) &\text{【当且仅当 T=1,}\varepsilon(T)=1\text{时】}\\ &=\text g(n) & \square \end{aligned} g(n)=i=1∑nμ(i)t(i)f(⌊in⌋)=i=1∑nμ(i)t(i)j=1∑⌊in⌋t(j)g(⌊j⌊in⌋⌋)=i=1∑nμ(i)t(i)j=1∑⌊in⌋t(j)g(⌊ijn⌋)=T=1∑ni=1∑nμ(i)t(i)j=1∑⌊in⌋[ij=T]t(j)g(⌊Tn⌋)=T=1∑ni∣T∑μ(i)t(i)t(iT)g(⌊Tn⌋)=T=1∑ng(⌊Tn⌋)i∣T∑μ(i)t(i)t(iT)=T=1∑ng(⌊Tn⌋)i∣T∑μ(i)t(T)=T=1∑ng(⌊Tn⌋)t(T)i∣T∑μ(i)=T=1∑ng(⌊Tn⌋)t(T)ε(T)=g(n)t(1)=g(n)【先枚举 ij 乘积】【j=1∑⌊in⌋[ij=T]对答案的贡献为 1，于是省略】【t 是完全积性函数】【μ∗1=ε】【当且仅当 T=1,ε(T)=1时】□
0x43 欧拉反演
本身是没有欧拉反演这个东西的，在刘汝佳的蓝书上讲过一道利用欧拉函数的性质简便求解答案的题目，由于和莫比乌斯反演雷同，都是由一个基本性质推出一个反演公式，慢慢大家也将这种方法叫做欧拉反演。
我们知道欧拉函数的基本性质：
φ ∗ 1 = i d ⇒ n = ∑ d ∣ n φ ( d ) \begin{aligned}\varphi*1&=id\Rightarrow n=\sum_{d|n}\varphi(d)\end{aligned} φ∗1=id⇒n=d∣n∑φ(d)
（性质的证明详见 0x33.1 常见积性函数的卷积的 性质0x33.5 ）
我们就可以利用这个性质，将 n n n 换成我们想要求的东西，来直接求解答案（反演）。
例如我们可以令 n = gcd ( i , j ) n=\gcd(i,j) n=gcd(i,j)，显然有（ d ∣ gcd ( i , j ) → gcd ( i , j ) ∣ i , j → d ∣ i , j d|\gcd(i,j)\to\gcd(i,j)|i,j\to d|i,j d∣gcd(i,j)→gcd(i,j)∣i,j→d∣i,j）：
gcd ( i , j ) = ∑ d ∣ g c d ( i , j ) φ ( d ) = ∑ d ∣ i ∑ d ∣ j φ ( d ) \begin{aligned}\gcd(i,j)&=\sum_{d|gcd(i,j)}\varphi(d)\\&=\sum_{d|i}\sum_{d|j}\varphi(d)\end{aligned} gcd(i,j)=d∣gcd(i,j)∑φ(d)=d∣i∑d∣j∑φ(d)
我们可以尝试使用一下这个式子：
∑ i = 1 n gcd ( i , n ) = ∑ i = 1 n ∑ d ∣ i ∑ d ∣ n φ ( d ) = ∑ d ∣ n ∑ i = 1 n ∑ d ∣ i φ ( d ) = ∑ d ∣ n ⌊ n d ⌋ φ ( d ) \begin{aligned}\sum_{i=1}^n\gcd(i,n)&=\sum_{i=1}^n\sum_{d|i}\sum_{d|n}\varphi(d)\\&=\sum_{d|n}\sum_{i=1}^n\sum_{d|i}\varphi(d)\\&=\sum_{d|n}\lfloor\frac{n}{d}\rfloor\varphi(d)\end{aligned} i=1∑ngcd(i,n)=i=1∑nd∣i∑d∣n∑φ(d)=d∣n∑i=1∑nd∣i∑φ(d)=d∣n∑⌊dn⌋φ(d)
一些结论：
结论43.1：
∑
i
=
1
n
∑
j
=
1
n
gcd
(
i
,
j
)
=
∑
d
=
1
n
d
(
2
∑
i
=
1
⌊
n
d
⌋
φ
(
i
)
−
1
)
\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} \gcd(i,j)=\sum_{d=1}^{n}d\left(2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\varphi(i)}-1\right)
i=1∑nj=1∑ngcd(i,j)=d=1∑nd⎝⎛2i=1∑⌊dn⌋φ(i)−1⎠⎞
结论43.2：
∑
i
=
1
n
∑
j
=
1
m
gcd
(
i
,
j
)
=
∑
d
=
1
n
φ
(
d
)
⌊
n
d
⌋
⌊
m
d
⌋
\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i,j)=\sum_{d=1}^{n} \varphi(d) \lfloor\frac{n}{d}\rfloor \lfloor\frac{m}{d}\rfloor
i=1∑nj=1∑mgcd(i,j)=d=1∑nφ(d)⌊dn⌋⌊dm⌋（例题）
结论43.3：
∏
i
=
1
n
∏
j
=
1
n
(
lcm
(
i
,
j
)
gcd
(
i
,
j
)
)
=
(
n
!
)
2
n
(
∏
d
=
1
n
d
(
2
S
φ
(
⌊
n
a
⌋
)
−
1
)
)
2
\displaystyle \prod_{i=1}^{n} \prod_{j=1}^{n} \left(\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\right)=\frac{(n!)^{2n}}{\left(\prod_{d=1}^{n} d^{\left(2 S_{\varphi}(\lfloor\frac{n}{a}\rfloor)-1\right)}\right)^{2}}
i=1∏nj=1∏n(gcd(i,j)lcm(i,j))=(∏d=1nd(2Sφ(⌊an⌋)−1))2(n!)2n（例题）
● 竞赛例题选讲
Problem A. 能量采集（P1447 [NOI2010] ）
Solution
方法一： 莫比乌斯反演 + 欧拉反演
先简单解释一下本题解题第一步用到的显然的结论。
数轴上任意一点 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 到原点之间线段上的经过的点 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) ， gcd ( x 2 , y 2 ) \gcd(x_2,y_2) gcd(x2,y2) 一定是 gcd ( x 1 , y 1 ) \gcd(x_1,y_1) gcd(x1,y1) 的因子。例如仪仗队那道题，从原点出发能看到的点一定都是 gcd ( x , y ) = 1 \gcd(x, y)=1 gcd(x,y)=1 的点。从原点到 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 所以经过的点的个数就是 gcd ( x 1 , y 1 ) − 1 \gcd(x_1,y_1)-1 gcd(x1,y1)−1（去掉自身）（ ( 2 , 4 ) (2,4) (2,4) 会有因子 ( 1 , 2 ) (1,2) (1,2) ）
证明来源：
Time
O ( n + n ) O(n+\sqrt n) O(n+n )
Code
const int N = 500007;
int primes[N], cnt, phi[N];
int n, m;
bool vis[N];
int sum[N];
void init(int n)
{
phi[1] = 1;
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0) {
primes[ ++ cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * phi[primes[j]];
}
}
for(int i = 1; i <= n; ++ i) {
sum[i] = sum[i - 1] + phi[i];
}
}
void solve()
{
int res = 0;
for(int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
res += (n / l) * (m / l) * (sum[r] - sum[l - 1]);//(sum[r] - sum[l - 1])已经是区间长度了
}
res = 2 * res - n * m;
printf("%lld\n", res);
}
signed main()
{
init(N - 7);
scanf("%lld%lld", &n, &m);
if(n > m) swap(n, m);
solve();
return 0;
}
方法二： 容斥原理
有趣的是，我们可以利用容斥原理解决这个问题。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
Code
#define int long long
using namespace std;
const int N = 500007;
int n, m;
int f[N];
signed main()
{
scanf("%lld%lld", &n, &m);
if(n > m) swap(n, m);
int ans = 0;
for(int i = n; i; -- i) {
f[i] = (n / i) * (m / i);
for(int j = i << 1; j <= n; j += i)
f[i] -= f[j];
ans += (2 * i - 1) * f[i];
}
printf("%lld\n", ans);
return 0;
}
0x44 二项式反演1
我们知道容斥原理的一般形式为
∣ A 1 ‾ ∩ . . . ∩ A n ‾ ∣ = ∣ A ∣ − ∑ i = 1 n ∣ A i ∣ + ∑ 1 ≤ i 1 < i 2 ≤ n ∣ A i 1 ∩ A i 2 ∣ − . . . + ( − 1 ) n ⋅ ∣ A 1 ∩ . . . ∩ A n ∣ |\overline{A_1} \cap ... \cap \overline{A_n}| = |A| - \sum\limits_{i=1}^n |A_i| + \sum\limits_{1 \leq i_1 < i_2 \leq n} |A_{i_1} \cap A_{i_2}| -... + (-1)^n \cdot |A_1 \cap ... \cap A_n| ∣A1∩...∩An∣=∣A∣−i=1∑n∣Ai∣+1≤i1<i2≤n∑∣Ai1∩Ai2∣−...+(−1)n⋅∣A1∩...∩An∣
那么根据德摩根定律显然有
∣
A
1
∪
.
.
.
∪
A
n
‾
∣
+
∣
A
1
‾
∩
.
.
.
∩
A
n
‾
∣
=
∣
A
∣
|\overline{A_1 \cup ...\cup A_n}|+|\overline{A_1}\cap ...\cap \overline{A_n}|=|A|
∣A1∪...∪An∣+∣A1∩...∩An∣=∣A∣
即
∣ A 1 ∪ A 2 ∪ . . . ∪ A n ∣ = ∑ 1 ≤ i ≤ n ∣ A i ∣ − ∑ 1 ≤ i < j ≤ n ∣ A i ∩ A j ∣ + . . . + ( − 1 ) n − 1 × ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ |A_1\cup A_2\cup...\cup A_n|=\sum\limits_{1\le i\le n}|A_i|-\sum\limits_{1\le i<j\le n}|A_i\cap A_j|+...+(-1)^{n-1}\times |A_1\cap A_2\cap ...\cap A_n| ∣A1∪A2∪...∪An∣=1≤i≤n∑∣Ai∣−1≤i<j≤n∑∣Ai∩Aj∣+...+(−1)n−1×∣A1∩A2∩...∩An∣
那么我们设
A
i
c
A_i^c
Aic 为
A
i
A_i
Ai 的补集，变形可得
∣
A
1
c
∩
A
2
c
∩
.
.
.
∩
A
n
c
∣
=
∣
S
∣
−
∑
1
≤
i
≤
n
∣
A
i
∣
+
∑
1
≤
i
<
j
≤
n
∣
A
i
∩
A
j
∣
−
.
.
.
+
(
−
1
)
n
×
∣
A
1
∩
A
2
∩
.
.
.
∩
A
n
∣
|A_1^c\cap A_2^c\cap ...\cap A_n^c|=|S|-\sum\limits_{1\le i\le n}|A_i|+\sum\limits_{1\le i<j\le n}|A_i\cap A_j|-...+(-1)^n\times |A_1\cap A_2\cap ...\cap A_n|
∣A1c∩A2c∩...∩Anc∣=∣S∣−1≤i≤n∑∣Ai∣+1≤i<j≤n∑∣Ai∩Aj∣−...+(−1)n×∣A1∩A2∩...∩An∣
显然补集的补集就是原集，则有
∣
A
1
∩
A
2
∩
.
.
.
∩
A
n
∣
=
∣
S
∣
−
∑
1
≤
i
≤
n
∣
A
i
c
∣
+
∑
1
≤
i
<
j
≤
n
∣
A
i
c
∩
A
j
c
∣
−
.
.
.
+
(
−
1
)
n
×
∣
A
1
c
∩
A
2
c
∩
.
.
.
∩
A
n
c
∣
|A_1\cap A_2\cap ...\cap A_n|=|S|-\sum\limits_{1\le i\le n}|A_i^c|+\sum\limits_{1\le i<j\le n}|A_i^c\cap A_j^c|-...+(-1)^n\times |A_1^c\cap A_2^c\cap ...\cap A_n^c|
∣A1∩A2∩...∩An∣=∣S∣−1≤i≤n∑∣Aic∣+1≤i<j≤n∑∣Aic∩Ajc∣−...+(−1)n×∣A1c∩A2c∩...∩Anc∣
设
f
(
n
)
f(n)
f(n) 表示
n
n
n 个补集的交集大小，
g
(
n
)
\text g(n)
g(n) 表示
n
n
n 个原集的大小
则
∣
A
1
c
∩
A
2
c
∩
.
.
.
∩
A
n
c
∣
=
∣
S
∣
−
∑
1
≤
i
≤
n
∣
A
i
∣
+
∑
1
≤
i
<
j
≤
n
∣
A
i
∩
A
j
∣
−
.
.
.
+
(
−
1
)
n
×
∣
A
1
∩
A
2
∩
.
.
.
∩
A
n
∣
|A_1^c\cap A_2^c\cap ...\cap A_n^c|=|S|-\sum\limits_{1\le i\le n}|A_i|+\sum\limits_{1\le i<j\le n}|A_i\cap A_j|-...+(-1)^n\times |A_1\cap A_2\cap ...\cap A_n|
∣A1c∩A2c∩...∩Anc∣=∣S∣−1≤i≤n∑∣Ai∣+1≤i<j≤n∑∣Ai∩Aj∣−...+(−1)n×∣A1∩A2∩...∩An∣
即可表示为
f
(
n
)
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
g
(
i
)
f(n)=\sum\limits_{i=0}^n(-1)^i{n\choose i}\text g(i)
f(n)=i=0∑n(−1)i(in)g(i)
而第二个等式
∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ = ∣ S ∣ − ∑ 1 ≤ i ≤ n ∣ A i c ∣ + ∑ 1 ≤ i < j ≤ n ∣ A i c ∩ A j c ∣ − . . . + ( − 1 ) n × ∣ A 1 c ∩ A 2 c ∩ . . . ∩ A n c ∣ |A_1\cap A_2\cap ...\cap A_n|=|S|-\sum\limits_{1\le i\le n}|A_i^c|+\sum\limits_{1\le i<j\le n}|A_i^c\cap A_j^c|-...+(-1)^n\times |A_1^c\cap A_2^c\cap ...\cap A_n^c| ∣A1∩A2∩...∩An∣=∣S∣−1≤i≤n∑∣Aic∣+1≤i<j≤n∑∣Aic∩Ajc∣−...+(−1)n×∣A1c∩A2c∩...∩Anc∣
即可表示为
g ( n ) = ∑ i = 0 n ( − 1 ) i ( n i ) f ( i ) \text g(n)=\sum\limits_{i=0}^n(-1)^i{n\choose i}f(i) g(n)=i=0∑n(−1)i(in)f(i)
即：
f
(
n
)
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
g
(
i
)
⇔
g
(
n
)
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
f
(
i
)
f(n)=\sum\limits_{i=0}^n(-1)^i{n\choose i}g(i)\Leftrightarrow \text g(n)=\sum\limits_{i=0}^n(-1)^i{n\choose i}f(i)
f(n)=i=0∑n(−1)i(in)g(i)⇔g(n)=i=0∑n(−1)i(in)f(i)
我们令
h
(
n
)
=
(
−
1
)
n
g
(
n
)
h(n)=(-1)^n\text g(n)
h(n)=(−1)ng(n) 带入上述公式即可得到二项式反演的第一种形式
● 二项式反演的第一种形式
f
(
n
)
=
∑
i
=
0
n
(
n
i
)
h
(
i
)
⇔
h
(
n
)
(
−
1
)
n
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
f
(
i
)
f(n)=\sum\limits_{i=0}^n{n\choose i}h(i)\Leftrightarrow \frac{h(n)}{(-1)^n}=\sum\limits_{i=0}^n(-1)^i{n\choose i}f(i)
f(n)=i=0∑n(in)h(i)⇔(−1)nh(n)=i=0∑n(−1)i(in)f(i)
更一般的形式为：
f
(
n
)
=
∑
i
=
m
n
(
n
i
)
g
(
i
)
⇔
g
(
n
)
=
∑
i
=
m
n
(
−
1
)
n
−
i
(
n
i
)
f
(
i
)
f(n)=\sum\limits_{i=m}^n{n\choose i}\text g(i)\Leftrightarrow \text g(n)=\sum\limits_{i=m}^n(-1)^{n-i}{n\choose i}f(i)
f(n)=i=m∑n(in)g(i)⇔g(n)=i=m∑n(−1)n−i(in)f(i)
● 二项式反演的第二种形式
f
(
n
)
=
∑
i
=
n
m
(
i
n
)
g
(
i
)
⇔
g
(
n
)
=
∑
i
=
n
m
(
−
1
)
i
−
n
(
i
n
)
f
(
i
)
f(n)=\sum\limits_{i=n}^m{i\choose n}\text g(i)\Leftrightarrow \text g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)
f(n)=i=n∑m(ni)g(i)⇔g(n)=i=n∑m(−1)i−n(ni)f(i)
二项式反演的第二种形式中，我们设 f ( n ) f(n) f(n) 表示 “钦定选择 n n n 个” 的方案数， g ( n ) \text g(n) g(n) 表示 “恰好选 n n n 个” 的方案数， f ( n ) f(n) f(n) 表示先钦定 n n n 个，再统计在已经钦定的情况下的方案数，那么对于任意的 i ≥ n i≥n i≥n ，在 f ( n ) f(n) f(n) 中被计算了 ( i n ) \displaystyle {i\choose n} (ni) 次，故 f ( n ) = ∑ i = n m ( i n ) g ( i ) \displaystyle f(n)=\sum\limits_{i=n}^m{i\choose n}\text g(i) f(n)=i=n∑m(ni)g(i) ，其中 m m m 是数目上界。而对于恰好选择了 i i i 个，从 i i i 个中钦定 n n n 个的方案数显然为 ( i n ) i\choose n (ni)，即 g ( i ) \text g(i) g(i) 也在 f ( i ) f(i) f(i)中被计算了 ( i n ) \displaystyle {i\choose n} (ni) 次，然后根据容斥原理，可得 g ( n ) = ∑ i = n m ( − 1 ) i − n ( i n ) f ( i ) \displaystyle \text g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i) g(n)=i=n∑m(−1)i−n(ni)f(i) 。
形式一证明 f ( n ) = ∑ i = 0 n ( n i ) ∑ j = 0 i ( − 1 ) i − j ( i j ) f ( j ) = ∑ i = 0 n ∑ j = 0 i ( − 1 ) i − j ( n i ) ( i j ) f ( j ) = ∑ j = 0 n f ( j ) ∑ i = j n ( − 1 ) i − j ( n i ) ( i j ) = ∑ j = 0 n ( n j ) f ( j ) ∑ i = j n ( n − j i − j ) ( − 1 ) i − j = ∑ j = 0 n ( n j ) f ( j ) ∑ t = 0 n − j ( n − j t ) ( − 1 ) t 1 n − j − t = ∑ j = 0 n ( n j ) f ( j ) ( 1 − 1 ) n − j \begin{aligned} f(n)&=\sum\limits_{i=0}^n{n\choose i}\sum\limits_{j=0}^i(-1)^{i-j}{i\choose j}f(j)\\&=\sum\limits_{i=0}^n\sum\limits_{j=0}^i(-1)^{i-j}{n\choose i}{i\choose j}f(j) \\&=\sum\limits_{j=0}^nf(j)\sum\limits_{i=j}^n(-1)^{i-j}{n\choose i}{i\choose j}\\&=\sum\limits_{j=0}^n{n\choose j}f(j)\sum\limits_{i=j}^n{n-j\choose i-j}(-1)^{i-j}\\ &=\sum\limits_{j=0}^n{n\choose j}f(j)\sum\limits_{t=0}^{n-j}{n-j\choose t}(-1)^t1^{n-j-t}\\ &=\sum\limits_{j=0}^n{n\choose j}f(j)(1-1)^{n-j} \end{aligned} f(n)=i=0∑n(in)j=0∑i(−1)i−j(ji)f(j)=i=0∑nj=0∑i(−1)i−j(in)(ji)f(j)=j=0∑nf(j)i=j∑n(−1)i−j(in)(ji)=j=0∑n(jn)f(j)i=j∑n(i−jn−j)(−1)i−j=j=0∑n(jn)f(j)t=0∑n−j(tn−j)(−1)t1n−j−t=j=0∑n(jn)f(j)(1−1)n−j 当
n − j ≠ 0 n-j\neq 0 n−j=0 时， ( 1 − 1 ) n − j = 0 (1-1)^{n-j}=0 (1−1)n−j=0当 n − j = 0 n-j=0 n−j=0 时，由于出现 0 0 0^0 00 ，而 0 0 0^0 00 没有任何意义，所以我们从组合角度出发，有 ( n − j t ) ( − 1 ) t = 1 {n-j\choose t}(-1)^{t}=1 (tn−j)(−1)t=1
故 ： ∑ t = 0 n − j ( n − j t ) ( − 1 ) t = [ j = n ] \displaystyle \sum\limits_{t=0}^{n-j}{n-j\choose t}(-1)^t=[j=n] t=0∑n−j(tn−j)(−1)t=[j=n]
即： f ( n ) = ( n n ) f ( n ) = f ( n ) f(n)={n\choose n}f(n)=f(n) f(n)=(nn)f(n)=f(n)
二项式反演第一种形式得证 □ \square □%
形式二证明 f ( n ) = ∑ i = n m ( i n ) ∑ j = i m ( − 1 ) j − i ( j i ) f ( j ) = ∑ i = n m ∑ j = i m ( − 1 ) j − i ( i n ) ( j i ) f ( j ) = ∑ j = n m f ( j ) ∑ i = n j ( − 1 ) j − i ( i n ) ( j i ) = ∑ j = n m ( j n ) f ( j ) ∑ i = n j ( j − n j − i ) ( − 1 ) j − i = ∑ j = n m ( j n ) f ( j ) ∑ t = 0 j − n ( j − n t ) ( − 1 ) t 1 j − n − t = ∑ j = n m ( j n ) f ( j ) ( 1 − 1 ) j − n = ∑ j = n m ( j n ) f ( j ) [ j = n ] = ( n n ) f ( n ) = f ( n ) \begin{aligned} f(n)&=\sum\limits_{i=n}^m{i\choose n}\sum\limits_{j=i}^m(-1)^{j-i}{j\choose i}f(j)\\ &=\sum\limits_{i=n}^m\sum\limits_{j=i}^m(-1)^{j-i}{i\choose n}{j\choose i}f(j)\\ &=\sum\limits_{j=n}^mf(j)\sum\limits_{i=n}^j(-1)^{j-i}{i\choose n}{j\choose i}\\ &=\sum\limits_{j=n}^m{j\choose n}f(j)\sum\limits_{i=n}^j{j-n\choose j-i}(-1)^{j-i}\\ &=\sum\limits_{j=n}^m{j\choose n}f(j)\sum\limits_{t=0}^{j-n}{j-n\choose t}(-1)^{t}1^{j-n-t}\\ &=\sum\limits_{j=n}^m{j\choose n}f(j)(1-1)^{j-n}\\ &=\sum\limits_{j=n}^m{j\choose n}f(j)[j=n]\\ &={n\choose n}f(n)\\ &=f(n) \end{aligned} f(n)=i=n∑m(ni)j=i∑m(−1)j−i(ij)f(j)=i=n∑mj=i∑m(−1)j−i(ni)(ij)f(j)=j=n∑mf(j)i=n∑j(−1)j−i(ni)(ij)=j=n∑m(nj)f(j)i=n∑j(j−ij−n)(−1)j−i=j=n∑m(nj)f(j)t=0∑j−n(tj−n)(−1)t1j−n−t=j=n∑m(nj)f(j)(1−1)j−n=j=n∑m(nj)f(j)[j=n]=(nn)f(n)=f(n)
二项式反演第二种形式得证 □ \square □
● 基本性质定理
性质44.1： f ( n ) = ∑ i = 0 n C n i g ( i ) ⟺ \displaystyle f(n)=\sum_{i=0}^{n}C_{n}^{i}g(i) \Longleftrightarrow f(n)=i=0∑nCnig(i)⟺ g ( n ) = ∑ i = 0 n ( − 1 ) n − i C n i f ( i ) \text g(n)=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}f(i) g(n)=∑i=0n(−1)n−iCnif(i)
性质44.2： f ( n ) = ∑ i = 0 n ( − 1 ) i C n i g ( i ) ⟺ \displaystyle f(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}g(i)\Longleftrightarrow f(n)=i=0∑n(−1)iCnig(i)⟺ g ( n ) = ∑ i = 0 n ( − 1 ) i C n i f ( i ) \text g(n)=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}f(i) g(n)=∑i=0n(−1)iCnif(i)
性质44.3： f ( n ) = ∑ i = n ? C i n g ( i ) ⟺ \displaystyle f(n)=\sum_{i=n}^{?}C_{i}^{n}\text g(i) \Longleftrightarrow f(n)=i=n∑?Cing(i)⟺ g ( n ) = ∑ i = n ? ( − 1 ) i − n C i n f ( i ) \text g(n)=\sum_{i=n}^{?}(-1)^{i-n}C_{i}^{n}f(i) g(n)=∑i=n?(−1)i−nCinf(i)（例题、例题）
性质44.4： f ( n ) = ∑ i = n ? ( − 1 ) i C i n g ( i ) ⟺ \displaystyle f(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}\text g(i)\Longleftrightarrow f(n)=i=n∑?(−1)iCing(i)⟺ g ( n ) = ∑ i = n ? ( − 1 ) i C i n f ( i ) \text g(n)=\sum_{i=n}^{?}(-1)^{i}C_{i}^{n}f(i) g(n)=∑i=n?(−1)iCinf(i)
性质44.5： f ( n , m ) = ∑ i = 0 n ∑ j = 0 m C n i C m j g ( i , j ) ⟺ \displaystyle f(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}C_{n}^{i}C_{m}^{j}g(i,j) \Longleftrightarrow f(n,m)=i=0∑nj=0∑mCniCmjg(i,j)⟺ g ( n , m ) = ∑ i = 0 n ∑ j = 0 m ( − 1 ) n + m − i − j C n i C m j f ( i , j ) g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{n+m-i-j}C_{n}^{i}C_{m}^{j}f(i,j) g(n,m)=i=0∑nj=0∑m(−1)n+m−i−jCniCmjf(i,j)
性质44.6： f ( n , m ) = ∑ i = 0 n ∑ j = 0 m ( − 1 ) i + j C n i C m j g ( i , j ) ⟺ \displaystyle f(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{i+j}C_{n}^{i}C_{m}^{j}g(i,j) \Longleftrightarrow f(n,m)=i=0∑nj=0∑m(−1)i+jCniCmjg(i,j)⟺ g ( n , m ) = ∑ i = 0 n ∑ j = 0 m ( − 1 ) i + j C n i C m j f ( i , j ) g(n,m)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}(-1)^{i+j}C_{n}^{i}C_{m}^{j}f(i,j) g(n,m)=i=0∑nj=0∑m(−1)i+jCniCmjf(i,j)
性质44.7： f ( n , m ) = ∑ i = n ? ∑ j = m ? C i n C j m g ( i , j ) ⟺ \displaystyle f(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}C_{i}^{n}C_{j}^{m}g(i,j) \Longleftrightarrow f(n,m)=i=n∑?j=m∑?CinCjmg(i,j)⟺ g ( n , m ) = ∑ i = n ? ∑ j = m ? ( − 1 ) i + j − n − m C i n C j m f ( i , j ) g(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j-n-m}C_{i}^{n}C_{j}^{m}f(i,j) g(n,m)=i=n∑?j=m∑?(−1)i+j−n−mCinCjmf(i,j)（例题、例题）
性质44.8： f ( n , m ) = ∑ i = n ? ∑ j = m ? ( − 1 ) i + j C i n C j m g ( i , j ) ⟺ \displaystyle f(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j}C_{i}^{n}C_{j}^{m}g(i,j) \Longleftrightarrow f(n,m)=i=n∑?j=m∑?(−1)i+jCinCjmg(i,j)⟺ g ( n , m ) = ∑ i = n ? ∑ j = m ? ( − 1 ) i + j C i n C j m f ( i , j ) g(n,m)=\sum\limits_{i=n}^{?}\sum\limits_{j=m}^{?}(-1)^{i+j}C_{i}^{n}C_{j}^{m}f(i,j) g(n,m)=i=n∑?j=m∑?(−1)i+jCinCjmf(i,j)
● 竞赛例题选讲
Problem A. 集合计数 （[BZOJ 2839]）
一个有N个元素的集合有 2 N 2^N 2N 个不同子集（包含空集），现在要在这 2 N 2^N 2N 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 K K K，求取法的方案数，答案模1000000007。（是质数喔~）
1 ≤ N ≤ 1 0 6 , 0 ≤ K ≤ N 1≤N≤10^6,0≤K≤N 1≤N≤106,0≤K≤N
Solution
设 f ( i ) f(i) f(i) 表示钦定交集元素为某 i i i 个，子集的交集至少为这 i i i 个元素的子集的方案数
显然有 f ( i ) = ( n i ) 2 2 n − i − 1 f(i)= {n \choose i}2^{2^{n-i}-1} f(i)=(in)22n−i−1
即先钦定 i i i 个必选的元素，所有子集至少包含该 i i i 个元素， 剩余 n − i n-i n−i 个元素，这 n − i n-i n−i 个元素，每个元素对于每一个子集而言，可选可不选，故能组成的至少包含这 i i i 个元素的子集方案数为 2 n − i 2^{n-i} 2n−i 个，不允许存在空集，故一共是 2 n − i − 1 2^{n-i}-1 2n−i−1 个可用子集，选择若干子集求交集的时候，每个子集可选可不选，子集的选择方案数为 2 2 n − i − 1 2^{2^{n-i}-1} 22n−i−1。
我们再设
g
(
i
)
\text g(i)
g(i) 表示交集元素恰好为
i
i
i 个的方案数，答案显然就是
g
(
k
)
g(k)
g(k) ，则显然有
f
(
k
)
=
(
n
k
)
(
2
2
n
−
k
−
1
)
=
∑
i
=
k
n
(
i
k
)
g
(
i
)
\begin{aligned}f(k)&={n\choose k}(2^{2^{n-k}}-1)&\\&=\sum\limits_{i=k}^n{i\choose k}\text g(i)\end{aligned}
f(k)=(kn)(22n−k−1)=i=k∑n(ki)g(i)
进行二项式反演显然有：
g
(
k
)
=
∑
i
=
k
n
(
−
1
)
i
−
k
(
i
k
)
f
(
i
)
=
∑
i
=
k
n
(
−
1
)
i
−
k
(
i
k
)
(
n
i
)
(
2
2
n
−
i
−
1
)
\begin{aligned}g(k)&=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}f(i)&\\&=\sum\limits_{i=k}^n(-1)^{i-k}{i\choose k}{n\choose i}(2^{2^{n-i}}-1)\end{aligned}
g(k)=i=k∑n(−1)i−k(ki)f(i)=i=k∑n(−1)i−k(ki)(in)(22n−i−1)
预处理后计算即可。
时间复杂度 O ( n ) O(n) O(n)
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
int n, m, s, t, k, ans, a[N];
int fact[N], infact[N], inv[N], pow22[N];
void pre_work(int n)
{
inv[1] = fact[0] = infact[0] = 1;
pow22[0] = 2;
for (int i = 2; i <= n; ++ i)
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for (int i = 1; i <= n; ++ i) {
fact[i] = 1ll * fact[i - 1] * i % mod;
infact[i] = 1ll * infact[i - 1] * inv[i] % mod;
pow22[i] = 1ll * pow22[i - 1] * pow22[i - 1] % mod;
}
}
int C(int n, int m)
{
if(n == m) return 1;
return 1ll * fact[n] * infact[n - m] % mod * infact[m] % mod;
}
int main()
{
pre_work(N - 7);
scanf("%d%d", &n, &k);
ans = 0;
for (int i = k; i <= n; ++ i) {
if((i - k) & 1)
ans = (1ll * ans - 1ll * C(i, k) * C(n, i) % mod * (pow22[n - i] - 1 + mod) % mod + mod) % mod;
else ans = (1ll * ans + 1ll * C(i, k) * C(n, i) % mod * (pow22[n - i] - 1 + mod) % mod) % mod;
}
cout << ans << endl;
return 0;
}
0x45 斯特林反演
前置知识
这里先复习一下两类斯特林数与上升幂，下降幂之间的转换公式：
x n = ∑ i = 0 n S ( n , i ) x i ‾ x n = ∑ i = 0 n ( − 1 ) n − i S ( n , i ) x i ‾ x n ‾ = ∑ i = 0 n ( − 1 ) n − i s ( n , i ) x i x n ‾ = ∑ i = 0 n s ( n , i ) x i \begin{aligned} x^n&=\sum_{i=0}^{n}S(n,i)x^{\underline i}\\ x^n&=\sum_{i=0}^{n}(-1)^{n-i}S(n,i)x^{\overline i}\\ x^{\underline n}&=\sum_{i=0}^{n}(-1)^{n-i}s (n,i)x^i\\ x^{\overline n}&=\sum_{i=0}^{n}s (n,i)x^i \end{aligned} xnxnxnxn=i=0∑nS(n,i)xi=i=0∑n(−1)n−iS(n,i)xi=i=0∑n(−1)n−is(n,i)xi=i=0∑ns(n,i)xi
根据下降幂的公式：
x n = ∑ i = 0 n S ( n , i ) x i ‾ x^n=\sum_{i=0}^{n}S(n,i)x^{\underline i} xn=i=0∑nS(n,i)xi
我们根据上面的公式将其变成上升幂：
x n = ∑ i = 0 n S ( n , i ) ( − 1 ) i ( − x ) i ‾ x^n=\sum_{i=0}^{n}S(n,i)(-1)^i(-x)^{\overline i} xn=i=0∑nS(n,i)(−1)i(−x)i
代入上升幂转第一类斯特林数的公式：
x n = ∑ i = 0 n S ( n , i ) ( − 1 ) i ∑ j = 0 i s ( i , j ) ( − x ) j x^n=\sum\limits_{i=0}^{n}S(n,i)(-1)^i\sum\limits_{j=0}^{i}s(i,j)(-x)^j xn=i=0∑nS(n,i)(−1)ij=0∑is(i,j)(−x)j
把 x x x 的幂提前，换一下求和符号：
x n = ∑ j = 0 n x j ∑ i = j n S ( n , i ) s ( i , j ) ( − 1 ) i − j x^n=\sum\limits_{j=0}^{n}x^j\sum\limits_{i=j}^nS(n,i)s(i,j)(-1)^{i-j} xn=j=0∑nxji=j∑nS(n,i)s(i,j)(−1)i−j
由于这里我们把 x x x 看成未知量，其他的都是已知量，所以我们可以把左右当作多项式，那么对比系数可得 反转公式：
∑ i = m n S ( n , i ) s ( i , m ) ( − 1 ) i − m = [ m = n ] \sum\limits_{i=m}^{n}S(n,i)s(i,m)(-1)^{i-m}=[m=n] i=m∑nS(n,i)s(i,m)(−1)i−m=[m=n]
同理我们可以得出第二个反转公式：
∑ i = m n s ( n , i ) S ( i , m ) ( − 1 ) i − m = [ m = n ] \sum\limits_{i=m}^{n}s(n,i)S(i,m)(-1)^{i-m}=[m=n] i=m∑ns(n,i)S(i,m)(−1)i−m=[m=n]
注意：反转公式 − 1 −1 −1 的指数也可以写成 n − i n−i n−i ，稍加分析可以发现 m = n m=n m=n 时成立， m ≠ n m≠n m=n 时有两种情况，一种不变，另一种会将答案取相反数，但是由于结果为 0 0 0 所以不影响。
斯特林反演及其证明
了解了上面的前置知识以后，我们引出斯特林反演的公式：
f ( n ) = ∑ i = 0 n S ( n , i ) g ( i ) ⟺ g ( n ) = ∑ i = 0 n ( − 1 ) n − i s ( n , i ) f ( i ) f(n)=\sum_{i=0}^{n}S(n,i)\text g(i)\Longleftrightarrow \text g(n)=\sum_{i=0}^{n}(-1)^{n-i}s(n,i)f(i) f(n)=i=0∑nS(n,i)g(i)⟺g(n)=i=0∑n(−1)n−is(n,i)f(i)
考虑证明：
我们先写出一个 [ i = n ] [i=n] [i=n] 的形式：
g ( n ) = ∑ i = 0 n [ i = n ] g ( i ) \text g(n)=\sum\limits_{i=0}^{n}[i=n]\text g(i) g(n)=i=0∑n[i=n]g(i)
我们再把斯特林数以及 [ m = n ] [m=n] [m=n] 的式子套进去，也就是上面的反转公式（注意 − 1 −1 −1 的指数）：
g ( n ) = ∑ i = 0 n g ( i ) ∑ j = i n ( − 1 ) n − j s 1 ( n , j ) s 2 ( j , i ) = ∑ j = 0 n ( − 1 ) n − j s 1 ( n , j ) ∑ i = 0 j s 2 ( j , i ) g ( i ) = ∑ i = 0 n ( − 1 ) n − i s 1 ( n , i ) f ( i ) \begin{aligned} \text g(n)&=\sum_{i=0}^{n}\text g(i)\sum_{j=i}^{n}(-1)^{n-j}s_1(n,j)s_2(j,i)\\ &=\sum_{j=0}^{n}(-1)^{n-j}s_1(n,j)\sum_{i=0}^{j}s_2(j,i)\text g(i)\\ &=\sum_{i=0}^{n}(-1)^{n-i}s_1(n,i)f(i) \end{aligned} g(n)=i=0∑ng(i)j=i∑n(−1)n−js1(n,j)s2(j,i)=j=0∑n(−1)n−js1(n,j)i=0∑js2(j,i)g(i)=i=0∑n(−1)n−is1(n,i)f(i)
综上所述，斯特林反演公式得证。□
当然由于反转公式的对称性，所以互换 s s s 和 S S S 依然成立。
性质45.1： f ( n ) = ∑ i = 0 n S n i g ( i ) ⟺ \displaystyle f(n)=\sum_{i=0}^{n} S_{n}^{i} \text g(i) \Longleftrightarrow f(n)=i=0∑nSnig(i)⟺ g ( n ) = ∑ i = 0 n ( − 1 ) n − i s n i g ( i ) \text g(n)=\sum_{i=0}^{n}(-1)^{n-i} s_{n}^{i} \text g(i) g(n)=∑i=0n(−1)n−isnig(i)
性质45.2： f ( n ) = ∑ i = 0 n s n i g ( i ) ⟺ \displaystyle f(n)=\sum_{i=0}^{n}s_{n}^{i}\text g(i)\Longleftrightarrow f(n)=i=0∑nsnig(i)⟺ g ( n ) = ∑ i = 0 n ( − 1 ) n − i S n i f ( i ) \text g(n)=\sum_{i=0}^{n}(-1)^{n-i}S_{n}^{i}f(i) g(n)=∑i=0n(−1)n−iSnif(i)
性质45.3： f ( n ) = ∑ i = n ? S i n g ( i ) ⟺ \displaystyle f(n)=\sum_{i=n}^{?} S_{i}^{n} \text g(i) \Longleftrightarrow f(n)=i=n∑?Sing(i)⟺ g ( n ) = ∑ i = n ? ( − 1 ) i − n s i n g ( i ) \text g(n)=\sum_{i=n}^{?}(-1)^{i-n} s_{i}^{n} \text g(i) g(n)=∑i=n?(−1)i−nsing(i)
性质45.4： f ( n ) = ∑ i = n ? s i n g ( i ) ⟺ \displaystyle f(n)=\sum_{i=n}^{?}s_{i}^{n}\text g(i)\Longleftrightarrow f(n)=i=n∑?sing(i)⟺ g ( n ) = ∑ i = n ? ( − 1 ) i − n S i n f ( i ) \text g(n)=\sum_{i=n}^{?}(-1)^{i-n}S_{i}^{n}f(i) g(n)=∑i=n?(−1)i−nSinf(i)
● 竞赛例题选讲
Problem A. 方阵（[2018雅礼集训1-16]）
给出一个 n × m n×m n×m 大小的矩形，每个位置可以填上 [ 1 , c ] [1,c] [1,c] 中的任意一个数，要求填好后任意两行互不等价且任意两列互不等价，两行或两列等价当且仅当对应位置完全相同，求方案数 。
n , m ≤ 5000 n,m≤5000 n,m≤5000
Solution
%https://www.cnblogs.com/hchhch233/p/10016522.html
0x46 单位根反演
单位根反演
∀ k , [ n ∣ k ] = 1 n ∑ i = 0 n − 1 ω n i k \forall k,[n\mid k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik} ∀k,[n∣k]=n1i=0∑n−1ωnik
若 n ∣ k n\mid k n∣k ，显然有 ω n i k = ω 0 = 1 \omega_n^{ik}=\omega^0=1 ωnik=ω0=1，故 1 n ∑ i = 0 n − 1 ω n i k = 1 \displaystyle \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik}=1 n1i=0∑n−1ωnik=1.
若 n ∤ k n\nmid k n∤k， 1 n ∑ i = 0 n − 1 ω n i k = 1 n ω n n k − ω n 0 ω n k − 1 = 0 \displaystyle \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik}=\displaystyle \frac{1}{n}\frac{\omega_n^{nk}-\omega_n^0}{\omega_n^k-1}=0 n1i=0∑n−1ωnik=n1ωnk−1ωnnk−ωn0=0
故原式得证。
若需计算某个多项式的特定倍数的系数和，即 ∑ i = 0 [ n k ] [ x i k ] f ( x ) \displaystyle \sum_{i=0}^{[\frac{n}{k}]}[x^{ik}]f(x) i=0∑[kn][xik]f(x)
则有：
∑ i = 0 [ n k ] [ x i k ] f ( x ) = ∑ i = 0 n [ k ∣ i ] [ x i ] f ( x ) = ∑ i = 0 n [ x i ] f ( x ) 1 k ∑ j = 0 k − 1 ω k j i = 1 k ∑ i = 0 n a i ∑ j = 0 k − 1 ω k i j = 1 k ∑ j = 0 k − 1 ∑ i = 0 n a i ( ω k j ) i = 1 k ∑ j = 0 k − 1 f ( ω k j ) \begin{aligned} &\ \ \ \ \sum_{i=0}^{[\frac{n}{k}]}[x^{ik}]f(x)=\sum_{i=0}^n[k|i][x^i]f(x)\\ &=\sum_{i=0}^n [x^i]f(x)\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ji}\\ &=\frac{1}{k}\sum_{i=0}^n a_i\sum_{j=0}^{k-1}\omega_{k}^{ij}\\ &=\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n a_i(\omega_k^j)^i\\ &=\frac{1}{k}\sum_{j=0}^{k-1}f(\omega_{k}^j) \end{aligned} i=0∑[kn][xik]f(x)=i=0∑n[k∣i][xi]f(x)=i=0∑n[xi]f(x)k1j=0∑k−1ωkji=k1i=0∑naij=0∑k−1ωkij=k1j=0∑k−1i=0∑nai(ωkj)i=k1j=0∑k−1f(ωkj)
- 基本性质定理
性质46.1.1： [ n ∣ k ] = ∑ i = 0 n − 1 w n i k n \displaystyle [n|k]=\frac{\displaystyle \sum_{i=0}^{n-1}w_{n}^{ik}}{n} [n∣k]=ni=0∑n−1wnik
性质46.1.2： [ a = b ] = ∑ i = 0 n − 1 w n a i w n − i b n ( a , b < n ) \displaystyle [a=b]=\frac{\displaystyle \sum_{i=0}^{n-1} w_{n}^{a i} w_{n}^{-i b}}{n}(a,b<n) [a=b]=ni=0∑n−1wnaiwn−ib(a,b<n)
- 推导结论
结论46.2.1： ∑ i = 0 n C n i m i a ( i m o d 4 ) = 1 4 ∑ j = 0 3 a j ∑ k = 0 3 w 4 − k j ( m w 4 k + 1 ) n \displaystyle \sum_{i=0}^{n}C_{n}^{i}m^{i}a_{(i\mod 4)}=\frac{1}{4}\sum_{j=0}^{3}a_{j} \sum_{k=0}^{3}w_{4}^{-kj}(mw_{4}^{k}+1)^{n} i=0∑nCnimia(imod4)=41j=0∑3ajk=0∑3w4−kj(mw4k+1)n（例题）
结论46.2.1： ∑ i = 0 n C n i m i ⌊ i k ⌋ = \displaystyle \sum\limits_{i=0}^{n}C_{n}^{i}m^i\lfloor\frac{i}{k}\rfloor= i=0∑nCnimi⌊ki⌋= 1 k ( n m ( m + 1 ) n − 1 − 1 k ∑ t = 0 k ( m ω k t + 1 ) n f ( t ) ) \frac{1}{k}{\left(nm\ (m\!+\!1)^{n-1}-\frac{1}{k}{\sum\limits_{t=0}^{k}(m\omega_{k}^{t}+1)^{n}f(t)}\right)} k1(nm (m+1)n−1−k1t=0∑k(mωkt+1)nf(t))（例题）
● 竞赛例题选讲
%[https://www.cnblogs.com/cjjsb/p/11728892.html](https://www.cnblogs.com/cjjsb/p/11728892.html)
0x47 子集反演
说是子集反演，其实就是裸的容斥
● 基本性质定理
性质47.1： f ( S ) = ∑ T ⊆ S g ( T ) ⟺ g ( S ) = ∑ T ⊆ S ( − 1 ) ∣ S ∣ − ∣ T ∣ f ( T ) \displaystyle f(S)=\sum_{T\subseteq S}g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) f(S)=T⊆S∑g(T)⟺g(S)=T⊆S∑(−1)∣S∣−∣T∣f(T)（模板）
性质47.2： f ( S ) = ∑ T ⊇ S g ( T ) ⟺ g ( S ) = ∑ T ⊇ S ( − 1 ) ∣ T ∣ − ∣ S ∣ f ( T ) \displaystyle f(S)=\sum_{T\supseteq S}g(T)\Longleftrightarrow g(S)=\sum_{T\supseteq S}(-1)^{|T|-|S|}f(T) f(S)=T⊇S∑g(T)⟺g(S)=T⊇S∑(−1)∣T∣−∣S∣f(T)
性质47.3： f ( S ) = ∑ T ⊆ S g ( T ) ⟺ g ( S ) = ∑ T ⊆ S μ ( ∣ S ∣ − ∣ T ∣ ) f ( T ) \displaystyle f(S)=\sum_{T\subseteq S}g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S}\mu(|S|-|T|)f(T) f(S)=T⊆S∑g(T)⟺g(S)=T⊆S∑μ(∣S∣−∣T∣)f(T)（ μ ( S ) \mu(S) μ(S) 在 S S S 有重复元素时为 0 0 0，否则为 ( − 1 ) ∣ S ∣ (-1)^{|S|} (−1)∣S∣）
性质47.4： f ( S ) = ∑ T ⊇ S g ( T ) ⟺ g ( S ) = ∑ T ⊇ S μ ( ∣ T ∣ − ∣ S ∣ ) f ( T ) \displaystyle f(S)=\sum_{T\supseteq S}g(T)\Longleftrightarrow g(S)=\sum_{T\supseteq S}\mu(|T|-|S|)f(T) f(S)=T⊇S∑g(T)⟺g(S)=T⊇S∑μ(∣T∣−∣S∣)f(T)（ μ ( S ) \mu(S) μ(S) 在 S S S 有重复元素时为 0 0 0，否则为 ( − 1 ) ∣ S ∣ (-1)^{|S|} (−1)∣S∣）
● 竞赛例题选讲
Problem A. 黑暗前的幻想乡 （Luogu P4336 [SHOI2016]）
n
≤
17
,
P
=
1
0
9
+
7
n\le 17, P = 10^9+7
n≤17,P=109+7
Solution
题目就是要求由 n − 1 n-1 n−1 个公司每个公司一条边建成的生成树的方案数。
显然求生成树的方案数，我们直接用矩阵树定理计算即可。
现在考虑满足 每个公司都只负责一条边的方案数 如何计算。
显然有： n ≤ 17 + 计 数 问 题 = 容斥 n\le 17 + 计数问题 = \text{容斥} n≤17+计数问题=容斥
我们可以先用矩阵树定理计算 n − 1 n-1 n−1 个公司包含的所有边集的生成树的个数，显然这里算出来的生成树，不一定 n − 1 n-1 n−1 个公司都参与了建设，我们用容斥原理减去不合法的即可。
显然就是枚举有多少个公司没有参与建设，然后利用容斥原理奇加偶减，答案减去容斥原理计算出的结果，变成奇减偶加。
我们设 g ( S ) g(S) g(S)为最终的答案，即全集 S S S 全部被覆盖的情况的方案数。
f ( S ) f(S) f(S) 为公司恰好仅为 S S S 的方案。
显然有：
g ( S ) = ∑ T ⊆ S f ( T ) g(S)=\sum\limits_{T\subseteq S}f(T) g(S)=T⊆S∑f(T)
根据子集反演可得：
f ( S ) = ∑ T ⊆ S ( − 1 ) ∣ S ∣ − ∣ T ∣ g ( T ) f(S)=\sum\limits_{T\subseteq S}(-1)^{\left|S\right|-\left|T\right|}g(T) f(S)=T⊆S∑(−1)∣S∣−∣T∣g(T)
即答案就是所有生成树的方案数，减去 1 1 1 个公司没有参与，由剩下的 n − 2 n-2 n−2 个公司建成的生成树的个数，加上 2 2 2 个公司没有参与，由剩下的 n − 3 n-3 n−3 个公司建成的生成树的个数，减去 3 3 3 个公司没有参与，由剩下的 n − 4 n-4 n−4 个公司建成的生成树的个数 ⋯ \cdots ⋯
我们可以通过二进制枚举来枚举具体选择了那几个公司的边，处理出此时的基尔霍夫矩阵，然后直接利用矩阵树定理高斯消元 O ( n 3 ) O(n^3) O(n3) 计算代数余子式的行列式即可。
注意我们矩阵树定理计算的时候是可以处理重边的，所以如果一条边被多个公司覆盖，就把它当成重边即可，这样都当成重边算，最后减下来是没有重边的。
Time
O ( 2 n × n 3 log P ) O(2^{n}\times n^3\log P) O(2n×n3logP)
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100 + 7, M = 1e5 + 7, mod = 1e9 + 7;
int n, m[M], s, t, k, ans, a[N][N];
int siz[M];
int u[N][N], v[N][N];
int qpow(int a, int b)
{
int res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int guass2(int n)// 辗转相除 = TLE
{
int det = 1;
for (int i = 2; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
while(a[j][i]) {
int t = a[i][i] / a[j][i];
for (int k = i; k <= n; ++ k)
a[i][k] = (a[i][k] - t * a[j][k] + mod) % mod;
swap(a[i], a[j]);
det = -det;
}
}
det = (det * a[i][i]) % mod;
if(det == 0) return 0;
}
return (det + mod) % mod;
}
int guass(int n)// 求逆元 = AC
{
int det = 1;
for (int i = 2; i <= n; ++ i) {
for (int j = i; j <= n; ++ j) {
if(a[i][j]) {
swap(a[i], a[j]);
if(i != j)
det = mod - det;
break;
}
}
int inv = qpow(a[i][i], mod - 2);
for (int j = i + 1; j <= n; ++ j) {
if(a[j][i]) {
int tmp = a[j][i] * inv % mod;
for (int k = i; k <= n; ++ k) {
a[j][k] = (a[j][k] - a[i][k] * tmp % mod + mod) % mod;
}
}
}
}
for (int i = 2; i <= n; ++ i)
det = det * a[i][i] % mod;
return det;
}
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n - 1; ++ i) {
scanf("%lld", &m[i]);
for (int j = 1; j <= m[i]; ++ j) {
scanf("%lld%lld", &u[i][j], &v[i][j]);
int x = u[i][j], y = v[i][j];
a[x][x] ++ ;
a[y][y] ++ ;
a[x][y] = (a[x][y] + mod - 1) % mod;
a[y][x] = (a[y][x] + mod - 1) % mod;
}
}
ans = guass(n);
for (int i = 1; i <= (1 << (n - 1)) - 1; ++ i) {
for (int j = 1; j <= n; ++ j)
for (int k = 1; k <= n; ++ k)
a[j][k] = 0;
int cnt = 0;
int tmp = i, j;
for (j = 1; tmp; tmp >>= 1, ++ j) {
if((tmp & 1) == 0) continue;
cnt ++ ;
for (int k = 1; k <= m[j]; ++ k) {
int x = u[j][k], y = v[j][k];
a[x][x] ++ ;
a[y][y] ++ ;
a[x][y] = (a[x][y] + mod - 1) % mod;
a[y][x] = (a[y][x] + mod - 1) % mod;
}
}
if(cnt == n - 1) continue;
ans = (ans - ((((n - 1) - cnt) & 1) ? 1 : -1) * guass(n) + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
0x48 最值反演 ( Min - Max 容斥)
● 基本性质定理
最值反演 —— Min - Max 容斥
设 min \min min 为集合最小值， max \max max 为集合最大值
max ( S ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 min ( T ) min ( S ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 max ( T ) \max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)\\\min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T) max(S)=T⊆S∑(−1)∣T∣+1min(T)min(S)=T⊆S∑(−1)∣T∣+1max(T)
证明：
记
S
=
{
a
i
}
S=\{a_i\}
S={ai}，其中对于
i
<
j
i<j
i<j 有
a
i
<
a
j
a_i<a_j
ai<aj
那么我们计算每一个
a
i
a_i
ai 的贡献，有
∑ T ∈ S ( − 1 ) ∣ T ∣ + 1 min { T } = ∑ i = 1 n a i ∑ j = 0 n − i ( − 1 ) j ( n − i j ) = ∑ i = 1 n a i [ n − i = 0 ] = ∑ i = 1 n a i [ n = i ] = a n = max { S } \begin{aligned}\sum_{T \in S}(-1)^{|T|+1} \min \{T\} &=\sum_{i=1}^{n} a_{i} \sum_{j=0}^{n-i}(-1)^{j}\left(\begin{array}{c}n-i \\j\end{array}\right) \\&=\sum_{i=1}^{n} a_{i}[n-i=0] \\&=\sum_{i=1}^{n} a_{i}[n=i] \\&=a_{n} \\&=\max \{S\}\end{aligned} T∈S∑(−1)∣T∣+1min{T}=i=1∑naij=0∑n−i(−1)j(n−ij)=i=1∑nai[n−i=0]=i=1∑nai[n=i]=an=max{S}
Min - Max 容斥在期望意义下也是成立的:，设 E ( x ) E(x) E(x) 表示元素 x x x 出现的期望操作次数，则：
E ( max ( S ) ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ − 1 E ( min ( T ) ) E ( min ( S ) ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ − 1 E ( max ( T ) ) E(\max(S))=\sum_{T \subseteq S}(-1)^{|T|-1}E(\min(T))\\ E(\min(S))=\sum_{T \subseteq S}(-1)^{|T|-1}E(\max(T)) E(max(S))=T⊆S∑(−1)∣T∣−1E(min(T))E(min(S))=T⊆S∑(−1)∣T∣−1E(max(T))
拓展 Min - Max 容斥
设
k
t
h
max
(
S
)
k^{th}\max(S)
kthmax(S) 表示 S 的第 k 大元素, 则
k
t
h
max
(
S
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
−
k
(
∣
T
∣
−
1
k
−
1
)
min
(
T
)
k^{th}\max(S)=\sum_{T \subseteq S} (-1)^{|T|-k} {|T|-1 \choose k-1} \min(T)
kthmax(S)=T⊆S∑(−1)∣T∣−k(k−1∣T∣−1)min(T)
证明同上，同样在期望意义下成立:
E ( k t h max ( S ) ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ − k ( ∣ T ∣ − 1 k − 1 ) E ( min ( T ) ) \displaystyle E(k^{th}\max(S))=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}E(\min(T)) E(kthmax(S))=T⊆S∑(−1)∣T∣−k(k−1∣T∣−1)E(min(T))
性质48.1：
max
(
S
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
+
1
min
(
T
)
\displaystyle \max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)
max(S)=T⊆S∑(−1)∣T∣+1min(T)
性质48.2：
min
(
S
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
+
1
max
(
T
)
\displaystyle \min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T)
min(S)=T⊆S∑(−1)∣T∣+1max(T)
性质48.3：
E
(
max
(
S
)
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
−
1
E
(
min
(
T
)
)
\displaystyle E(\max(S))=\sum_{T \subseteq S}(-1)^{|T|-1}E(\min(T))
E(max(S))=T⊆S∑(−1)∣T∣−1E(min(T))
性质48.4：
E
(
min
(
S
)
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
−
1
E
(
max
(
T
)
)
\displaystyle E(\min(S))=\sum_{T \subseteq S}(-1)^{|T|-1}E(\max(T))
E(min(S))=T⊆S∑(−1)∣T∣−1E(max(T))
性质48.5：
k
t
h
max
(
S
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
−
k
(
∣
T
∣
−
1
k
−
1
)
min
(
T
)
\displaystyle k^{th}\max(S)=\sum_{T \subseteq S} (-1)^{|T|-k} {|T|-1 \choose k-1} \min(T)
kthmax(S)=T⊆S∑(−1)∣T∣−k(k−1∣T∣−1)min(T)
性质48.6：
E
(
k
t
h
max
(
S
)
)
=
∑
T
⊆
S
(
−
1
)
∣
T
∣
−
k
(
∣
T
∣
−
1
k
−
1
)
E
(
min
(
T
)
)
\displaystyle E(k^{th}\max(S))=\sum_{T\subseteq S}(-1)^{|T|-k}{|T|-1\choose k-1}E(\min(T))
E(kthmax(S))=T⊆S∑(−1)∣T∣−k(k−1∣T∣−1)E(min(T))
Problem A
有 N ( 1 ≤ N ≤ 20 ) N(1\le N \le 20) N(1≤N≤20)张卡片，每包中含有这些卡片的概率为 p 1 , p 2 , ⋯ p N p_1,p_2,\cdots p_N p1,p2,⋯pN。每包至多一张卡片，可能没有卡片。求需要买多少包才能拿到所有的 N N N 张卡片，求次数的期望。
Solution
对于此题，我们想要求出所有卡片集合 S 中最晚出现的卡片的期望，就转化为计算 S 的所有子集中最早出现的期望
点集中最早出现的元素的期望是 min ，最晚出现的元素的期望是 max ；全部出现的期望就是最晚出现的元素的期望。
对于一个集合T，显然出现一张卡片的期望为 1 ∑ i ∈ T p i \displaystyle \cfrac{1}{\sum_{i \in T} p_{i}} ∑i∈Tpi1
Code
const int N = 23, M = 1048576 + 3;
int n, V, cnt[M];
double ans, p[N], Min[M];
int main() {
while (~scanf("%d", &n)) {
V = (1 << n) - 1, ans = 0;
for (int i = 1; i <= n; ++i)
scanf("%lf", &p[i]);
for (int s = 1; s <= V; ++s) {
Min[s] = 0, cnt[s] = cnt[s >> 1] + (s & 1);
for (Re i = 1; i <= n; ++i)
if (s & (1 << i - 1))
Min[s] += p[i];
Min[s] = 1.0 / Min[s];
}
for (int t = 1; t <= V; ++t)
ans += (cnt[t] & 1) ? Min[t] : -Min[t];
printf("%lf\n", ans);
}
}
Problem B. 按位或（Luogu P3175 [HAOI2015]）
刚开始你有一个数字 0 0 0，每一秒钟你会随机选择一个 [ 0 , 2 n − 1 ] [0,2^n-1] [0,2n−1] 的数字，与你手上的数字进行按位或。选择数字 i i i 的概率是 p i p_i pi 。保证 0 ≤ p i ≤ 1 0\leq p_i \leq 1 0≤pi≤1， ∑ p i = 1 \sum p_i=1 ∑pi=1 。问期望多少秒后，你手上的数字变成 2 n − 1 2^n-1 2n−1。
Solution
分析题目，我们每次选择的数是在 [ 0 , 2 n − 1 ] [0,2^n-1] [0,2n−1] 的数，进行按位或运算，显然无论如何选择，手里的数都不会大于 2 n − 1 2^n-1 2n−1。我们希望最后手里的数变为 2 n − 1 2^n-1 2n−1，即一个 n n n 位二进制数 x x x 中所有 n n n 位全部变成 1 1 1，因此我们可以将问题抽象成，有一个 n n n 位二进制数 x x x，开始 n n n 位上全是 0 0 0，我们每次选择一个数，可以使得 x x x 发生变化，最后 x x x 的所有位全部变为 1 1 1 的期望选择次数（时间）。
然后因为选择数字 i i i 的概率为 p i p_i pi，我们每次选择数 i i i，使得该二进制数发生一些变化，直到所有二进制数全部变为 1 1 1，显然我们可以联想到一个类似的问题模型：有 n ≤ 20 n\le 20 n≤20 种牌，每种牌无限张，得到第 i i i 种牌的概率为 p i p_i pi，问每张牌均至少拥有一张的期望购买次数（时间）。即 HDU4336 Card Collector，我们发现抽象出来问题模型之后，两个问题的模型几乎一模一样！
我们回想 HDU4336 Card Collector 是怎么解决的， Min - Max 容斥！
我们设 a i a_i ai 为得到卡片 i i i 的期望时间，集合 S = { a i } S=\{a_i\} S={ai}。显然 max { S } \max\{S\} max{S} 为得到最后一张卡片的期望时间（此时我们已经得到了所有的卡片，游戏结束），则 min { S } \min\{S\} min{S} 为得到第一张卡片的期望时间。
显然有 Min - Max 容斥：
max ( S ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 min ( T ) min ( S ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 max ( T ) \max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)\\\min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T) max(S)=T⊆S∑(−1)∣T∣+1min(T)min(S)=T⊆S∑(−1)∣T∣+1max(T)
我们只需要直接爆搜计算集合 S S S 的所有子集 T T T 的 min ( T ) = 1 ∑ i ∈ T p i \min(T)=\frac 1{\sum\limits_{i\in T}p_i} min(T)=i∈T∑pi1 即可在 O ( 2 n ) O(2^n) O(2n) 的时间复杂度下求得 max ( S ) \max(S) max(S)，即为答案。
显然两个题目的模型是一模一样的，我们考虑使用 Min - Max 容斥解决本题。
类似的，我们设 a k a_k ak 为二进制数 x x x 的第 k k k 位变为 1 1 1 的期望时间，集合 S = { a i } S=\{a_i\} S={ai}，显然这里的 S S S 为全集，也就是二进制数 x x x 的全部 n n n 位， S S S 的子集 T T T，表示某几位，也就是二进制数 x x x 的 y ≤ n y\le n y≤n 位。
显然 max { S } \max\{S\} max{S} 为二进制数 x x x 的所有位均为 1 1 1 所有的期望时间， min { S } \min\{S\} min{S} 为二进制数 x x x 第一次有位数变为 1 1 1 的期望时间。
max ( S ) = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 min ( T ) \max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T) max(S)=T⊆S∑(−1)∣T∣+1min(T)
同样的，我们只需要计算集合 S S S 的所有子集 T T T 的 min ( T ) \min(T) min(T) 即可。
显然根据期望公式有：
min ( T ) = ∑ i = 1 + ∞ i × P ( min ( T ) = i ) \min(T)=\sum\limits^{+\infty}_{i=1}i\times P(\min(T)=i) min(T)=i=1∑+∞i×P(min(T)=i)
其中 P ( min ( T ) = i ) P(\min(T)=i) P(min(T)=i) 表示在第 i i i 秒，集合 T T T 中第一次出现了 1 1 1 的概率，这也就意味着前 i − 1 i−1 i−1 秒内，每一秒，集合 T T T 中均没有出现 1 1 1，即集合 T T T 在全集 S S S 的补集 W W W 中出现了 1 1 1（ W = ∁ S T , W ∩ T = ∅ , W + T = S W=\complement_ST,W\cap T=\varnothing,W+T=S W=∁ST,W∩T=∅,W+T=S，显然 W = S xor T W=S\ \text{xor}\ T W=S xor T，因为这里代表的是二进制数）。设每一秒为事件 A A A，显然有 P ( A ) = ∑ w ⊂ W P ( w ) P(A)=\sum\limits_{w\subset W}P(w) P(A)=w⊂W∑P(w) ，其中 P ( w ) P(w) P(w) 表示出现的 1 1 1 是在集合 w w w 中的概率。
第 i i i 秒，集合 T T T 第一次出现 1 1 1，显然概率为 1 − P ( A ) = 1 − ∑ w ⊂ W P ( w ) 1-P(A)=1-\sum\limits_{w\subset W}P(w) 1−P(A)=1−w⊂W∑P(w)。
显然为几何概型，期望为：
E
(
min
(
T
)
)
=
1
P
=
1
1
−
∑
w
⊂
W
P
(
w
)
,
W
=
∁
S
T
\begin{aligned}E(\min(T))&={\dfrac{1}{P}}&\\&=\dfrac{1}{1-\displaystyle\sum\limits_{w\subset W}P(w)},W=\complement_ST\end{aligned}
E(min(T))=P1=1−w⊂W∑P(w)1,W=∁ST
也就是说我们只需要计算出每个集合的子集和概率之和 ∑ w ⊂ W P ( w ) \displaystyle\sum\limits_{w\subset W}P(w) w⊂W∑P(w) 即可利用 Min - Max 容斥在 O ( 2 n ) O(2^n) O(2n) 的复杂度下计算出答案。
那么要怎么算呢？
显然如果直接枚举子集计算的话需要 O ( 3 n ) O(3^n) O(3n)， n ≤ 20 n\le 20 n≤20，肯定要炸，所以考虑优化。
我们知道 FMT 计算按位或卷积的时候我们执行了这样一个 O ( n log n ) O(n\log n) O(nlogn) 的过程：
定义 FMT ( f ) n = ∑ i ⊆ n f i \text{FMT}(f)_n=\sum_{i\subseteq n}f_i FMT(f)n=∑i⊆nfi
FMT ( a ) n × FMT ( b ) n = ∑ i ⊆ n a i ∑ j ⊆ n b j = ∑ k ⊆ n ∑ i ∪ j = k a i b j = FMT ( c ) n \begin{aligned} &\text{FMT}(a)_n\times \text{FMT}(b)_n\\ &{=\sum_{i\subseteq n}a_i\sum_{j\subseteq n}b_j}\\ &{=\sum_{k\subseteq n}\sum_{i∪j=k}a_ib_j}\\ &{=\text{FMT}(c)_n} \end{aligned} FMT(a)n×FMT(b)n=i⊆n∑aij⊆n∑bj=k⊆n∑i∪j=k∑aibj=FMT(c)n
好嘛，FMT 就是枚举子集…
即：序列经历过一次 FMT 按位或变换之后得到的新的序列就是原序列的子集和形式！
因此我们可以直接利用一次 FMT 在 O ( m log m ) , m = 2 n O(m\log m),m=2^{n} O(mlogm),m=2n 的复杂度下计算出所有的 P ( w ) = ∑ w ⊂ W P ( w ) P(w)=\displaystyle\sum\limits_{w\subset W}P(w) P(w)=w⊂W∑P(w)，然后利用 Min - Max 容斥在 O ( 2 n ) O(2^n) O(2n) 的复杂度下计算出答案即可。
Code
// Problem: P3175 [HAOI2015]按位或
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3175
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 7;
int n, m, s, t, k, a[N];
double ans;
double p[N];
int cnt[N];
void FMT_OR(double *f, int n, double x = 1.0)
{
for (int o = 2; o <= n; o <<= 1) {
for (int i = 0, k = o >> 1; i <= n; i += o) {
for (int j = 0; j < k; ++ j) {
f[i + j + k] = f[i + j] * x + f[i + j + k];
}
}
}
}
int main()
{
scanf("%d", &n);
int S = (1 << n) - 1;
int limit = 1;
while(limit <= S) limit <<= 1;
for (int i = 0; i <= S; ++ i)
scanf("%lf", &p[i]);
FMT_OR(p, limit);
for (int i = 1; i <= S; ++ i)
cnt[i] = cnt[i >> 1] + (i & 1);
ans = 0;
for (int i = 1; i <= S; ++ i) {
int SminusT = S ^ i;
if(1 - p[SminusT] < 1e-8)
return puts("INF"), 0;
ans += 1.0 / (1.0 - p[SminusT]) * (cnt[i] & 1 ? 1 : -1);
}
printf("%.10f\n", ans);
return 0;
}
Problem C. 重返现世 （Luogu P4707）
为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 n n n 种原料，只需要集齐任意 k k k 种，就可以开始制作。
Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 i i i 种原料被生成的概率是 p i m \cfrac{p_i}{m} mpi 。如果 Yopilla 没有这种原料，那么就可以进行收集。
Yopilla 急于知道，他收集到任意 k k k 种原料的期望时间，答案对 998244353 998244353 998244353 取模。
Solution
https://www.luogu.com.cn/blog/Sooke/solution-p4707
0x49 拉格朗日反演
● 基本性质定理
对于两个多式 F ( x ) , G ( x ) F(x),G(x) F(x),G(x)，两个多项式都是常数项均为 0 0 0 且 1 1 1 次项不为 0 0 0，如果有 F ( G ( x ) ) = x F(G(x))=x F(G(x))=x ，我们称 F , G F,G F,G 互为复合逆，同时一定有 G ( F ( x ) ) = x G(F(x))=x G(F(x))=x ，即可称 G ( x ) = F − 1 ( x ) , F ( x ) = G − 1 ( x ) G(x)=F^{-1}(x),F(x)=G^{-1}(x) G(x)=F−1(x),F(x)=G−1(x) 。
在这种情况下，拉格朗日反演
[ x n ] F ( x ) = 1 n [ x − 1 ] ( 1 G ( x ) ) n = 1 n [ x n − 1 ] ( x G ( x ) ) n \displaystyle [x^n]F(x)=\frac{1}{n}[x^{-1}](\frac{1}{G(x)})^n=\frac{1}{n}[x^{n-1}](\frac{x}{G(x)})^n [xn]F(x)=n1[x−1](G(x)1)n=n1[xn−1](G(x)x)n
扩展拉格朗日反演
[ x n ] H ( F ( x ) ) = 1 n [ x − 1 ] H ′ ( x ) ( 1 G ( x ) ) n = 1 n [ x n − 1 ] H ′ ( x ) ( x G ( x ) ) n [x^n]H(F(x))=\frac{1}{n}[x^{-1}]H'(x)(\frac{1}{G(x)})^n=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{G(x)})^n [xn]H(F(x))=n1[x−1]H′(x)(G(x)1)n=n1[xn−1]H′(x)(G(x)x)n
Problem A. 大朋友和多叉树（BZOJ 3684）
我们的大朋友很喜欢计算机科学，而且尤其喜欢多叉树。对于一棵带有正整数点权的有根多叉树，如果它满足这样的性质，我们的大朋友就会将其称作神犇的：点权为
1
1
1 的结点是叶子结点；对于任一点权大于
1
1
1 的结点
u
u
u，
u
u
u 的孩子数目 deg[u] 属于集合
D
D
D ，且
u
u
u 的点权等于这些孩子结点的点权之和。
给出一个整数
s
s
s ，你能求出根节点权值为
s
s
s 的神犇多叉树的个数吗？请参照样例以更好的理解什么样的两棵多叉树会被视为不同的。
我们只需要知道答案关于
950009857
950009857
950009857 （
453
×
2
21
+
1
453\times 2^{21}+1
453×221+1，一个质数）取模后的值。
1 ≤ m < s ≤ 1 0 5 , 2 ≤ d [ i ] ≤ s 1\le m<s\le 10^5, 2\le d[i]\le s 1≤m<s≤105,2≤d[i]≤s
Solution
显然计数问题，我们可以写出二叉树的个数的生成函数为：
H ( x ) = x + ∏ i ∈ D H i ( x ) ⇒ H ( x ) − ∏ i ∈ D H i ( x ) = x H(x)=x+\prod_{i\in D}H^i(x)\\\Rightarrow H(x)-\prod_{i\in D}H^i(x)=x H(x)=x+i∈D∏Hi(x)⇒H(x)−i∈D∏Hi(x)=x
令 F ( x ) = H ( x ) F(x)=H(x) F(x)=H(x), G ( x ) = x − ∏ i ∈ D x i G(x)=x-\prod_{i\in D}x^i G(x)=x−∏i∈Dxi，显然有 G ( F ( x ) ) = x G(F(x))=x G(F(x))=x
因此我们就可以进行拉格朗日反演：
[ x n ] F ( x ) = 1 n [ x − 1 ] 1 G ( x ) n [x^n]F(x)=\frac{1}{n}[x^{-1}]\frac{1}{G(x)^n} [xn]F(x)=n1[x−1]G(x)n1
显然直接辅以多项式全家桶暴力计算即可在 O ( n log n ) O(n\log n) O(nlogn) 的时间复杂度下求出 T ( s ) T(s) T(s) 即为答案。
0x4A 反演常用技巧
反演往往是通过一系列和式变换，将一个无法承受的时间复杂度优化到一个可以接收的时间复杂度下，
技巧4A.1 ：无关项提前
∑ i = 1 n ∑ j = 1 m n a i b j = n ∑ i = 1 n a i ∑ j = 1 m b j \sum_{i=1}^n\sum_{j=1}^mna_ib_j=n\sum_{i=1}^na_i\sum_{j=1}^mb_j i=1∑nj=1∑mnaibj=ni=1∑naij=1∑mbj
技巧4A.2 ：交换枚举顺序
∑ i = 1 n a i ∑ j = 1 m b j = ∑ j = 1 m b j ∑ i = 1 n a i \sum_{i=1}^na_i\sum_{j=1}^mb_j=\sum_{j=1}^mb_j\sum_{i=1}^na_i i=1∑naij=1∑mbj=j=1∑mbji=1∑nai
∑ i = 1 n a i ∑ d ∣ i b d = ∑ d = 1 n b d ∑ i = 1 ⌊ n d ⌋ a i d \sum_{i=1}^na_i\sum_{d|i}b_d=\sum_{d=1}^nb_d\sum_{i=1}^{\lfloor\frac nd\rfloor}a_{id} i=1∑naid∣i∑bd=d=1∑nbdi=1∑⌊dn⌋aid
这样可以将枚举的约数变成枚举倍数。
技巧4A.3 ：暴力破解法
无从下手的时候，多一个暴力枚举判断，多一重枚举，构造出判断式，尝试构造 ε = [ n = 1 ] \varepsilon=[n=1] ε=[n=1] 进行反演。
∑ i = 1 n ∑ j = 1 m f ( gcd ( i , j ) ) = ∑ d = 1 m i n ( n , m ) ∑ i = 1 n ∑ j = 1 m f ( d ) [ gcd ( i , j ) = d ] = ∑ d = 1 m i n ( n , m ) f ( d ) ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = d ] ⋯ \begin{aligned}&\ \ \ \ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j))&\\& =\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^mf(d)[\gcd(i,j)=d]&\\& =\sum_{d=1}^{min(n,m)}f(d)\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]&\\& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \end{aligned} i=1∑nj=1∑mf(gcd(i,j))=d=1∑min(n,m)i=1∑nj=1∑mf(d)[gcd(i,j)=d]=d=1∑min(n,m)f(d)i=1∑nj=1∑m[gcd(i,j)=d] ⋯
技巧4A.4 ：减少未知数
∑
p
∣
k
∑
d
=
1
⌊
n
p
⌋
μ
(
d
)
⌊
n
p
d
⌋
⌊
m
p
d
⌋
\displaystyle \sum_{p|k}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor
p∣k∑d=1∑⌊pn⌋μ(d)⌊pdn⌋⌊pdm⌋
可以令
k
=
p
d
k=pd
k=pd（尽量减少未知数，减少枚举）
∑
p
∣
k
∑
d
=
1
⌊
n
p
⌋
μ
(
k
p
)
⌊
n
k
⌋
⌊
m
k
⌋
\displaystyle \sum_{p|k}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(\frac{k}{p})\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor
p∣k∑d=1∑⌊pn⌋μ(pk)⌊kn⌋⌊km⌋
技巧4A.5：狄利克雷卷积优化
尽力拼凑成积性函数卷积的形式
∑ d = 1 n d 3 ∑ k = 1 ⌊ n d ⌋ μ ( k ) k 2 ( ∑ i = 1 ⌊ n d k ⌋ i ) 2 = ∑ T = 1 n T 2 μ ( T d ) d ( ∑ i = 1 ⌊ n d k ⌋ i ) 2 = ∑ T = 1 n T 2 φ ( T d × d ) ( ∑ i = 1 ⌊ n d k ⌋ i ) 2 = ∑ T = 1 n T 2 φ ( T ) ∑ i = 1 ⌊ n d k ⌋ i 3 \begin{aligned}&\ \ \ \ \ \sum_{d=1}^nd^3\sum_{k=1}^{\left\lfloor\frac n d\right\rfloor}\mu(k)k^2(\sum_{i=1}^{\left\lfloor\frac n {dk}\right\rfloor}i)^2&\\&=\sum_{T=1}^{n}T^2\mu(\frac T d)d(\sum_{i=1}^{\left\lfloor\frac n {dk}\right\rfloor}i)^2&\\&=\sum_{T=1}^{n}T^2\varphi(\frac T d \times d)(\sum_{i=1}^{\left\lfloor\frac n {dk}\right\rfloor}i)^2&\\&=\sum_{T=1}^{n}T^2\varphi(T)\sum_{i=1}^{\left\lfloor\frac n {dk}\right\rfloor}i^3\end{aligned} d=1∑nd3k=1∑⌊dn⌋μ(k)k2(i=1∑⌊dkn⌋i)2=T=1∑nT2μ(dT)d(i=1∑⌊dkn⌋i)2=T=1∑nT2φ(dT×d)(i=1∑⌊dkn⌋i)2=T=1∑nT2φ(T)i=1∑⌊dkn⌋i3
技巧4A.6：前缀和公式
1 + 2 + 3 + ⋯ + ( n − 1 ) = 1 2 n 2 − 1 2 n = n ( n − 1 ) 2 1 2 + 2 2 + 3 2 + ⋯ + ( n − 1 ) 2 = 1 3 n 3 − 1 2 n 2 + 1 6 n = n ( n − 1 ) ( 2 n − 1 ) 6 1 3 + 2 3 + 3 3 + ⋯ + ( n − 1 ) 3 = 1 4 n 4 − 1 2 n 3 + 1 4 n 2 = n 2 ( n − 1 ) 2 4 1 4 + 2 4 + 3 4 + ⋯ + ( n − 1 ) 4 = 1 5 n 5 − 1 2 n 4 + 1 3 n 3 − n 30 = n ( n − 1 ) ( 2 n − 1 ) ( 3 n 2 − 3 n − 1 ) 30 1 5 + 2 5 + 3 5 + ⋯ + ( n − 1 ) 5 = 1 6 n 6 − 1 2 n 5 + 5 12 n 4 − 1 12 n 2 = n 2 ( n − 1 ) 2 ( 2 n 2 − 2 n − 1 ) 12 \begin{aligned}&1+2+3+\cdots+(n-1)\ \ \ \ \ \ =\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \frac 1 2n^2-\frac 1 2n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \frac{n(n-1)} 2&\\&1^2+2^2+3^2+\cdots+(n-1)^2=\ \ \ \ \ \ \ \ \ \ \ \frac 1 3n^3-\frac 1 2 {n^2} +\frac 1 6n \ \ \ \ \ \ \ = \frac{n(n-1)(2n-1)} 6&\\&1^3+2^3+3^3+\cdots+(n-1)^3=\ \ \ \ \ \ \ \ \ \frac 1 4n^4-\frac 1 2 {n^3} +\frac 1 4n^2\ \ \ \ \ \ \ = \frac{n^2(n-1)^2} 4&\\&1^4+2^4+3^4+\cdots+(n-1)^4=\ \ \ \ \frac 1 5 n^5-\frac 1 2n^4+\frac 1 3 n^3-\frac n {30} \ \ =\frac{n(n-1)(2n-1)(3n^2-3n-1)}{30}&\\&1^5+2^5+3^5+\cdots+(n-1)^5=\frac 1 6n^6-\frac 1 2 n^5+\frac 5 {12}n^4-\frac 1 {12}n^2=\frac{n^2(n-1)^2(2n^2-2n-1)}{12}\end{aligned} 1+2+3+⋯+(n−1) = 21n2−21n =2n(n−1)12+22+32+⋯+(n−1)2= 31n3−21n2+61n =6n(n−1)(2n−1)13+23+33+⋯+(n−1)3= 41n4−21n3+41n2 =4n2(n−1)214+24+34+⋯+(n−1)4= 51n5−21n4+31n3−30n =30n(n−1)(2n−1)(3n2−3n−1)15+25+35+⋯+(n−1)5=61n6−21n5+125n4−121n2=12n2(n−1)2(2n2−2n−1)
证明
规定 C ( n , k ) C(n,k) C(n,k) 表示从 n n n 个数中取 k k k 个的组合数。
2 n + 1 = 1 + C ( n + 1 , 1 ) 1 n + C ( n + 1 , 2 ) 1 n − 1 + C ( n + 1 , 3 ) 1 n − 2 + ⋯ + C ( n + 1 , n + 1 ) 2^{n+1}=1+C(n+1,1)1^n+C(n+1,2)1^{n-1}+C(n+1,3)1^{n-2}+\cdots+C(n+1,n+1) 2n+1=1+C(n+1,1)1n+C(n+1,2)1n−1+C(n+1,3)1n−2+⋯+C(n+1,n+1)
3 n + 1 = 2 n + 1 + C ( n + 1 , 1 ) 2 n + C ( n + 1 , 2 ) 2 n − 1 + c ( n + 1 , 3 ) 2 n − 2 + ⋯ + c ( n + 1 , n + 1 ) 3^{n+1}=2^{n+1}+C(n+1,1)2^n+C(n+1,2)2^{n-1}+c(n+1,3)2^{n-2}+\cdots+c(n+1,n+1) 3n+1=2n+1+C(n+1,1)2n+C(n+1,2)2n−1+c(n+1,3)2n−2+⋯+c(n+1,n+1)
…
( n + 1 ) n + 1 = n n + 1 + C ( n + 1 , 1 ) n n + C ( n + 2 , 2 ) n n − 1 + ⋯ + C ( n + 1 , n + 1 ) (n+1)^{n+1}=n^{n+1}+C(n+1,1)n^n+C(n+2,2)n^{n-1}+\cdots+C(n+1,n+1) (n+1)n+1=nn+1+C(n+1,1)nn+C(n+2,2)nn−1+⋯+C(n+1,n+1)
上面 n n n 个式子相加
( n + 1 ) n + 1 = 1 + ( n + 1 ) ( 1 n + 2 n + . . . + n n ) + C ( n + 2 , 2 ) ( 1 n − 1 + 2 n − 1 + . . . + n n − 1 ) + . . . + C ( n + 1 , n ) ( 1 + 2 + 3 + . . . + n ) + n (n+1)^{n+1}=1+(n+1)(1^n+2^n+...+n^n)+C(n+2,2)(1^{n-1}+2^{n-1}+...+n^{n-1})+...+C(n+1,n)(1+2+3+...+n)+n (n+1)n+1=1+(n+1)(1n+2n+...+nn)+C(n+2,2)(1n−1+2n−1+...+nn−1)+...+C(n+1,n)(1+2+3+...+n)+n
整理得
1 n + 2 n + ⋯ + n n = ( n + 1 ) n − 1 n + 1 − ( 1 n + 1 ) ( C ( n + 2 , 2 ) ( 1 n − 1 + 2 n − 1 + . . + n n − 1 ) + . . . + C ( n + 1 , n ) ( 1 + 2 + 3 + ⋯ + n ) + n ) 1^n+2^n+\cdots+n^n=(n+1)^n-\frac 1 {n+1}-(\frac 1 {n+1})(C(n+2,2)(1^{n-1}+2^{n-1}+..+n^{n-1})+...+C(n+1,n)(1+2+3+\cdots+n)+n) 1n+2n+⋯+nn=(n+1)n−n+11−(n+11)(C(n+2,2)(1n−1+2n−1+..+nn−1)+...+C(n+1,n)(1+2+3+⋯+n)+n)
我们知道 1 1 1 次的前缀和为: 1 + 2 + ⋯ + n = n ( 1 + n ) 2 1+2+\cdots+n=\cfrac {n(1+n)} 2 1+2+⋯+n=2n(1+n)
因此我们就可以递推得到 2 2 2次， 3 3 3 次，乃至 n n n 次前缀和公式
0x4B. Dirichlet 前缀和
0x4B.1 Dirichlet 前缀和
Template Problem Dirichlet 前缀和 （P5495）
给定一个长度为 n n n 的数列 a 1 , a 2 , a 3 , … , a n a_1,a_2,a_3,\dots,a_n a1,a2,a3,…,an 。
现在你要求出一个长度为 n n n 的数列 b 1 , b 2 , b 3 , … , b n b_1,b_2,b_3,\dots,b_n b1,b2,b3,…,bn ，满足
b d = ∑ i ∣ d a i b_d=\sum_{i|d}a_i bd=i∣d∑ai
Solution
如果我们直接枚举倍数的话显然可以做到 O ( ∑ i = 1 n ⌊ n i ⌋ ) = O ( n log n ) \displaystyle O(\sum_{i=1}^n\left\lfloor\cfrac n i\right\rfloor)=O(n\log n) O(i=1∑n⌊in⌋)=O(nlogn) ，考虑优化。
根据唯一分解定理，我们可以设 i = ∏ p d α d , j = ∏ p d β d \displaystyle i=\prod p_d^{\alpha_d},j=\prod p_d^{\beta_d} i=∏pdαd,j=∏pdβd ，则 a i a_i ai 贡献到 b j b_j bj 当且仅当 ∀ d , α d ≤ β d \forall d,\alpha_d\leq \beta_d ∀d,αd≤βd。
发现这个实际上就是一个关于质因子分解后的指数的高维前缀和（例如FMT），即每个数字会被它除以所有质因子的那个数转移过来，所有的质因子构成了一组正交基，核心代码：
for(int i = 1; i <= cnt && primes[i] <= n; ++ i)
for(int j = 1; j * primes[i] <= n; ++ j)
a[j * primes[i]] += a[j];
显然时间复杂度同埃氏筛： O ( n log log n ) O(n\log \log n) O(nloglogn)
Code
#define uint unsigned int
uint seed;
inline uint getnext() {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return seed;
}
uint a[N], b[N];
uint ans;
int n, m;
bool vis[N];
int primes[N], cnt;
void get_primes(int n)
{
for(int i = 2; i <= n; ++ i) {
if(vis[i] == 0)
primes[ ++ cnt] = i;
for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
vis[i * primes[j]] = true;
if(i % primes[j] == 0) break;
}
}
}
int main()
{
get_primes(N - 1);
scanf("%d%u", &n, &seed);
for(int i = 1; i <= n; ++ i)
a[i] = getnext();
for(int i = 1; i <= cnt && primes[i] <= n; ++ i)
for(int j = 1; j * primes[i] <= n; ++ j)
a[j * primes[i]] += a[j];
ans = a[1];
for(int i = 2; i <= n; ++ i)
ans ^= a[i];
printf("%u\n", ans);
return 0;
}
0x4B.2 Dirichlet 后缀和
b [ i ] = ∑ i ∣ d a [ d ] b[i] = \sum_{i|d} a[d] b[i]=i∣d∑a[d]
我们这里是从一个数字本身 转移到 这个数字除以所有质因子的数。
for(int i = 1; i <= cnt && primes[i] <= n; ++ i)
for(int j = n / primes[i]; j ; -- j)
a[j] += a[j * primes[i]];
0x4B.2 倒推 Dirichlet 前缀和
b [ i ] = ∑ d ∣ i a [ d ] b[i] = \sum_{d|i} a[d] b[i]=d∣i∑a[d]
这里是我们知道数组 b b b ，求数组 a a a
for(int i = cnt; i ; -- i)
for(int j = n / primes[i]; j ; -- j)
a[j * primes[i]] -= a[j];
0x4B.3 倒推 Dirichlet 后缀和
b [ i ] = ∑ i ∣ d a [ d ] b[i] = \sum_{i|d} a[d] b[i]=i∣d∑a[d]
同上，我们知道数组 b b b ，求数组 a a a
for(int i = cnt; i ; -- i)
for(int j = 1; j * primes[i] <= n; ++ j)
a[j] -= a[j * primes[i]];
本小节部分内容来源于二项式反演及其应用@GXZlegend ↩︎
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
