51nod 1407

一道非常不错的容斥题（也有利于理解前缀和）

下面我将两种方法：

1.一般在网上搜到的方法，首先算出1406题的答案，dp[i]表示n个数中满足x&i==i的x有几个，然后我们考虑 dp[i]所代表的所有数互相&，出去空集外共有 2dp[i] 种，这些方案代表了所有&和包含i的方案，即i上的1都有，其他的任意，这样我们就可以容斥了，Ans=所有方案数-不合法的方案数，不合法的怎么算？一位数字的总数-两位数字总数+三位……，Ans=0位的-1位的+2位的……

2.前缀和版本，这种版本还可以解释1406，在二维平面上求前缀和我们可以这样;

for (int i=;i<=n;i++)
    for (int j=;j<=m;j++)
        s[i][j]+=s[i-][j];
for (int i=;i<=n;i++)
    for (int j=;j<=m;j++)
        s[i][j]+=s[i][j-];     
           

这种一维一维求的方法挺直观的，

这道题目每个数字是不是可以看成20维数，而且每一维只能是0或1；

x&i==i，那么是不是x的每一维都大于i的每一维？

就是求一个前缀和喽，可以自行脑补一维的，二维的和三维的

而我们要求的包含i的数是不是每一位都大于等于i的数的个数，这是不是就是求一个后缀和？

for (int i=;i<(<<);i<<=)
        for (int j=;j<(<<);j+=*i) //这样枚举保证j第i位为0;
            for (int k=j;k<j+i;k++)
                sum[k]+=sum[k+i]; //此处sum[i]含义为包含i的数的个数; 
           

这里还有一种神奇的枚举方式，先枚举1在哪一位，再枚举前面的1，再枚举后面的1，就好了，

这样我们求出了1406要求的答案，那怎么做这一题呢？

我们发现，包含i的数任意组合&还是包含i，所以 2sum[i]−1 就表示所有包含i的组合方式，为什么，假设有一种组合方式，他们所有的数一定在i的数位上为1，这样的数就符合上一题的要求被统计进sum[i]了，

这样我们求出了包含i的所有组合方案，这时候我们在进行上面的求后缀和的逆过程就可以求出所有==i的方案了

for (int i=;i<(<<);i++) sum[i]=pow[sum[i]]-;
    //此处sum[i]含义为&和包含i的方案数;  
    for (int i=;i<(<<);i<<=)
        for (int j=;j<(<<);j+=*i) //这样枚举保证j第i位为0;
            for (int k=j;k<j+i;k++)
                    sum[k]=(sum[k]-sum[k+i]+MOD)%MOD;   
                    //此处sum[i]含义为&和==i的方案数;