发布时间：2025-05-22

容斥原理

$$\left|\bigcup_{i=1}^{n} S_{i}\right| = \sum_{m=1}^{n} (-1)^{m-1} \sum_{1 \leq a_1 < a_2 < \cdots < a_m \leq n} \left| \bigcap_{i=1}^{m} S_{a_i} \right|$$

如果求交集，那么就是$\left|\bigcap_{i=1}^{n} S_{i}\right| = |U| - \left|\bigcup_{i=1}^{n} \overline{S_{i}}\right|$

不定方程的非负整数解

求不定方程 $\sum_{i=1}^{n}x_{i}=m$ ($m\in\mathbb{N}$) 的非负整数解个数 满足约束条件 $x_{i}\leq b_{i}$ ($b_{i}\in\mathbb{N},\ i=1,2,\dots,n$)

题目要求$|\bigcap S_i|=|U|-|\bigcup \overline{S_i}|$,$U$为没有限制的情况，直接隔板法，答案为$\binom{m+n-1}{n-1}$

转化为一些有限制，一些没限制，因此$\sum_{i=1}^nx_i=m-\sum_{i=1}^k(b_{a_i}+1),$$\bigcap_{a_i \lt a_{i+1}}^{1 \leq i \leq k}S_{a_i}=\binom{\sum x_i+n-1}{n-1}$

例题1

四种硬币面值为$c_i$，每种硬币有$d_i$个，$n$次询问，求组成$S$的面值方案数？

背包复杂度为$O(4nS)$

容斥做，那么$\sum c_id_i=m$，$\sum c_id_i=S-\sum_{i=1}^kc_i(d_i+1)$，复杂度为$O(4S+2^4n)$

void solve(){
    array<int,4> c,d;
    int n,s;
    cin>>c[0]>>c[1]>>c[2]>>c[3]>>n;
    vector<int> dp(1e5+10);
    dp[0]=1;
    for(int i=0;i<4;i++){
        for(int j=c[i];j<=1e5;j++)dp[j]+=dp[j-c[i]];
    }
    while(n--){
        for(int i=0;i<4;i++)cin>>d[i];
        cin>>s;
        int ans=dp[s],res=0;
        for(int i=1;i<1<<4;i++){// 如果从0开始，那么可以发现是偶正奇反
            int ss=s,cnt=0;
            for(int j=0;j<4;j++){
                if(i>>j&1){
                    cnt++;
                    ss-=c[j]*(d[j]+1);
                }
            }
            if(ss<0)continue;
            res+=((cnt&1)?1:-1)*dp[ss];
        }
        cout<<ans-res<<"\n";
    }
}

注意到可以从0开始枚举状态，因此可以转变为：所有满足限制的方案=$(-1)^{i \&1}$有$i$个违反限制的方案

CCPC2021威海M

长度为$n$的01序列，求恰好有$m$个$1$，连续段最长恰好为$k$的方案数

经典trick:$f(k)$表示小于等于$k$的方案，答案就是$f(k)-f(k-1)$

考虑求$f(k)$,把$0$看成隔板，就是求$\sum_{i=1}^{n-m+1} x_i=m,0 \leq x_i \leq k$

因为所有限制条件相同，因此，直接枚举有$j$个违反了限制