【ALGO】容斥原理和莫比乌斯函数

文章导航

• Mobius函数
• • 模板代码
• 例题
• • ACW 214. Devu and Flowers
  • • 题面
    • 解析
    • AC代码
  • ACW 215. 破译密码
  • • 题面
    • 解析
    • AC代码

Mobius函数

定义 F ( n ) F(n) F(n)和 f ( n ) f(n) f(n)是定义在非负整数集合上的两个函数，并且满足条件 F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d\mid n}f(d) F(n)=∑d∣n​f(d)，可以得到方程

f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum_{d\mid n}\mu(d)F(\frac{n}{d}) f(n)=d∣n∑​μ(d)F(dn​)

其中 μ ( d ) \mu(d) μ(d)函数定义如下

1. 当 d = 1 d=1 d=1，那么 μ ( d ) = 1 \mu(d)=1 μ(d)=1
2. 当 d = p 1 p 2 … p k d=p_1p_2\dots p_k d=p1​p2​…pk​， p i p_i pi​均为互异的素数，那么 μ ( d ) = ( − 1 ) k \mu(d)=(-1)^k μ(d)=(−1)k
3. 否则 μ ( d ) = 0 \mu(d)=0 μ(d)=0

μ ( d ) \mu(d) μ(d)函数有如下性质

1. 对于任意 n ∈ Z + n\in\mathbb{Z}^+ n∈Z+， ∑ d ∣ n μ ( d ) = { 1 n = 1 0 n > 1 \sum\limits_{d\mid n}\mu(d)=\left\{\begin{aligned}1 \quad n=1\\ 0 \quad n>1\end{aligned}\right. d∣n∑​μ(d)={1n=10n>1​
2. 对于任意 n ∈ Z + n\in \mathbb{Z}^+ n∈Z+， ∑ d ∣ n μ ( d ) d = ϕ ( n ) n \sum\limits_{d\mid n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n} d∣n∑​dμ(d)​=nϕ(n)​

模板代码

使用线性筛求Mobius函数代码

void Mobius(int n){
	memset(primes, 0x00, sizeof primes);
	memset(vis, 0x00, sizeof vis);
	memset(mu, 0x00, sizeof mu);
	mu[1]=1;
	int cnt=0;
	for(int i=2; i<=n; ++i){
		primes[cnt++]=i;
		mu[i]=-1;
	}
	for(int j=0; primes[j]<=n/i; ++j){
		vis[primes[j]*i]=true;
		if(i%primes[j]) mu[primes[j]*i]=-mu[i];
		else {mu[primes[j]*i]=0; break;}
	}
}
           

例题

ACW 214. Devu and Flowers

题目链接

题面

Devu有 N N N个盒子，第 i i i个盒子中有 A i A_i Ai​枝花。同一个盒子内的花颜色相同，不同盒子内的花颜色不同.

Devu要从这些盒子中选出 M M M枝花组成一束，求共有多少种方案.

若两束花每种颜色的花的数量都相同，则认为这两束花是相同的方案.

结果需对 1 e 9 + 7 1e9+7 1e9+7取模之后方可输出。

解析

先考虑每个盒子中花的数量为无限个的情况

不妨假设第 i i i个盒子选 x i x_i xi​朵花，所以满足等式

x 1 + x 2 + ⋯ + x N = M 0 ≤ x i (1) \begin{aligned} & x_1+x_2+\dots+x_N=M\\ & 0\leq x_i \tag{1} \end{aligned} ​x1​+x2​+⋯+xN​=M0≤xi​​(1)

因此方案数为方程 ( 1 ) (1) (1)的非负整数解的个数.

令 y i = x i + 1 y_i=x_i+1 yi​=xi​+1，方程转化为

y 1 + y 2 + ⋯ + y N = M + N y i ≥ 1 (2) \begin{aligned} &y_1+y_2+\dots+y_N=M+N\\ &y_i\geq 1\tag{2} \end{aligned} ​y1​+y2​+⋯+yN​=M+Nyi​≥1​(2)

使用隔板法可以计算出等效方程 ( 2 ) (2) (2)的方案数为 C M + N − 1 N − 1 C_{M+N-1}^{N-1} CM+N−1N−1​.

考虑带有 A i A_i Ai​限制的情况

限制条件为 x 1 ≤ A 1 , x 2 ≤ A 2 … , x n ≤ A n x_1\leq A_1, x_2\leq A_2\dots, x_n\leq A_n x1​≤A1​,x2​≤A2​…,xn​≤An​，不妨从反面的角度，计算不满足限制条件的方案数，根据容斥原理求解.

不妨设不满足限制 x i ≤ A i x_i\leq A_i xi​≤Ai​的方案数为 ∣ S i ∣ \lvert S_i\rvert ∣Si​∣，因此总方案数为

C M + N − 1 N − 1 − ∣ S 1 ∪ S 2 ∪ ⋯ ∪ S n ∣ = C M + N − 1 N − 1 − ( ∣ S 1 ∣ + ∣ S 2 ∣ + … ∣ S n ∣ ) + ( ∣ S 1 ∩ S 2 ∣ + ⋯ + ∣ S n − 1 ∩ S n ∣ ) − ( ∣ S 1 ∩ S 2 ∩ S 3 ∣ + …   ) + ( − 1 ) n ( ∣ … ∣ ) = C M + N − 1 N − 1 − ∑ i C M + N − A i − 2 N − 1 + ∑ i < j C M + N − A i − A j − 2 N − 1 + ⋯ + ( − 1 ) n ∑ ( …   ) \begin{aligned} &C_{M+N-1}^{N-1}-\lvert S_1 \cup S_2\cup \dots \cup S_n\rvert \\ =&C_{M+N-1}^{N-1}-(\lvert S_1\rvert+\lvert S_2\rvert+\dots \lvert S_n \rvert)+(\lvert S_1\cap S_2\rvert+\dots+|S_{n-1}\cap S_n|)-(\lvert S_1\cap S_2\cap S_3\rvert+\dots)+(-1)^n(\lvert\dots\rvert)\\ =&C_{M+N-1}^{N-1}-\sum_iC_{M+N-A_i-2}^{N-1}+\sum_{i<j}C_{M+N-A_i-A_j-2}^{N-1}+\dots+(-1)^n\sum(\dots) \end{aligned} ==​CM+N−1N−1​−∣S1​∪S2​∪⋯∪Sn​∣CM+N−1N−1​−(∣S1​∣+∣S2​∣+…∣Sn​∣)+(∣S1​∩S2​∣+⋯+∣Sn−1​∩Sn​∣)−(∣S1​∩S2​∩S3​∣+…)+(−1)n(∣…∣)CM+N−1N−1​−i∑​CM+N−Ai​−2N−1​+i<j∑​CM+N−Ai​−Aj​−2N−1​+⋯+(−1)n∑(…)​

AC代码

#include <cstring>
#include <iostream>

using namespace std;
typedef long long LL;
const int N=20;
const int mod=1e9+7;
LL A[N];
int down=1;

int qmi(int a, int k, int p){ // a^k%p
    int ans=1;
    while(k){
        if(k&0x01) ans=(LL)ans*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return ans;
}

LL C(LL a, LL b){
    if(a<b) return 0;
    int up=1;
    for(LL i=a; i>a-b; --i) up=i%mod*up%mod;
    return (LL)up*down%mod;
}

int main(){
    LL n, m;
    cin>>n>>m;
    for(int i=0; i<n; ++i) cin>>A[i];
    for(int j=1; j<=n-1; j++) down=(LL)j*down%mod;
    down=qmi(down, mod-2, mod); // 费马小定理
    LL ans=0;
    for(int i=0; i<1<<n; ++i){
        LL a=m+n-1, b=n-1;
        int sgn=1;
        for(int j=0; j<n; ++j){
            if(i>>j & 0x01){
                sgn*=-1;
                a-=A[j]+1;
            }
        }
        ans=(ans+C(a, b)*sgn)%mod;
    }
    cout<<(ans%mod+mod)%mod<<endl;
    return 0;
}
           

ACW 215. 破译密码

题目链接

题面

对于给定的整数 a , b a,b a,b和 d d d，有多少正整数对 x , y x,y x,y，满足 x < = a ， y < = b x<=a，y<=b x<=a，y<=b，并且 gcd ⁡ ( x , y ) = d \gcd(x,y)=d gcd(x,y)=d

解析

对mobius函数计算前缀和求解

AC代码

#include <cstring>
#include <iostream>

using namespace std;

typedef long long LL;
const int N=50005;

int primes[N], cnt=0;
bool vis[N];
int mob[N], sum[N];

void mobius(int n){ // 线性筛求mobius
    mob[1]=1;
    for(int i=2; i<=n; ++i){
        if(!vis[i]){primes[cnt++]=i; mob[i]=-1;}
        for(int j=0; primes[j]<=n/i; ++j){
            int t=primes[j]*i;
            vis[t]=true;
            if(i%primes[j]==0){mob[t]=0; break;}
            mob[t]=mob[i]*(-1);
        }
    }
    
    // 计算mobius函数的前缀和
    for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+mob[i];
}

int main(){
    mobius(N);
    int T;
    cin>>T;
    while(T--){
        int a, b, d;
        cin>>a>>b>>d;
        a/=d, b/=d;
        int n=min(a, b);
        LL ans=0;
        for(int l=1, r; l<=n; l=r+1){
            r=min(n, min(a/(a/l), b/(b/l)));
            ans+=(sum[r]-sum[l-1])*(LL)(a/l)*(b/l);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}