【算法专题】容斥原理

题

E. Devu and Flowers

https://codeforces.com/contest/451/problem/E
前置知识：隔板法
然后正难则反，把至多取 \(a_i\) 个转化为 至少取 \(a_i+1\) 的反问题，就能套用隔板法的公式了。
答案即为：

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 25, mod = 1e9 + 7;
ll c[N], n, m, sum, fm = 1;

ll qmi(ll a, ll k, ll p){
    ll res = 1;
    while(k){
        if(k & 1)    res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

ll C (ll a, ll b) { //a! / (b!(a-b)!)
    if (a < b)  return 0;
    ll fz = 1;
    for (ll i = a; i > a - b; i--)     (fz *= i % mod) %= mod;
    return (fz % mod * fm) % mod;
}

int main () {
    cin >> n >> m;
    for (int i = 0; i < n; i++)    cin >> c[i];
    for (int i = 1; i < n; i++)     fm = (i * fm) % mod;
    fm = qmi (fm, mod - 2, mod);
    for (int i = 0; i < 1ll << n; i++) { //二进制枚举
        ll a = m + n - 1, b = n - 1, sign = 1;
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) {
                sign *= -1;
                a -= c[j] + 1;
            }
        }
        sum = (sum + C (a, b) * sign + mod) % mod;        
    }
    cout << (sum + mod) % mod;
}

215. 破译密码

https://www.acwing.com/problem/content/217/
前置知识：莫比乌斯函数和数论分块

题解：https://www.acwing.com/solution/content/17858/

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 50005;
ll a, b, d, mobius[N], prime[N], sum[N];
bool vis[N];

void init (int x) { //线性筛法求mobius函数
    mobius[1] = 1;
    int cnt = 0;
    for (int i = 2; i <= x; i++) {
        if (!vis[i])    prime[++cnt] = i, mobius[i] = -1;
        for (int j = 1; i * prime[j] <= x; j++) {
            int t = i * prime[j];
            vis[t] = true;
            if (i % prime[j] == 0) {
                mobius[t] = 0;
                break;
            }
            mobius[t] = mobius[i] * -1;
        }
    }
    for (int i = 1; i <= x; i++)    sum[i] = sum[i-1] + mobius[i];
}

void solve () {
    scanf ("%lld%lld%lld", &a, &b, &d);
    a /= d, b /= d; //即求 x<=a, y<=b, (a,b)=1的个数
    ll l = 1, r, n = min (a, b), ans = 0;
    while (l <= n) {
        r = min (n, min (a / (a / l), b / (b / l)));
        ans += (a / l) * (b / l) * (sum[r] - sum[l-1]);
        l = r + 1;
    }
    printf ("%lld\n", ans);
}

int main () {
    init (N - 1);
    int t;
    scanf ("%d", &t);
    while (t--) solve ();
}

F - Tree and Constraints

https://atcoder.jp/contests/abc152/tasks/abc152_f