BZOJ 4762 容斥 DP

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)^{|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^{|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

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu