容斥原理

容斥原理的基本原理是根据集合之间的交来求集合之间的并，以下仅为容斥原理的部分相关习题

https://codeforces.com/problemset/problem/803/F

题意了然，即求出所有符合公共最小公约数为１的序列数目，那么考虑一种特殊情况：只有数字ｉ，很明显他们的最小公约数一定是ｉ，且对于每个位置都有选或者不选两种情况，再去掉都不选的一种，所有情况为 \(2^n - 1\)，那么对于ｉ的倍数，这里举例为：２，４，６，８　那么这样一个序列所出现的公约数分别有：２，４，６，８，共有 \(2^4 - 1\) 种情况，那么设 \(dp[i]\) 是以ｉ为公约数的序列的个数，那么有：\(dp[i] = 2^n - 1 - \sum{dp[j]}\)，\(j\mod i = 0\)
倒着推即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int cnt[N];
int qpow(int a,int k){
    int res=1;
    while(k){
        if(k&1) res=res*a%mod;
        k>>=1,a=a*a%mod;
    }
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,mx=0; cin>>n;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        cnt[x]++;
        mx=max(mx,x);
    }
    vector<int>dp(mx+1);
    for(int i=mx;i>=1;i--){
        int k=0,ans=0;
        for(int j=i;j<=mx;j+=i){
            k=(k+cnt[j])%mod,ans=(ans+dp[j])%mod;
        }
        dp[i]=(qpow(2,k)-1-ans+mod)%mod;
    }
    cout<<dp[1];
    return 0;
}

https://www.luogu.com.cn/problem/P1450
首先考虑没有数量限制的情况下，我们可以直接使用完全背包求方案数，接下来考虑某个面值使用数目不合法的情况，对于求和100 元来说，设１元面值有５个，\(dp[i]\) 表示总和ｉ的方案数，那么 \(dp[94]\) 就表示为１不合法的方案数，因为如果只靠１元面值，无法到达求和 100 元，同理设２元面值有２个，那么１元和２元同时不合法的方案数为：\(dp[100-1*5-2*3]\)，故我们需要在 \(dp[100]\) 这个方案数下减去所有不合法方案数，也就是四个面值的并集，容斥即可求出

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vector<int>c(5);
    int n;
    for(int i=1;i<=4;i++) cin>>c[i];
    cin>>n;
    vector<int>dp(N);
    dp[0]=1;
    for(int i=1;i<=4;i++){
        for(int j=c[i];j<N;j++){
            dp[j]+=dp[j-c[i]];
        }
    }
    vector<int>d(5);
    while(n--){
        for(int i=1;i<=4;i++) cin>>d[i];
        int s; cin>>s;
        int res=dp[s];
        for(int i=1;i<(1<<4);i++){
            int cnt=s,vis=-1;
            for(int j=1;j<=4;j++){
                if(i&(1<<(j-1))){
                    cnt-=(d[j]+1)*c[j];
                    vis=-vis;
                }
            }
            if(cnt>=0) res-=vis*dp[cnt];
        }
        cout<<res<<'\n';
    }
    return 0;
}