数学学习笔记6

一月 13, 2024

积性函数

对于 $a,b$ 满足 $(a,b)=1$，则 $f(ab)=f(a)f(b)$，那么 $f$ 函数称为积性函数。

$f$ 函数必须是数论函数。（仅限于下面的讨论）

我们有以下常见的积性函数：

常数函数 $1(n)=1$，单位函数 $\epsilon(n)=[n=1]$，恒等函数 $\operatorname{Id}(n)=n$，$k$ 次幂函数 $\operatorname{Id}^k(n)$。

还有欧拉函数 $\varphi$、莫比乌斯函数 $\mu$，约数 $k$ 次方和函数 $\sigma^k$ 等等函数。

以下主要介绍莫比乌斯函数。

莫比乌斯函数

$$
\mu(n)=\begin{cases}
1 & n=1\\
(-1)^k & n=p_1p_2\dots p_k \\
0 & \text{Otherwise}
\end{cases}
$$

其中有 $\sum_{d \mid n}\mu(d)=[n=1]$，证明如下：

当 $n=1$ 的时候答案显然成立。

否则设 $n$ 有 $k$ 个不同的质因数，那么有答案等于 $\sum_{i=0}^k C_{i}^{k}(-1)^i=(-1+1)^k$，$k$ 一定大于等于 $1$，此式一定等于 $0$。

狄利克雷卷积

卷积是定义与两个数论函数之间的操作：

$$
h = f*g
$$

其中 $h(n) = \sum_{d \mid n}f(d)g(\frac nd)$。

狄利克雷卷积显然满足交换律 $f*g=g*f$，结合律 $(f*g)*h=f*(g*h)$，对加法的分配律 $(f+g)*h=f*h+g*h$。

如果是三个函数一起做卷积，那么可以写成：

$$
ff(n)=\sum_{d_1d_2d_3=n}f(d_1)g(d_2)h(d_3)
$$

计算

暴力算两个函数的卷积可以直接枚举倍数 $O(n \log n)$ 计算。

但是如果 $g=1$ 的时候我们可以用狄利克雷前缀和做到 $O(n \log \log n)$ 的时间复杂度。

也就是 $h_n = \sum_{d \mid n}f_n$，具体地，枚举每个质因子，把每个质因子当做一个维度，做高维前缀和即可。

代码如下：

for(int i=1;i<=tot;i++){
	for(int j=1;j*pri[i]<=n;j++){
		f[j*pri[i]]+=f[j];
		if(f[j*pri[i]]>=mod) f[j*pri[i]]-=mod;
	}
}

同理可以定义狄利克雷后缀和，但是要注意我们的枚举顺序：

for(int i=1;i<=tot;i++){
	for(int j=n/pri[i];j>=1;j--){
		f[j]+=f[j*pri[i]];
		if(f[j]>=mod) f[j]-=mod;
	}
}

性质

两个积性函数的狄利克雷卷积也是积性函数。

因此我们可以 $O(n)$ 计算出两个积性函数的狄利克雷卷积，只需要求出 $f(p^k)$，然后合并即可。

推论：积性函数的狄利克雷前缀和也是积性函数。

逆元

一个数论函数的逆元为存在 $f^{-1}$ 满足 $f^{-1} * f=\epsilon$。

当 $f(1)=1$ 的时候，存在 $f^{-1}$，否则不存在。

可以倒推求解，就会发现 $f_1$ 作为了分母，所以证明显然。

因为 $\sum_{d \mid n}\mu(d)=[n=1]$，所以 $\mu$ 函数的逆元是 $\epsilon$。

若有 $F=f * 1$，那么 $f = F * \mu$，证明只需要两边乘上 $\mu$ 函数即可。

关系式

$$
\mu \rightarrow^{*1} \varepsilon \rightarrow^{*1}1\rightarrow^{*1}d
$$

$$
\mu \leftarrow^{*\mu} \varepsilon \leftarrow^{*\mu}1\leftarrow^{*\mu}d
$$

$$
\varphi \rightarrow^{*1} \operatorname{Id} \rightarrow^{*1} \sigma
$$

$$
\varphi \leftarrow^{*\mu} \operatorname{Id} \leftarrow^{*\mu} \sigma
$$

杜教筛

在 $O(n^{\frac 23})$ 的时间复杂度内求出某个数论函数（不一定是积性函数） $f$ 的前缀和，下面以 $f=\varphi$ 和 $f = \mu$ 举例说明。

这个算法的本质在于构造 $g,h$ 满足 $f *g=h$，然后利用 $g,h$ 求出 $f$ 的前缀和，设我们要求 $S(k) = \sum_{i=1}^k f(i)$。

那么有 $\sum_{i=1}^n h(i) = \sum_{i=1}^n \sum_{d \mid i} f(d)g(\frac id)=\sum_{i=1}^n g(i)S(\lfloor \frac ni \rfloor)$。

于是就有 $S(n)g(1)=\sum_{i=1}^n h(i)-\sum_{i=2}^n g(i)S(\lfloor \frac ni \rfloor)$，于是直接数论分块+快速处理 $g,h$ 的前缀和就可以了。

这样直接记忆化搜索 $S$ 的话时间复杂度是 $O(n^{\frac 34})$，我们可以先线性筛出来 $S$ 的前 $n^{\frac 23}$ 项，时间复杂度就是 $O(n^{\frac 23})$ 了。

（前提是 $g$ 和 $h$ 的前缀和可以快速计算）

例如 $f = \varphi$，$g=I$，$h=Id$，于是可以直接计算。

或者 $f=\mu$，$g = I$，$h = \epsilon$，也可以直接计算。

示例代码如下：

#include<bits/stdc++.h>
#define ll long long
#define N 10000005
#define M 2000005
using namespace std;
ll T,n;
bool vis[N];
int mu[N],pri[N],tot;
long long phi[N];
inline void init(){
	phi[1] = 1,mu[1] = 1;
	for(ll i=2;i<=1e7;i++){
		if(!vis[i]) pri[++tot]=i,phi[i]=i-1,mu[i]=-1;
		for(ll j=1;j<=tot;j++){
			if(i*pri[j]>1e7) break;
			vis[i*pri[j]] = 1;
			if(i%pri[j]==0){
				phi[i*pri[j]] = phi[i]*pri[j],mu[i*pri[j]] = 0;
				break;
			}
			else{
				mu[i*pri[j]] = mu[i]*mu[pri[j]],phi[i*pri[j]] = phi[i]*(pri[j]-1);
			}
		}
	}
	for(ll i=1;i<=1e7;i++) phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}
struct hash_table{
	ll la[M],val[N],ne[N],tot;
	long long val2[N];
	inline long long found(ll x){
		ll temp = x%1999997;
		for(ll i=la[temp];i;i=ne[i]) if(val[i]==x) return val2[i];
		return -1;
	}
	inline void insert(ll x1,long long x2){
		ll temp = x1%1999997;
		tot++,ne[tot] = la[temp],la[temp] = tot,val[tot] = x1,val2[tot] = x2;
	}
}hash1,hash2;
inline long long solve1(ll x){
	if(x<=1e7) return phi[x];		
	long long temp = hash1.found(x);
	if(temp!=-1) return temp;	
	long long num = 1ll*x*(x+1)/2;
	for(ll i=2,r;i<=x;i=r+1){
		r = x/(x/i);
		num -= 1ll*(r-i+1)*solve1(x/i);
	}
	hash1.insert(x,num);
	return num;
}
inline ll solve2(ll x){
	if(x<=1e7) return mu[x];	
	ll temp = hash2.found(x);
	if(temp!=-1) return temp;
	ll num = 1;
	for(ll i=2,r;i<=x;i=r+1){
		r = x/(x/i);
		num -= (r-i+1)*solve2(x/i);
	}
	hash2.insert(x,num);
	return num;
}
int main(){
	init();
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n;
		cout<<solve1(n)<<" "<<solve2(n)<<endl;
	}
	return 0;
}

莫比乌斯反演

形式

莫比乌斯反演形式 1：
$$
F(n) = \sum_{d \mid n}f(d) \\
f(n) = \sum_{d \mid n}F(d)\mu(\frac nd)
$$
莫比乌斯反演形式 2（大部分推导公式）：
$$
\sum_{d \mid n}\mu(d)=\varepsilon(n)=[n=1]
$$
莫比乌斯反演形式 3（狄利克雷后缀和的反演）：
$$
F(n) = \sum_{n \mid d}f(d) \\
f(n) = \sum_{n \mid d}F(d)\mu(\frac dn)
$$
莫比乌斯反演形式 4：
$$
F(n) = \prod_{d \mid n}f(d) \\
f(n) = \prod_{d \mid n}F(d)^{\mu(\frac nd)}
$$

常见积性函数乘积展开

$$
\mu(ij)=\mu(i)\mu(j)[\gcd(i,j)=1] \\
\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} \\
d(ij)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1] \\
\sigma_k(ij)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1](\frac {xj}{y})^k
$$

特别注意，当 $\gcd(i,j)=1$ 的时候才有贡献的时候，可以默认 $\gcd(i,j)=1$。

例题

题面

$$
\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n \sum_{k=1}^{ij}[(i,k)=1][(j,k)=1]k
$$

其中 $n,m \le 10^7$，求出上式的值。时间复杂度在 $O(n \log \log n)$ 以内。

分析

推公式时间！

注意：

$$
\mu \ * \ \operatorname{Id} = \varphi
$$

特别地，当只有 $\gcd(i,j)=1$ 的时候这个项有贡献的时候，我们在进行拆函数（$\varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$）的时候可以默认 $\gcd(i,j)=1$，而不需要考虑其它情况。

下面是正式内容（中间有些常数直接省略了）：

$$
\begin{aligned}
& \ \ \ \ \ \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n \sum_{k=1}^{ij} [(i,k)=1][(j,k)=1]k \\
&=\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n \sum_{k=1}^{ij} [(k,ij)=1]k \\
&=\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n \sum_{k=1}^{ij} k \sum_{d \mid k,d \mid ij} \mu(d) \\
&=\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n \sum_{d \mid ij} \mu(d)d \sum_{k=1}^{\frac {ij} d}k \\
&=\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n \sum_{d \mid ij} \mu(d)\frac {(d+ij)\frac {ij} d}{2}\\
&=\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^n ij\varphi(ij)\\
&= \sum_{d=1}^{n} d^n \sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}[\gcd(i,j)=1]ijd^2\varphi(ijd^2) \\
&= \sum_{d=1}^{n} d^n \sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}[\gcd(i,j)=1]ijd^2\frac{\varphi(id)\varphi(jd)d}{\varphi(d)} \\
&= \sum_{d=1}^{n} \frac{d^{n+1}}{\varphi(d)} \sum_{i=1}^{\frac nd}id\varphi(id)\sum_{j=1}^{\frac md}[\gcd(i,j)=1]jd\varphi(jd) \\
&= \sum_{d=1}^{n} \frac{d^{n+1}}{\varphi(d)} \sum_{i=1}^{\frac nd}id\varphi(id)\sum_{j=1}^{\frac md}jd\varphi(jd) \sum_{k \mid i,k \mid j} \mu(k)\\
&= \sum_{1 \le k\le n} \mu(k) \sum_{d=1}^{n} \frac{d^{n+1}}{\varphi(d)} \sum_{i=1}^{\frac n{dk}}idk\varphi(idk)\sum_{j=1}^{\frac m{dk}}jdk\varphi(jdk) \\
T \gets dk \\
&= \sum_{T=1}^{n} \sum_{d \mid T} \mu(\frac Td )\frac{d^{n+1}}{\varphi(d)} \sum_{i=1}^{\frac n{T}}iT\varphi(iT)\sum_{j=1}^{\frac m{T}}jT\varphi(jT)
\end{aligned}
$$

$ f(T)=\sum_{d \mid T} \mu(\frac Td )\frac{d^{n+1}}{\varphi(d)}$ 是一个积性函数和积性函数的狄利克雷卷积，所以仍然是积性函数，我们求出 $f(p^k)$，再用线性筛合并即可。

后面两堆是一个狄利克雷后缀和，时间复杂度为 $O(n+n \log \log n)=O(n \log \log n)$。

二项式反演

两个公式在下面，记住基本上就会做题了：

$$
f(n)= \sum_{i=0}^n C_n^ig(i)\Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i}C_n^if(i)
$$

$$
f(n)= \sum_{i=n}^m C_i^n g(i)\Leftrightarrow g(n)=\sum_{i=n}^m (-1)^{i-n}C_i^nf(i)
$$

其中 $g(n)$ 是恰好 $n$ 个元素满足条件的方案数量，$f(n)$ 分别是至少/至多（钦定）$n$ 个元素满足条件的方案数量。

也就是说，同一个 $f(n)$ 中有可能有两组一模一样的方案在里面，但是这两组中我们钦定的那 $n$ 个元素一定（不）满足条件在两组中是不一样的。

例题：集合计数，题面如下：

一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $k$，求取法的方案数，答案模 $10^9+7$。

首先考虑构造 $f(i)$ 满足交集的元素个数至少为 $i$（钦定了 $i$ 个），那么首先就有钦定 $i$ 个的方案数 $C_n^i$，然后剩下的集合我们随便选择，也就是乘上 $2^{2^{n-i}}$。

记得要减去空集合的方案 $1$。

最后通过第一种形式得到 $g(k)$ 就可以了。

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define mod 1000000007 
using namespace std;
ll n,k,jc[N],i,inv[N],g[N],ans;
inline ll qmi(ll a,ll b,ll p){
	ll res = 1%p,t = a;
	while(b){
		if(b&1) res = res*t%p;
		t=t*t%p;
		b>>=1;
	}
	return res;
}
inline ll C(ll n,ll m){
	if(n<m) return 0;
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
	cin>>n>>k;
	jc[0]=1;
	for(i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
	inv[n]=qmi(jc[n],mod-2,mod);
	for(i=n;i>=1;i--) inv[i-1]=inv[i]*i%mod;
	for(i=0;i<=n;i++) g[i]=C(n,i)*(qmi(2,qmi(2,n-i,mod-1),mod)-1+mod)%mod;
	for(i=k;i<=n;i++) ans=(ans+C(i,k)*qmi(mod-1,i-k,mod)%mod*g[i]%mod)%mod;
	cout<<ans<<endl;
	return 0;
}

查看评论