[CF 449D] Jzzhu and Numbers

作法：

考慮一個$n\times 20$的表格，其中第$i$列就是把第$i$個數的二進制表示寫成橫的放在表格中。現在我們要算的東西是：要選出好幾個橫排，使得這些橫排的每個直行裡都至少有一個$0$，我們反過來看單一一個直行中的所有$1$形成的一個$\{ 1,2,...,n \}$的子集合，假設第$i$個直行的這樣的集合為$S_i$（$i=0,...,19$），那麼對於某個集合$T$來說，如果他是某個$S_i$的子集合，那麼$T$就是不符合條件的集合，並且反過來也是對的。因此我們只要算出「$S_0,...,S_{19}$總共有多少種不重複的子集合」就可以了。這可以用排容算，因為「$S_i$的所有子集合」可以看成一個集合，我們要算的就是這$20$個集合的聯集大小。因此我們需要知道：給定一個$\{0,...,19\}$的子集合${c_1,...,c_r}$，那麼$S_{c_1}\bigcap ... \bigcap S_{c_r}$中共有幾個數，對於所有$\{0,...,19\}$的子集合都必須知道這件事的答案。這裡要觀察到，如果$x\in S_{c_1}\bigcap ... \bigcap S_{c_r}$，那麼代表在第$x$列中的第$c_1,...,c_r$個位子都是$1$，也就是可以改寫為$a[x]\& S = S$，其中$S$代表$c_1,...,c_r$用位元壓起來的數。有了這件事之後，假設我們要算的陣列叫$num$陣列（也就是$num[S]$代表上述所說的$S_{c_1}\bigcap ... \bigcap S_{c_r}$大小，其中$S$是由$c_1,...,c_r$位元壓縮起來的）（大小為$2^{20}$），那麼就可以從另一個角度去算$num$陣列，就是在讀入一個$a[i]$時，將所有滿足$S\& a[i]=S$的$S$的$num$值都$+1$（或是說把輸入的$a[i]$看成一個集合的 bit ，那麼舊把這集合的子集合對應的 index 的$num$值都$+1$），那麼全部讀完後就會是我們要的$num$陣列了。而上面這件事又等價於：記$f[x]$代表在輸入中有幾個$x$，那麼$num[S]$的值就會等於所有$f[x]$的值，其中$x$滿足$x\& S=S$（或是說$x$是$S$的子集）。我們考慮固定$S$時要怎麼求出$num[S]$的值，例如$S$的二進制長的像$1010$好了，那麼就直接從最左邊那位往右 DFS 下去，遇到$1$的話代表這位只能放$1$，遇到$0$則代表這位可以放$1$或$0$，這樣我們會DFS到的數就會是$1010,1011,1110,1111$，恰好是所有滿足$S\& x=S$的$x$，把他們的$f$值加起來就是我們要的答案了。觀察剛才DFS的過程，我們可以用「當前已經確定到第幾位了」還有「當前的數字是多少」來當作傳入DFS的參數，那麼就不難發現這其實可以改成一個DP了（$dp[21][2^{20}]$），並且轉移式只要看DFS時是怎麼求答案的就可以了。邊界為當所有位子都確定時就回傳$f$的值，也就是$dp[20][i]=f[i]$。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=1<<20 ;
 
int dp[21][maxn] ;
int pw2[maxn] ;
main()
{
    for(int i=0;i<maxn;i++) pw2[i]= i?pw2[i-1]*2%MOD : 1 ;
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        int x ; scanf("%d",&x) ;
        dp[0][x]++ ;
    }
    for(int d=0;d<20;d++) for(int i=0;i<(1<<20);i++)
        dp[d+1][i]=dp[d][i]+( (i&(1<<d)) ? 0 : dp[d][i+(1<<d)] ) ;
 
    LL ans=0LL ;
    for(int i=1;i<(1LL<<20);i++)
        ans=(ans+(__builtin_popcount(i)%2 ? 1 : -1)*pw2[dp[20][i]])%MOD ;
    printf("%I64d\n",(pw2[n]-ans+MOD)%MOD) ;
}