专栏首页数据结构与算法cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

题意

题目链接

给出\(n\)个数,问任意选几个数,它们\(\&\)起来等于\(0\)的方案数

Sol

正解居然是容斥原理Orz,然而本蒟蒻完全想不到。。

考虑每一种方案

答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案

至少有\(i\)位为\(1\)的方案可以dp算,设\(f[x]\)表示满足\(f[x] = a_i \& x = x\)的\(a_i\)的个数

最终答案$ = (-1)^{bit(i)} f[i]$

\(f\)数组可以通过高维前缀和预处理

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
using namespace std;
const int MAXN = 3e6 + 10, mod = 1e9 + 7, B = 20;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], bit[65537], f[MAXN];
int add(int &x, int y) {
    if(x + y < 0) x = x + y + mod;
    else x = (x + y >= mod ? x + y - mod : x + y);
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a); p >>= 1;
    }
    return base;
}
int get1(int x) {
//  return __builtin_popcount(x);
    return bit[x & 65535] + bit[x >> 16];
}
int main() {
    for(int i = 1; i <= 65536; i++) bit[i] = bit[i >> 1] + (i & 1);
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read(), f[a[i]]++;
    int Lim = (1 << B) - 1, ans = 0;
    for(int i = 0; i <= 20; i++)
        for(int sta = 0; sta <= Lim; sta++) 
            if(!(sta & (1 << i))) add(f[sta], f[sta | (1 << i)]);
    for(int sta = 0; sta <= Lim; sta++) {
        int k = (get1(sta) & 1) ? -1 : 1;
        add(ans, mul(k, fp(2, f[sta])));
    }
    cout << ans;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforces415D. Glad to see you!

    交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$

    attack
  • 洛谷P4197 Peaks(Kruskal重构树 主席树)

    考虑把Kruskal重构树建出来,重构树上每个新的节点代表的是边权,同时用倍增数组维护出跳2^i步后能走到的值最大的节点

    attack
  • cf1136E. Nastya Hasn't Written a Legend(二分 线段树)

    显然从一个位置开始能影响到的位置是单调的,而且这些位置的每个改变量都是\((a_i + x) + \sum_{t=i}^{j-1} k_t\)

    attack
  • codeforces415D. Glad to see you!

    交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$

    attack
  • 挑战程序竞赛系列(26):3.5二分图匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 位操作运算有什么奇技淫巧?(附源码)

    比如说16位二进制数A:1001 1001 1001 1000,如果来你想获A的哪一位的值,就把数字B:0000 0000 0000 0000的那一位设置为1.

    李肖遥
  • 位操作运算有什么奇技淫巧?(附源码)

    比如说16位二进制数A:1001 1001 1001 1000,如果来你想获A的哪一位的值,就把数字B:0000 0000 0000 0000的那一位设置为1.

    刘盼
  • ViewDragHelper使用笔记及侧滑菜单实践

    佛系编码
  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • 计算机二级大题.

    1题 #include <iostream> using namespace std; class MyClass { public: MyClass(...

    东风冷雪

扫码关注云+社区

领取腾讯云代金券