选数 容斥原理

发表于 更新于 分类于

题目

桌面上有\(N\)个数字排成一排，小武要求小林从中选出\(3\)个数字，使得这\(3\)个数字的按位或的结果恰好等于\(x\)，小林很快 就解决了这个问题，小武想了想，决定把问题加强一下，小武会问小林\(Q\)次问题，每次选的\(3\)个数字只能在从左往右 的第\(l\)个数和第\(r\)个数之间选择，并且要小林说出符合要求的方案数，小林顿时不会了，于是把问题交给了你。 第一行两个数\(N\)和\(Q\), 第二行\(N\)个数，按照从左到右的顺序给出桌面上的数字 接下来\(Q\)行，每行\(3\)个数字，分别为\(l,r,x\ Q\)行，每行一个数表示方案数。

分析

首先，如果\(x\)某位等于\(0\)。那么选出的数该为只能等于\(0\)。

排除这种情况，选出的数一定是\(x\)的子集，即\(i\and x=i\)

而没有顺序的选出三个数方案是\(\binom{n}{3}\)

选出的三个数一定属于某个集合，我们直接枚举这个集合\(S\)，\(S\)一定是\(x\)的子集，不然没有意义。如果\(S\)和\(x\)一的个数不同，一定是\(S\)为\(0\)，\(x\)是\(1\)。所以要把\(S\)的所有选择方案减去。但是某个三元组可能被反复减，如果\(1\)的个数差偶数个时又要加上去。

为什么这样是对的？

假如当前有一个三元组或起来等于\(10001101\)，而\(x=10111111\)

我们考虑这个三元组的贡献，也就是在哪些集合会枚举到它。

显然可以自由放\(1\)的位置有\(3\)个。

则贡献是\(\binom{3}{0}-\binom{3}{1}+\binom{3}{2}-\binom{3}{3}\)

一般的说\(\sum\limits_{i=0}^{n}(-1)^{i+1}\binom{n}{i}=-1\times \sum\limits_{i=0}^{n}(-1)^{i}\binom{n}{i}=0\)

如果有偶数个自由放的位置也是同理，所以说如果三个数或起来不等于\(x\)，则贡献是\(0\)。

如果恰好等于\(x\)的，只会在\(S=x\)时被算一次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 256;
int pop[N + 2], sum[100005][N + 2], n, Q;

int main() {
	freopen("select.in", "r", stdin);
	freopen("select.out", "w", stdout);
    for (int i = 1; i <= N; i++) pop[i] = pop[i >> 1] + (i & 1);
    scanf("%d %d", &n, &Q);
    for (int i = 1; i <= n; i++) {
    	int x;
    	scanf("%d", &x);
    	for (int j = 1; j <= N; j++) sum[i][j] = sum[i - 1][j] + ((x & j) == x);
    }
    while (Q--) {
        int l, r, x;
        ll res = 0;
        scanf("%d %d %d", &l, &r, &x);
        for (int i = 1; i < N; i++) {
        	if ((x & i) != i) continue;
        	int now = pop[x] - pop[i];
        	ll ans;
        	if (now & 1) ans = -1;
        	else ans = 1;
        	ans *= (sum[r][i] - sum[l - 1][i]) * 1ll * (sum[r][i] - sum[l - 1][i] - 1) * 1ll * (sum[r][i] - sum[l - 1][i] - 2) / 6ll;
        	res += ans;
        }
        printf("%lld\n", res);
    }
    return 0;
}