2015年7月4日 星期六

[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) ;
}
 

沒有留言:

張貼留言