天行廖的游戏

题目连接：

http://acm.uestc.edu.cn/#/problem/show/1294

Description

天行健，君子以自强不息。地势坤，廖爷以厚德载物

一日在喵哈哈村，天行廖和沈宝宝正在玩一个游戏。

天行廖分别在$N$个纸片上写上一个数字，并放到一个盒子中。

现在沈宝宝要从盒子中抓出任意张纸片。

如果沈宝宝抓出的纸片上的数字$A\_{i1}$,$A\_{i2}$,....$A\_{ik}$满足$A\_{i1}$ & $A\_{i2}$ & ....$A\_{ik}$$ = 0$ ( $i\_{1} < i\_{2} … < i\_{k}$)，那么天行廖赢得这次游戏的胜利，否则沈宝宝赢。

Input

第一行输入$1$个整数$N。$($1 \leq N \leq 10^6$)

第二行输入$N$个整数$A\_1，A\_2....A\_N$。($1 \leq A_i \leq 10^6 $)

Output

输出获胜的方案数量。因为结果可能很大，输出答案对$10^9+7$取模的结果即可。

Sample Input

6

5 2 0 5 2 1

Sample Output

Hint

题意

题解：

首先，我们再看一遍题意：对于一个长度为n的数列a1,a2...an，挑出任意个数，使得这些数的且运算结果为0。

首先暴力2^n枚举是肯定不行的。考虑不那么暴力的DP做法，令dp[i][j]表示从前i个数选结果为j的方案有多少种，转移方程为dp[i][j] = sigma(dp[i - 1][k]) (k & a[i] = j)，复杂度为n^3，显然也不行...

于是我们考虑是否能用容斥原理做。1e6的二进制表达式有20位，总方案数为2^n，然后我们减去结果第一位为1的方案数，第二位为2的方案数...第二十位为1的方案数，即某一位为1的方案数。然后根据容斥原理，我们再加上结果某两位为1的方案数，减去结果某三位为1的方案数...，加上全为1的方案数。假设F(i)为结果为i的方案数量(令F(0) = 2 ^ n)，g(i)为i二进制下1的个数，则ans = sigma(F(i)*(-1)^(g(i)))。

那么现在问题即如何计算F(i)。若要使得k个数b1,b2...,bk的且运算为i，那么对于所有i为1的位，任意bj在该位置上也都为1，即bj & i = i。如果我们能算出满足aj & i = i的数的个数cnt(i)，就能得到F(i) = 2 ^ cnt(i)，于是问题转换为如何快速计算cnt(i)。

我们令cnt[k][i]表示只有前k位与i不同且满足aj & i = i的数的个数，边界cnt[0][i]表示正好为i的数的个数。现在分两种情况讨论cnt[k][i]的递推式:

1、i的第k位是1，那么cnt[k][i] = cnt[k - 1][i]，因为若第k位不同,则与i作且运算是第k位为0，所以相当于只有前k-1位不同。

2、i的第k位是0，则是第k位0或1没有影响,对比第一种情况需要加上前k-1位不同且第k位为1的数的个数。显然这个方案数等于dp[k - 1][i + 2^k]，则得到递推式cnt[k][i] = cnt[k - 1][i] + cnt[k - 1][i + 2 ^ k]。

因为位数K最大为log(1e6)约等于20,于是我们就能在O（NK）（K=20）的复杂度计算出cnt(i)，并在O（N）的时间内完成容斥的计算，总时间复杂度为O（NK）。至此，我们解完了这题。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1 << 20;

const LL MOD = 1e9 + 7;

int n,m;

LL dp[21][N];

///dp[i][x]表示,二进制下只有前i位可能与x不同的数与x进行and运算仍然为x的数的个数

LL g[N];

bool s[N];

void init()

{

    scanf("%d",&n);

    g[0] = 1;

    for(int i = 1;i <= n;i++) g[i] = (g[i - 1] << 1LL) % MOD;

    int f0;

    for(int i = 1;i <= n;i++)

    {

        scanf("%d",&f0);

        dp[0][f0]++;

    }

}

void work()

{

    for(int i = 1;i <= 20;i++)

    {

        for(int j = 0;j < N;j++)

        if( (j & (1 << (i - 1)) ) == 0)

          dp[i][j] = dp[i - 1][j] + dp[i - 1][j | (1 << (i - 1))];

        else

          dp[i][j] = dp[i - 1][j],s[j] ^= 1;

    }

    LL ans = 0;

    for(int i = 0;i < N;i++)

      ans = ( ans + (s[i]?(-1LL):1LL) * g[dp[20][i]] + MOD ) % MOD;

    printf("%lld\n",ans);

}

int main()

{

    init();

    work();

    return 0;

}

天行

CDOJ 1294 天行廖的游戏 dp 容斥