【算法专题】容斥原理
题
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 ();
}