首页 > 代码库 > Codeforces Round #257 (Div. 1) (Codeforces 449D)

Codeforces Round #257 (Div. 1) (Codeforces 449D)

2024-07-13 05:16:07   222人阅读

思路：定义f(x)为 Ai & x==x  的个数，g(x)为x表示为二进制时1的个数，最后答案为    。为什么会等于这个呢：运用容斥的思想，如果 我们假设 ai&x==x 有f（x）个，那么 这f(x)个 组成集合的子集 & 出来是 >=x那么我们要扣掉>x的 。。。  因为这里我们要求的是 & 之后等于0 一开始1个数为0那么就是 1个数为偶数时加上去，  为奇数时减掉了。

 那么就剩下求f(x)    。我们把A[i]和x的二进制 分成  前 （20-k）位和  后 k 位时  X1表示A[i]前20-k位 ,X2表示A[i]后k位， Y1表示x前20-k 位,Y2表示A[i]后k位。

　d[k][x] 表示X1==Y1  &&  (X2&Y2==Y2) 那么 d[k][x]转移就能O（1） 转移  ,如下：

当（x&(1<<(k-1))）==1时 d[k][x]=d[k-1][x],   当（x&(1<<(k-1))）==0时d[k][x]=d[k-1][x]+d[k-1][x+(1<<(k-1)];

 

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include <iostream>#define N 1050000#define LL __int64#define MOD 1000000007using namespace std;int f[22][N];int a[N];LL qmod(LL a, LL b) {    LL res = 1;    while (b) {        if (b & 1)            res = (res * a) % MOD;        a = (a * a) % MOD;        b >>= 1;    }    return res;}int cal(int i) {    int flag = 0;    int res = (int) qmod(2, f[20][i]);    while (i) {        if (i & 1)            flag++;        i >>= 1;    }    if (flag & 1)        return -res;    else        return res;}int main() {    int n;    scanf("%d", &n);    int w = (1 << 20);    for (int i = 1; i <= n; ++i) {        scanf("%d", &a[i]);        f[0][a[i]]++;    }    for (int k = 1; k <= 20; ++k) {        for (int i = 0; i < w; ++i) {            if (i & (1 << (k - 1))) {                f[k][i] = f[k - 1][i];            } else {                if (i + (1 << (k - 1)) < w)                    f[k][i] = (f[k - 1][i] + f[k - 1][i + (1 << (k - 1))])                            % (MOD - 1);                else                    f[k][i] = f[k - 1][i];            }        }    }    int ans = 0;    for (int i = 0; i < w; ++i) {        ans = (ans + cal(i)) % MOD;    }    printf("%d\n", (ans+MOD)%MOD);    return 0;}
View Code


联系
我们