BZOJ 4762: 最小集合

好劲的题啊……苦想了1h然后又看了1h题解推来推去才会做，不过实在是太妙了的说

注意到限制\(2\)可以转化为：满足限制\(1\)的集合\(S\)若拿掉它的任意一个元素那么都不会符合限制\(1\)（因为\(\and\)只会越来越小，因此让子集的大小尽量大）

首先我们定义\(f(S)\)表示\(\bigwedge_{a\in S} a\)，\(S_a\)表示\(S\and C_S \{a\}\)，即\(S\)集合里去掉元素\(a\)

然后我们来形式化的写一写答案的式子：

\(ans=\sum_S [f(S)=0]\and [\forall_{a\in S} f(S_a)\not =0]\)

对于后面的这个$ [\forall_{a\in S} f(S_a)\not =0] $，我们容斥一下就有：

\[ans=\sum_S [f(S)=0]\and \sum_{S'\subseteq S}[\forall_{a\in S'} f(S_a)=0](-1)^{|S'|}\]

注意到\(\forall_{a\in S'} f(S_a)=0\Leftrightarrow(\bigvee_{a\in S'} f(S_a))=0\)

再代回去就有：

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

注意到这个式子可以看成两个条件\(f(S)=0\)和\((\bigvee_{a\in S'} f(S_a))=0\)以及一个权值\((-1)^{|S'|}\)

那么我们不如把前面两个值放到DP的状态里，然后记录的是后面的这个值（大胆的想法）

设\(f_{i,j,k}\)表示做了前\(i\)个数，当前的\(f(S)=j\)，对于枚举的\(S'\)有\((\bigvee_{a\in S'} f(S_a))=k\)时\((-1)^{|S'|}\)的和

对于现在的\(a_i=x\)，有以下的三种转移：

1. \(x\not \in S\)，此时\(f_{i,j,k}+=f_{i-1,j,k}\)，含义十分明显
2. \(x\in S\)，\(x\not \in S'\)，此时\(f_{i,j\and x,k\and x}+=f_{i-1,j,k}\)，此时虽然\(x\in S'\)但是对于每一个枚举的\(S'\)它们的\(f(S_a)\)都要多\(\and\)上一个\(x\)
3. \(x\in S\)，\(x\in S'\)，此时\(f_{i,j\and x,j\or (k\and x)}-=f_{i-1,j,k}\)，乍一看很难理解，实际上妙不可言。第三维\((k\and x)\)的含义与\(2\)类似，因为就算\(x\)加入了\(S'\)，\(S'\)中其它的元素\(a'\)的\(f(S_{a'})\)也是需要\(\and\)上\(x\)的。当\(a=x\)时，此时\(f(S_a)\)将不包括\(x\)，因此要\(\or\)上原来的\(f(S)\)

这样一看复杂度好像是\(O(n\times 1024^2)\)的，但是我们细细分析一下就会发现\(j\subseteq k\)，因此复杂度是\(O(n\times 3^{10})\)（原本的两维独立变成了枚举子集）

然后\(f\)滚存一下即可，初始值是\(f_{0,1023,1023}=1\)（注意后面的转移都是\(\and\)），最后的答案就是\(f_{n,0,0}\)（根据推出的式子）

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=1024,mod=1e9+7;
int n,x,f[2][N][N];
inline void inc(int& x,CI y)
{
    if ((x+=y)>=mod) x-=mod;
}
int main()
{
    RI nw=0,i,j,k; for (scanf("%d",&n),f[nw][N-1][N-1]=i=1;i<=n;++i)
    {
        for (scanf("%d",&x),nw^=1,k=0;k<N;++k)
        for (j=k;;j=(j-1)&k) { f[nw][j][k]=0; if (!j) break; }
        for (k=0;k<N;++k) for (j=k;;j=(j-1)&k)
        {
            int tp=f[nw^1][j][k]; if (tp)
            inc(f[nw][j][k],tp),inc(f[nw][j&x][k&x],tp),
            inc(f[nw][j&x][k&x|j],mod-tp); if (!j) break;
        }
    }
    return printf("%d",f[nw][0][0]),0;
}

BZOJ 4762: 最小集合

原文：https://www.cnblogs.com/cjjsb/p/12256231.html