BZOJ 4762 容斥 DP

定义一个非空集合是合法的,当且仅当它满足以下两个条件。

  1. 集合内所有元素and和为0;
  2. 它的非空子集中仅有它本身满足1.

给出一个集合S,求它的合法非空子集数。

$ |S|\le 1000, a_i<1024 $ .

Sol.

很棒的容斥题.

$ S $ 的 AND 和合法, iff 任意 $ |S-1| $ 大小的子集的 AND 和不为零.

定义 $ S_a:=S-\{a\}, f(S):=\&_{i\in S} i $ .

题目等价求

$$ \begin{align} \sum_S[f(S)=0 \and \bigwedge_{a\in S} (f(S_a)\neq0)] = \sum_S[f(S)=0][\bigwedge_{a\in S}(f(S_a)\neq 0)] \end{align} $$

对后项考虑运用 De Morgan 后容斥,有

$$ [\bigwedge_{a\in S} (f(S_a)\neq 0)] = \sum_{S' \sub S} [\bigwedge_{a\in S'} (f(S_a)=0)](-1)^{|S'|} $$

注意到 $ [\bigwedge_{a\in S'}(f(S_a)=0)] = [\bigvee_{a\in S'} f(S_a)=0] $ ,代入原式

$$ \sum_S\sum_{S'\sub S}[f(S)=0][\bigvee_{a\in S'}f(S_a) = 0](-1)^{|S'|} $$

现在可以很方便的设计状态啦~

设 $ f_{i,k,j} := $ 前 $ i $ 个元素前项值为 $ k $ 后项值为 $ j $ 的方案数,初值 $ f_{0,1023,1023}=1 $ ,答案为 $ f_{n,0,0} $ .

分别考虑不加入 $ S $ ;加入 $ S $ 但不加入 $ S' $ ;加入 $ S' $ . 转移如下

$$ \begin{align} f_{i+1,k,j} &\leftarrow f_{i,k,j} \\ f_{i+1,k,j\&d} &\leftarrow f_{i,k,j} \\ f_{i+1,k\&d,k|j\&d} &\leftarrow -f_{i,k,j} \end{align} $$

枚举子集即可.

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1030, mod = 1e9 + 7;
int f[2][maxn][maxn];
int main()
{
    int n; read(n);
    f[0][1023][1023] = 1;
    for(int i = 1, d; i <= n; ++i)
    {
        read(d);
        for(int j = 0; j < 1024; f[i & 1][0][j] = 0, ++j) for(int k = j; k; k = (k - 1) & j)
            f[i & 1][k][j] = 0;
        for(int j = 0; j < 1024; ++j) 
        {
            for(int k = j; k; k = (k - 1) & j) if(f[i & 1 ^ 1][k][j])
                (f[i & 1][k][j] += f[i & 1 ^ 1][k][j]) %= mod, (f[i & 1][k & d][j & d] += f[i & 1 ^ 1][k][j]) %= mod, (f[i & 1][k & d][k | j & d] += (mod - f[i & 1 ^ 1][k][j])) %= mod;
            (f[i & 1][0][j] += f[i & 1 ^ 1][0][j]) %= mod, (f[i & 1][0][j & d] += f[i & 1 ^ 1][0][j]) %= mod, (f[i & 1][0][j & d] += (mod - f[i & 1 ^ 1][0][j])) %= mod;
        }
    }
    printf("%d\n", f[n & 1][0][0]);
    return 0;
}

标签: none

添加新评论