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的方案數;