组合计数 - 容斥原理

一、容斥原理引入

Ex.1 P3197 越狱

1. 题面梗概

共有 $n$ 个盒子，$m$ 个物品，求相邻两个盒子物品相同的情况。

$m \leq 10^8, n \leq 10^{12}$

2. 逻辑推导

由于本题的 $n, m$ 数量级都很大，猜测答案是一个和 $n, m$ 相关的表达式，但是如果直接统计满足条件的情况很困难，此时不妨从补集的角度来入手。

设 $| U |$ 是所有的情况，$| A |$ 是相邻两个盒子物品相同的情况，$| \complement_u A|$ 就是相邻两个盒子物品不同的情况，由于 $| U | = | A | + | \complement_u A|$，所以只需要求出 $| U |$ 和 $| \complement_{u}A |$ 即可。

由乘法原理可得 $|U| = m^n$（ $n$ 个盒子，每个盒子有 $m$ 种选择 ）。

接着求解 $|\complement_{u}A|$，可以按位置来考虑，显然，第一个盒子的物品有 $m$ 种选择，第二个盒子的物品有 $m - 1$ 种选择，由乘法原理可得 $|\complement_{u}A| = m \times (m - 1)^{n-1}$。

这里可能会遇到一个问题，第二次求解中，只保证了每个盒子跟上一个盒子的物品不同，没有考虑跟后一个的关系。其实，在求第 $i+1$ 个盒子的时候，已经保证了它和第 $i$ 个盒子的物品不同，因此对于第 $i$ 个盒子来说，它的物品一定和第 $i+1$ 个盒子不同。

这启示我们，采用合理的枚举顺序，往往会给给解题带来很大的便利。

最后的答案就是：$|A| = |U| - |\complement_{u}A| = m^n - m \times (m-1)^{n-1}$。快速幂求解即可，代码略。

Ex.2 P1287 盒子与球

1. 题面梗概

有多少种方案将 $n$ 个互不相同的球放入 $r$ 个互不相同的盒子，使得没有一个盒子为空。

$0 \leq r \leq n \leq 10$

2. 逻辑推导

容易想到，如果去掉没有空的条件，由乘法原理，最终的答案为 $r^n$，接着考虑出现空格的情况。

指定 $a_{1}, a_{2}, \cdots a_{k}$ 盒子为空，则 $n$ 个球分别有 $r - k$ 个盒子可以放入。由乘法原理，在这种情况下有 $(r - k)^n$ 种方案，又由于对于任意一个 $k$，有 $C_{r}^{k}$ 个满足条件的 $a_{1}, a_{2}, \cdots, a_{k}$，于是有 $k$ 个盒子为空的情况总数为 $C_{r}^{k} (r-k)^n$。

由容斥原理，可以得到答案为：

$$\sum_{k=0}^{r-1} (-1)^k C_{r}^{k} (r-k)^n$$

代码略。

二、容斥原理应用

Ex. 1 P1450 硬币购物

1. 题面梗概

有 $4$ 类硬币，面值为 $c_{1},c_{2},c_{3},c_{4}$。现在求 $n$ 次：第 $i$ 类硬币共有 $d_{i}$ 枚，有多少种方案购买价值为 $s$ 的东西刚好花完。

$1 \leq c_{i}, d_{i}, s \leq 10^5, n \leq 1000$

2. 逻辑推导

第 $i$ 类硬币有 $d_{i}$ 枚，可以看作限制：第 $i$ 类硬币不能用多于 $d_{i}$ 枚。

如果不考虑限制条件，如何回答询问？使用背包 DP 预处理所有为 $s$ 的答案，设 $dp[i][j]$ 表示前 $i$ 类硬币支付 $j$ 元的方案数。转移方程为 $dp[s][z] = dp[s-c[z]][z] + dp[s][z-1]$，初始条件是 $dp[0][0] = 1$，答案为 $dp[s][4]$，可以用滚动数组优化。

然后考虑如果第 $a_{1},a_{2}, \dots, a_{t} \quad (t \leq 4)$ 类物品超过了限制，其它硬币不考虑，如何回答询问。事实上只需要强制用了至少 $d_{i} + 1$ 个硬币。于是可以对这些硬币预先从 $s$ 里扣走 $\sum_{i=1}^{t} (d[a_{i}] + 1 ) \times c[a_{i}]$ 个硬币，而将这些直接安排给超过限制的硬币即可。

对于剩下的 $s - \sum_{i=1}^{t} (d[a_{i}] + 1 ) \times c[a_{i}]$ 个硬币如何分配，又是一个新的完全背包问题，其处理方法与之前的动态规划一致。

接着，由容斥原理，可以得到最终的答案为 “至少偶数种硬币超限” 的情况减去 “至少奇数种硬币超限” 的情况。在这里，可以预处理动态规划，然后直接统计得出答案。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 50;

ll dp[maxn];
ll d[5], c[5], s;
int n, Q;

ll get( int x ) { return x < 0 ? 0 : dp[x]; }

int main( )
{
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> Q;

    dp[0] = 1;
    for( int i = 1; i <= 4; ++ i )
    {
        for( int j = c[i]; j <= maxn; ++ j )
        {
            dp[j] += dp[j - c[i]];
        }
    }

    while( Q -- )
    {
        for( int i = 1; i <= 4; ++ i )
        {
            cin >> d[i];
            d[i] = ( d[i] + 1 ) * c[i];
        }
        cin >> s;
        ll ans = dp[s];
        ans -= get( s - d[1] ) + get( s - d[2] ) + get( s - d[3] ) + get( s - d[4] );
        ans += get( s - d[1] - d[2] ) + get( s - d[1] - d[3] ) + get( s - d[1] - d[4] )
            + get( s - d[2] - d[3] ) + get( s - d[2] - d[4] ) + get( s - d[3] - d[4] );
        ans -= get( s - d[1] - d[2] - d[3] ) + get( s - d[1] - d[2] - d[4] )
            + get( s - d[1] - d[3] - d[4] ) + get( s - d[2] - d[3] - d[4] );
        ans += get( s - d[1] - d[2] - d[3] - d[4] );
        cout << ans << '\n';
    }

    return 0;
}

Ex.2 P5664 Emiya 家今天的饭

1. 题面梗概

有 $m$ 种食材以及 $n$ 种烹饪方法。每道菜都刚好使用恰好一种食材和恰好烹饪方式。使用第 $i$ 种烹饪方法和第 $j$ 种食材可以做出 $a_{i,j}$ 种不同的菜肴，问可可以摆出多少桌不同的菜肴，满足下列限制条件：

1. 至少一道菜。
2. 每道菜的烹饪方法各不相同。
3. 设共有 $k$ 道菜，则每一种食材在该集合内被使用至多 $\left\lfloor \frac{k}{2} \right\rfloor$ 次。

$n \leq 100, m \leq 2000$。

2. 逻辑推导

如果只有前 $2$ 个限制，怎么做？在每一种烹饪方法中，选择出至多一个菜，也可以不选。因为这些选择是独立的，所以可以用乘法原理计数。

第 $i$ 种烹饪方法可以得到 $\sum_{j=1}^{m} a_{i,j}$ 个菜肴，因为可以不选，对乘积的贡献为 $1 + \sum_{j=1}^{m} a_{i,j}$。对所有 $i$ 相乘可以得到 $\prod_{i=1}^{n}(1 + \sum_{j=1}^{m} a_{i,j} )$。

但如果全部都不选，就违背了限制 $1$，所以答案在此基础上 $-1$，即：

$$\prod_{i=1}^{n}(1 + \sum_{j=1}^{m} a_{i,j} ) - 1$$

将总方案数设为全集，那么违反限制条件 3 的方案与满足限制条件 3 的方案互为补集，要求解后者，只需求出前者即可。

接下来，考虑计算违反限制 3 的方案，发现最多有一种食材出现次数大于 $\left\lfloor \frac{k}{2} \right\rfloor$，否则菜肴的总数至少为 $\left( \left\lfloor \frac{k}{2} \right\rfloor + 1 \right) \times 2 > k$ 矛盾。于是，可以枚举哪种食材被使用了超过 $\left\lfloor \frac{k}{2} \right\rfloor$ 次。

考虑动态规划，令该食材为 $x$，$dp[i][k][c]$ 表示前 $i$ 种烹饪方法，总共选出来 $k$ 个菜，其中 $c$ 个菜用食材 $x$，尝试转移，由于每种烹饪方法最多使用一种食材，所以要么选择一种食材，要么什么都不选。

1. 如果选一种食材，转移为：如果 $j = x$，则共 $a_{i,j} \times dp[i-1][k-1][c-1]$ 中；如果 $j \neq x$，则共 $a_{i,j} \times dp[i-1][k-1][c]$ 种。
2. 如果什么都不选，共 $dp[i-1][k][c]$ 种。

最后，对所有 $c,k$ 的 $dp[n][k][c]$ 求和，其中 $c > \left\lfloor \frac{k}{2} \right\rfloor$ 且 $k > 0$。这样，时间复杂度是 $O(m \times n^3 m)$，不能接受。

考虑优化，$c > \left\lfloor \frac{k}{2} \right\rfloor$ 实际上意味着什么，分类讨论后可知，该条件等价于 $c > \frac{k}{2}$。

接着整理表达式得到：$2c - k > 0$，或者 $c - (k - c) > 0$。其实际意义是 $j = x$ 的物品数量，减去 $j \neq x$ 的物品数量，大于 $0$。所以我们只需要关心这两个值的差，而不关心菜肴的数量，那么动态规划可以作以下优化：

$dp[i][\Delta c]$ 为只考虑前 $i$ 个操作，食材 $x$ 被使用的次数减去食材 $x$ 没被使用的次数为 $\Delta c$ 的方案数。

PS：这里 $\Delta c$ 可能是负数。

当烹饪方法为 $i$，食材为 $j$，转移为：

1. 如果 $j = x$，则 $dp[i][\Delta c+1] \leftarrow dp[i-1][\Delta c]$，
2. 如果 $j \neq x$，则 $dp[i][\Delta c-1] \leftarrow dp[i-1][\Delta c]$。
3. 不选，则 $dp[i][\Delta c] \leftarrow dp[i-1][\Delta c]$，最后对所有正整数 $\Delta$ 取 $dp[n][\Delta c]$ 之和。

注意到优化到这里就可以把很多转移累计在一起。不必枚举所有 $j$，而可以直接分 $j=x$，$j \neq x$ 和不选三种情况。

1. 对于 $j = x$，则 $dp[i][\Delta] \leftarrow dp[i-1][\Delta]$。
2. 对于 $j \neq x$，则 $dp[i][\Delta] \leftarrow \left( -a_{i,x} + \sum_{j=1}^{m} a_{i,j} \right) dp[i-1][\Delta]$。
3. 不选的情况，则 $dp[i][\Delta] \leftarrow dp[i-1][\Delta]$。

最终复杂度为 $O(n^2m)$，可以接受。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 998244353;
const int maxn = 105;
const int maxm = 2005;

int a[maxn][maxm];
ll sum[maxn];
ll dp[maxn][maxn<<1];
int n, m;

int main( )
{	
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j <= m; ++ j )
        {
            cin >> a[i][j];
            sum[i] = ( sum[i] + a[i][j] ) % mod;
        }
    }

    ll total = 1;
    for( int i = 1; i <= n; ++ i )
    {
        total = ( total * ( sum[i] + 1 ) ) % mod;
    }
    total = ( total - 1 + mod ) % mod;


    ll res = 0;
    for( int c = 1; c <= m; ++ c )
    {
        memset( dp, 0, sizeof( dp ) );
        dp[0][n] = 1;
        
        for( int i = 1; i <= n; ++ i )
        {
            for( int j = n - i; j <= n + i; ++ j )
            {
                dp[i][j] = dp[i-1][j];

                if( j - 1 >= 0 )
                    dp[i][j] = ( dp[i][j] + dp[i-1][j-1] * a[i][c] ) % mod;
                if( j + 1 <= 2 * n )
                    dp[i][j] = ( dp[i][j] + dp[i-1][j+1] * ( sum[i] - a[i][c] + mod ) % mod ) % mod;
            }
        }
    
        for( int j = n + 1; j <= 2 * n; ++ j )
        {
            res = ( res + dp[n][j] ) % mod;
        }
    }

    ll ans = ( total - res + mod ) % mod;

    cout << ans << '\n';

    return 0;
}

Ex.3 P5505 分特产

1. 题意梗概

有 $n$ 个有标号的盒子和 $m$ 个有标号的球，每种球有 $a[i]$ 个，求每个盒子至少放一种球的总方案数。

$n, m, a \leq 1000$

2. 逻辑推导

本题的难点在于每种球可以独立分发，且盒子可为空。

首先我们先分析这样一个问题：把 $a_{j}$ 个相同的球放入 $r$ 个不同的盒子中，盒子可以为空，那么通过隔板法，可以得出这样的方案数为：

$$\binom{a_j + r - 1}{r - 1}$$

直接计算 “每个盒子都不为空” 较难，我们转向计算 “至少 $i$ 个盒子为空” 的情况，设 $f[i]$ 为至少 $i$ 个盒子为空，则其余 $n-i$ 个盒子随意分的方案数。

接着计算 $f[i]$，从 $n$ 个盒子中选出 $i$ 个作为空盒子，共有 $\binom{n}{i}$ 种选法。然后剩下 $n-i$ 个盒子去分 $a[j]$ 个球，也就是 $\binom{a_j+(n-i)-1}{(n-i)-1}$ 种情况，由于每种球是独立的，所以用乘法原理即可求解，综上：

$$f[i] = \binom{n}{i} \prod_{j=1}^{m} \binom{a_j+(n-i)-1}{(n-i)-1}$$

最后根据容斥原理，所有盒子都不为空（ 即恰好 $0$ 个盒子为空 ）的方案数为：

$$\begin{align} Ans &= \sum_{i=0}^{n-1} (-1)^i f(i) \\ &= \sum_{i=0}^{n-1} (-1)^i \binom{n}{i} \prod_{j=1}^{m} \binom{a_j+(n-i)-1}{(n-i)-1} \end{align}$$

代码略。

Ex.4 P2567 幸运数字

1. 题面梗概

计算 $[l,r]$ 之间有多少个数满足含 6 或含 8，或者是含 6 或含 8 的数的倍数。

$l, r \leq 10^{10}$

2. 逻辑推导

由于 $r$ 最大为 $10^{10}$，而幸运数字每多一位，数量才翻一倍。所以在 $10^{10}$ 以内的幸运数字总数约为 $2^{11} - 2 = 2046$ 个，数量很少，因此可以直接用 DFS 递归构造出所有符合条件的幸运数字。

接着我们要统计多个集合（ 每个幸运数字的倍数集 ）的并集大小。根据容斥原理，可以得到：

$$Ans = \sum(cnt(a_{i})) - \sum(lcm(a_{i}, a_{j})) + \sum(lcm(a_{i}, a_{j}, a_{k})) \dots$$

其中，在区间 $[l, r]$ 内 $x$ 的倍数个数为：

$$cnt(x) = \lfloor \frac{r}{x} \rfloor - \lfloor \frac{l-1}{x} \rfloor$$

直接这样统计会 TLE，我们考虑对搜索剪枝。

1. 控制 LCM，若当前 LCM 已经大于 $r$，那么贡献为 0，跳出搜素。

2. 关系剪枝：如果 $a = kb$，那么凡是 $a$ 的倍数也一定是 $b$ 的倍数，因此，$a$ 是多余的，可以直接删除。

举个例子，算了 6，就不用算 66 了。

3. 加速剪枝：由剪枝 1 可知，如果 LCM 更快达到 r，就更快结束搜索。所以我们把幸运数字从大到小排序，从而大幅减少递归深度。

然后就可以 AC 了。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e4 + 5;

ll temp[maxn];
ll lucky[maxn];
int cnt = 0, cnt1 = 0;
bool mark[maxn];

void dfs( ll x, ll limit )
{
    if( x > limit ) return ;
    if( x != 0 ) temp[++ cnt] = x;
    dfs( x * 10 + 6, limit );
    dfs( x * 10 + 8, limit );
}

ll lcm( ll a, ll b, ll limit ) { 
    __int128 g = __gcd( a, b );
    __int128 res = (__int128)a / g * b;
    if( res > limit ) return limit + 1;  
    return (ll)res; 
}

ll solve( int idx, ll cur_lcm, ll a, ll b )
{
    ll res = 0;
    for( int i = idx; i <= cnt1; ++ i )
    {
        ll next_lcm = lcm( cur_lcm, lucky[i], b );
        if( next_lcm > b ) continue;
        ll cnt = ( b / next_lcm ) - ( ( a - 1 ) / next_lcm );
        res += cnt - solve( i + 1, next_lcm, a, b );
    }
    return res;
}

int main( )
{
    ios::sync_with_stdio( 0 ); cin.tie( 0 );

    ll a, b;
    cin >> a >> b;

    dfs( 0, b );
    sort( temp + 1, temp + cnt + 1 );

    for( int i = 1; i <= cnt; ++ i )
    {
        if( mark[i] == 0 ) lucky[++ cnt1] = temp[i];
        for( int j = i + 1; j <= cnt; ++ j )
        {
            if( temp[j] % temp[i] == 0 ) mark[j] = 1;
        }
    }

    sort( lucky + 1, lucky + cnt1 + 1, greater<ll>() );
    cout << solve( 1, 1, a, b ) << '\n';

    return 0;
}