容斥原理

hcywoi · 2022-12-27 15:37:31 · 个人记录

\mathcal Preface

可能容斥原理的公式等还是 AK\ IOI 的巨佬讲得详细，大家可以看看这篇博客。

~~这篇博客把我写得手残疾了。~~

我这里直接上公式：

|\bigcup\limits_{i=1}^{N}S_i|=\sum\limits_{i=1}^{N}|S_i| - \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}|S_i \bigcap S_j|+\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}|S_i\bigcap S_j\bigcap S_k|\cdots

【例题 \mathit 1】

Devu and Flowers。

先在这里明确一下（与题目翻译有所不同）：n 表示花瓶的个数，m 表示需要的花的数量，f_i 表示第 i 个花瓶花的朵数。

【题目大意】

让我们求出序列 q 的个数。

其中序列 q 要满足以下条件：

【分析】

如果我们去除条件 2，则让我们求 \left(\sum\limits_{i=1}^{n}q_i\right) = m 的非负整数解的个数。

首先我们把 y_i = q_i + 1，则我们要求出 \left(\sum\limits_{i=1}^{n}y_i\right) = n + m 的正整数解的个数。

即求不定方程正整数解的个数，这个可以用隔板法做。

形象化的说：

那么我们要从 $n+m-1$ 个空隙中（至于为什么是 $n+m-1$ 个空隙，我依旧不知道怎么讲）选出 $n-1$ 个空隙放隔板，那么这个就是小学奥数题，即为 $\dbinom{n+m-1}{n-1}$（这玩意就等于 $C_{n+m-1}^{n-1}$）。然后加上条件 $2$，对于一个不合法的解**至少**有一个 $1\le i\le n$ 满足 $q_i > f_i$。我们把 $q_i > f_i$ 的 $q_i$ 表示成一个集合 $S_i$。则不合法的解为一开始的公式（~~我只不过复制了一下~~）： $$ |\bigcup\limits_{i=1}^{N}S_i|=\sum\limits_{i=1}^{N}|S_i| - \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}|S_i \bigcap S_j|+\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}|S_i\bigcap S_j\bigcap S_k|\cdots $$ 则答案就为： $$ \dbinom{n+m-1}{n-1}-|\bigcup\limits_{i=1}^{N}S_i|=\dbinom{n+m-1}{n-1}-\sum\limits_{i=1}^{N}|S_i| + \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}|S_i \bigcap S_j|-\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}|S_i\bigcap S_j\bigcap S_k|\cdots $$ 然后问题又来了，如果求上面的答案呢。我们发现如果 $S_i$ 不合法必定是 $q_i > f_i$ 这个就为 $q_i \ge f_i+1$，那么我们把 $q_i$ 减去 $f_i+1$。那么不管你剩余的 $m - (f_i + 1)$ 个花怎么选都是 $\in S_i$ 的。这里是没有 $f_i$ 进行限制，那么这用回到了之前求不定方程解的个数。答案就为 $\dbinom{n+m-f_i-2}{n-1}$（这玩意就为 $C_{n+m-f_i-2}^{n-1}$），如果看到这里模糊的话请**仔细**阅读起那面求不定方程的过程。那么如果是 $|S_i \bigcap S_j|$ 也是同理。要同时满足 $q_i > f_i$ 和 $q_j > f_j$，那么和上面一样减去 $q_i + 1$ 和 $q_j + 1$。然后再从剩余的 $m - (q_i + 1) - (q_j + 1)$ 朵花中去选。答案为 $\dbinom{n+m-f_i-f_j-3}{n-1}$（这玩意就为 $C_{n+m-f_i-f_j-3}^{n-1}$）。然后我们把答案再写一下： $$ \dbinom{n+m-1}{n-1}-|\bigcup\limits_{i=1}^{N}S_i|=\dbinom{n+m-1}{n-1}-\sum\limits_{i=1}^{N}\dbinom{n+m-f_i-2}{n-1}+\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\dbinom{n+m-f_i-f_j-3}{n-1}-\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}\dbinom{n+m-f_i-f_j-f_k-4}{n-1}\cdots $$ 这个组合数的求法就按照 $C_{b}^{a}=\frac{b\times(b-1)\times\cdots\times (b-a+1)}{a!}$，因为 $a \le 20$，与 $n$ 同级，所以时间复杂度为 $\mathcal O(n)$。当然这个要用逆元即 $\frac{a}{b} \equiv a\cdot b^{-1} \pmod p$，$b^{-1}$ 为 $b$ 的逆元即为 $b^{p-2}$，$p$ 为模数（证明可以去百度搜费马小定理）。然后那个柿子可以用二进制枚举来求，如果二进制中第 $i$ 位是 $1$ 表示要属于集合 $S_i$。时间复杂度：$\mathcal O(2^n\times n)$，空间复杂度：$\mathcal O(n)$。 ### $\mathcal Code

#include <bits/stdc++.h>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 20, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

void solve();

int main()
{
    IOS;
    cit, cot;
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}

LL n, m;
LL q[N];

int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % MOD;
        a = (LL)a * a % MOD;
        k >>= 1;
    }

    return res;
}

int C(LL a, LL b)
{
    if (a < b) return 0;
    int x = 1, y = 1;
    for (LL i = a - b + 1; i <= a; i ++ ) x = i % MOD * x % MOD;
    for (int i = 1; i <= b; i ++ ) y = y * (LL)i % MOD;
    return x * (LL)qmi(y, MOD - 2) % MOD;
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> q[i];

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
    {
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
            {
                sign *= -1;
                a -= q[j] + 1;
            }
        res = ((res + C(a, b) * sign) % MOD + MOD) % MOD;
    }
    cout << res << endl;
}

【例题 \mathit 2】

硬币购物。

这题我就不写得像前一题那么详细。

先来考虑如果没有 d_i 限制，d_i 的含义见题意。

那么就是一道完全背包的模板题。

如果加上 d_i 限制，我们将 q_i > d_i 的 q_i 加入集合 S_i（q_i 为第 i 张纸牌拿的张数）。

那么答案为： $$ f_m-|\bigcup\limits_{i=1}^{N}S_i|=f_m-\sum\limits_{i=1}^{N}|S_i| + \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}|S_i \bigcap S_j|-\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}|S_i\bigcap S_j\bigcap S_k|\cdots $$ $|S_i|$ 我们也用上题的思路去求，将 $d_i + 1$ 张钱拿去，那么 $m$ 应该减去 $(d_i + 1)\times c_i$，$m$ 为价值，$c_i$ 为钱的面值。然后问题转换成了求没有 $d_i$ 限制，且价值为 $m - (d_i + 1)\times c_i$ 的方案数，这也是完全背包的裸题。 $|S_i\bigcap S_j|\cdots$ 等不展开了，具体见柿子。我们再写一遍答案： $$ f_m-|\bigcup\limits_{i=1}^{N}S_i|=f_m-\sum\limits_{i=1}^{N}f_{m - (d_i + 1)\times c_i} + \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}f_{m - (d_i + 1)\times c_i - (d_j + 1)\times c_j}-\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}f_{m - (d_i + 1)\times c_i - (d_j + 1)\times c_j - (d_k+1)\times c_k}\cdots $$ ### $\mathcal Code

#include <bits/stdc++.h>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

void solve();

int main()
{
    IOS;
    cit, cot;
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}

int c[4], n;
LL f[N];

void solve()
{
    cin >> c[0] >> c[1] >> c[2] >> c[3] >> n;
    f[0] = 1;
    for (int i = 0; i < 4; i ++ )
        for (int j = c[i]; j < N; j ++ )
            f[j] += f[j - c[i]];
    while (n -- )
    {
        int d[4], _s;
        cin >> d[0] >> d[1] >> d[2] >> d[3] >> _s;

        LL res = 0;
        for (int i = 0; i < 1 << 4; i ++ )
        {
            int sign = 1;
            LL s = _s;
            for (int j = 0; j < 4; j ++ )
                if (i >> j & 1)
                {
                    sign *= -1;
                    s -= c[j] * (d[j] + 1ll);
                }
            if (s >= 0) res += sign * f[s];
        }
        cout << res << endl;
    }
}

【例题 \mathit{3}】

Count GCD。

\mathcal Solution

先进行转化，\gcd(b_1, b_2, \cdots, b_i)=\gcd(\gcd(b_1, b_2, \cdots, b_{i-1}), b_i)=\gcd(a_{i-1}, b_i)=a_i

也就是让 \gcd(\frac{a_{i-1}}{a_i}, \frac{b_i}{a_i})=1。

再进行转化，就是让 \gcd(\frac{a_{i-1}}{a_i}, b_i)=1 并且 b_i\le \left\lfloor\frac{m}{a_i}\right\rfloor。

我们先不考虑条件 1，那么答案为 \left\lfloor\frac{m}{a_i}\right\rfloor。

然后我们再加上条件 1，那么我们将 n=\frac{a_{i-1}}{a_i}，则我们将 n 分解质因式后为 n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_q^{\alpha_q}。

然后根据容斥原理，即减去所有的 \gcd(\frac{a_{i-1}}{a_i}, b_i)>1。

然后我们再书写一遍答案：

\left\lfloor\frac{m}{a_i}\right\rfloor-\sum\limits_{i=1}^{q}S_{p_i}+\sum\limits_{i=1}^{q}\sum\limits_{j=i+1}^{q}S_{p_ip_j}-\sum\limits_{i=1}^{q}\sum\limits_{j=i+1}^{q}\sum\limits_{k=j+1}^{q}S_{p_ip_jp_k}+\cdots

其中 S_i 表示 \left\lfloor\frac{\left\lfloor\frac{m}{a_i}\right\rfloor}{i}\right\rfloor，即 [1, \left\lfloor\frac{m}{a_i}\right\rfloor] 中所有 i 的倍数的个数。

因为 2\times3\times5\times7\times11\times13\times17\times19\times23\ge 10^9，所以 q\le 9。

当然这里要加点小优化，即如果 a_{i} \nmid a_{i-1} 时，那么直接输出 0，不用做下面计算，否则你会喜提 TLE。

因为满足 a_{i}\mid a_{i-1} 的序列，一定满足 a 是单调递增的，那么 \displaystyle\sum_{i=1}^{n-1}\sqrt{\dfrac{a_{i+1}}{a_i}} 不会被卡满，大约是 \mathcal O(\sqrt{m}\log m)。

\mathcal Code

#include <bits/stdc++.h>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 200010, M = 100010, MOD =  998244353;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int n, m;
int a[N];

void solve();

int main()
{
    IOS;
    cit, cot;
    int T = 1;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

void solve()
{
    cin >> n >> m;
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if (i > 1 && a[i - 1] % a[i])
        {
            flag = false;
        }
    }
    if (!flag)
    {
        cout << 0 << endl;
        return;
    }

    int res = 1;
    for (int i = 2; i <= n; i ++ )
    {
        int k = m / a[i], t = a[i - 1] / a[i];

        vector<int> p;
        for (int j = 2; j <= t / j; j ++ )
            if (t % j == 0)
            {
                p.push_back(j);
                while (t % j == 0) t /= j;
            }
        if (t > 1) p.push_back(t);

        int sum = 0, sz = p.size();
        for (int i = 0; i < 1 << sz; i ++ )
        {
            int sign = 1, s = 1;
            for (int j = 0; j < sz; j ++ )
                if (i >> j & 1)
                {
                    sign *= -1;
                    s *= p[j];
                }
            sum += sign * (k / s);
        }

        res = res * (LL)sum % MOD;
    }
    cout << res << endl;
}