容斥原理

用户头像 发布于 21 天前 104 次阅读 OI

数学2（容斥原理）

P3197 [HNOI2008] 越狱

发生越狱的状态数=总状态数-不越狱的状态数，
很显然总状态数为 $m^n$，
而不越狱的状态数应该是同样宗教互不相邻，
第一个房间有 $m$ 种，其他房间都是 $m-1$ 种，
所以状态数应该是 $m·(m-1)^{n-1}$。
答案：$m^n-m·(m-1)^{n-1}$
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=100003;
int m,n;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}
signed main(){
	cin>>m>>n;
	cout<<(mi(m,n)-m*mi(m-1,n-1)%mod+mod)%mod;
	return 0;
}

P8557 炼金术（Alchemy）

显而易见，对于每一种矿物，至少需要分配到一个熔炉，
方案数为总集减去空集，即 $2^k-1$。
而一共有 $n$ 个矿物，每个矿物有 $2^k-1$种方案，
所以答案就是 $(2^k-1)^n$
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,k;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans%mod;
}
signed main(){
	cin>>n>>k;
	cout<<mi((mi(2,k)-1),n);
	return 0;
}

P6298 齿轮

首先统计每个齿数的出现频率 $t[x]$，
并预处理组合数 $\binom{n}{k} \bmod M$ 用于快速计算。
接着对于每个数 $i$，
统计所有齿数为 $i$ 的倍数的齿轮个数 $f[i] = \sum_{j=i, 2i, \dots}^{j \le m} t[j]$，
这表示最大公约数是 $i$ 的倍数的候选齿轮数。
然后利用容斥原理，从大到小计算 $ans[i] = \binom{f[i]}{k} - \sum_{j=2}^{\lfloor m/i \rfloor} ans[i \cdot j]$，
这样 $ans[i]$ 就表示最大公约数恰好为 $i$ 的方案数。
最后输出 $ans[1]$ 到 $ans[m]$ 即为所有损耗因子的答案。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=1e9+7;
int n,m,k;
int a[N],ans[N],t[N],f[N],j[N],jj[N];

int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}

int C(int x,int y){
    if(x<0||y<0||x>y) return 0;
    return j[y]*jj[x]%mod*jj[y-x]%mod;
}

signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        t[a[i]]++;
    }
    j[0]=jj[0]=1;
    for(int i=1;i<=n;i++){
        j[i]=j[i-1]*i%mod;
        jj[i]=mi(j[i],mod-2);
    }
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j+=i){
            f[i]+=t[j];
        }
    }
    for(int i=m;i>=1;i--){
        ans[i]=C(k,f[i]);
        for(int j=i*2;j<=m;j+=i){
            ans[i]=(ans[i]-ans[j]+mod)%mod;
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<" ";
    return 0;
}