SOS-DP(子集DP)_牛客博客

简单的求子集和的4种做法:

$1:4^n$

for(int i=0;i<(1<<n);i++)
    for(int j=0;j<i;j++)
        if(j&i==j)F[i]+=A[j];

$2:3^n$

for(int i=0;i<(1<<n);i++)
{
    F[i]=A[0];
    for(int j=i;j>0;j=(j-1)&i)
        F[i]+=A[j];
}

$3:2^n \times n$ ，这一做法用到了高位前缀和

for(int i=0;i<n;i++)
    for(int j=0;j<(1<<n);j++)
        if(j&(1<<i))F[j]+=F[j^(1<<i)];

$4:2^n \times n$ ，这一做法是fwt的一个特性

代码不给出了，就是做一遍or卷积，而方法3的做法和fmt差不多，也就是为什么有些人不写fwt写fmt的原因。

技巧：

如果我们现在有 $F[i]= \sum_{j \& i=j}F[j]$
我们要求i除去i的真子集后的值。我们只需倒着做一遍即可。

for(int i=N-1;i>=0;i--)
{
    for(int j=0;j<(1<<N);j++)
    if(j&(1<<i))Add(F[j],mod-F[j^(1<<i)]);
}

例题：

CF1208F

You are given an array a of n integers.
You need to find the maximum value of ai|(aj&ak) over all triplets (i,j,k) such that i<j<k.

有点难度，首先转化题目 $max(ai|(aj \& ak))=max(ai \& (aj|ak))$

然后就是对于每个ai进行考虑，因为是 and ,所以肯定是从高位到低位贪心。所以我们只要求出有多少数在第 $pos$ 位上是1，且前 $pos-1$ 位是 $S$ 。这个直接子集DP一波即可。

原先只要高位前缀和一下就行，但现在是每次加入一个数，那么就要麻烦一点（需要对子集DP有一定理解）。

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
const int N=2e6+5;
int n,ans,a[N],dp[N][21];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void add(int x,int y)
{
    if(y>20)return;
    if(dp[x][y]>1)return;
    dp[x][y]++;
    add(x,y+1);
    if(x&(1<<y))add(x^(1<<y),y);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=n;i;i--)
    {
        int res=0,S=0;
        for(int j=20;j>=0;j--)
            if(a[i]&(1<<j))res+=(1<<j);
            else if(dp[S+(1<<j)][20]>1)
            {
                res+=(1<<j);
                S+=(1<<j);
            }
        add(a[i],0);
        if(i<=n-2)ans=max(ans,res);
    }
    cout<<ans;
    return 0;
}

SPECIAL PAIRS

求 $ai \& aj=0$ 的 $(i,j)$ 个数

子集DP就是枚举ai,然后求F[(1<<n)-1-ai]。

当然FWT的and卷积更简单（模板）

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
const int N=5e6+5;
int n,a[N],F[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        F[a[i]]++;
    }
    int ma=(1<<22)-1;
    for(int i=0;i<22;i++)
        for(int j=0;j<=ma;j++)
            if(j&(1<<i))F[j]+=F[j^(1<<i)];
    for(int i=1;i<=n;i++)
        ans+=F[ma-a[i]];
        cout<<ans/2;
    return 0;
}

E. Compatible Numbers

求对于每一个ai，是否存在aj，使 $ai \& aj =0$

和上一题差不多，就是一个简单的高位前缀和。

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
const int N=5e6+5;
int n,a[N],F[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        F[a[i]]=a[i];
    }
    int ma=(1<<22)-1;
    for(int i=0;i<22;i++)
        for(int j=0;j<=ma;j++)
            if(j&(1<<i)&&F[j^(1<<i)])F[j]=F[j^(1<<i)];
    for(int i=1;i<=n;i++)
    {
        if(F[ma-a[i]]>0)printf("%d ",F[ma-a[i]]);
        else printf("%d ",-1);
    }
    return 0;
}

E.Vowels

对于24个字母，选出若干字母当“元音”，一个字符串是好的，至少有一个字符是“元音”。
答案是所以情况的好字符串个数的平方的异或和。

最简单的想法，枚举元音的状态，计算有多少个字符串是好的。
考虑如何快速求出F[S]，表示元音状态为S，的好字符串个数。发现需要容斥，1个字符-2个字符+......。这样就能用子集DP来解决了

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=(1<<24)+5;
int n,ans,F[N];
char s[15];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        int t=0;
        for(int i=1;i<=3;i++)
            t|=(1<<(s[i]-'a'));
        for(int i=t;i>0;i=(i-1)&t)
            if(__builtin_popcount(i)%2==1)F[i]++;
            else F[i]--;
    }
    for(int i=0;i<24;i++)
        for(int j=0;j<(1<<24);j++)
            if(j&(1<<i))F[j]+=F[j^(1<<i)];
    for(int i=0;i<(1<<24);i++)
        ans=ans^(F[i]*F[i]);
    cout<<ans;
}

还有些例题请参考：巨佬博客