或与异或 [背包DP]

也许更好的阅读体验

\(\mathcal{Description}\)
给定\(n\)和长度为\(n\)的数组\(a\)
问从\(a\)中选取任意个数使得其 异或起来的值 等于 或起来的值 的方案数

\(n\leq 50,a_i\leq 2^{13}\)

\(\mathcal{Solution}\)

考虑枚举最终答案是什么，即最后或起来的值是什么
这样是\(2^{13}\)的复杂度
之后把这个值的子集求出来，这是\(2^s\)的复杂度
把合法的\(a\)提出来
设\(f_{i,j}\)表示前\(i\)个数异或起来为\(j\)的方案数，直接做背包\(DP\)即可
设枚举到的答案是\(s\)，\(DP\)的复杂度为\(n*2^s\)
总复杂度为\(\sum\limits_{i=1}^{13}\begin{pmatrix}n\\i\end{pmatrix}2^i*n=n\sum\limits_{i=1}^{13}\begin{pmatrix}n\\i\end{pmatrix}2^i*1^{n-i}=n\left(2+1\right)^{13}=3^{13}n\)

\(\mathcal{Code}\)

/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年10月28日 星期一 14时27分41秒
*******************************/
#include <cstdio>
#include <fstream>
#define ll long long
using namespace std;
const int maxn = 55;
const int maxm = 16485;
//{{{cin
struct IO{
    template<typename T>
    IO & operator>>(T&res){
        res=0;
        bool flag=false;
        char ch;
        while((ch=getchar())>'9'||ch<'0')   flag|=ch=='-';
        while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
        if (flag)   res=~res+1;
        return *this;
    }
}cin;
//}}}
int n,S,cnt,tot;
int a[maxn],s[maxm],v[maxn];
ll ans;
ll f[maxn][maxm];
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)  cin>>a[i];
    S=(1<<14)-1;

    for (int i=1;i<=S;++i){
        cnt=tot=0;
        for (int j=i;j;j=(j-1)&i)   s[++cnt]=j;
        s[++cnt]=0;

        for (int j=1;j<=n;++j)
            if ((a[j]|i)==i)    v[++tot]=a[j];

        f[0][0]=1;
        for (int j=1;j<=tot;++j)
            for (int k=1;k<=cnt;++k)    f[j][s[k]]=f[j-1][s[k]^v[j]]+f[j-1][s[k]];

        ans+=f[tot][i];
    }

    printf("%lld\n",ans);
    return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

或与异或 [背包DP]

原文：https://www.cnblogs.com/Morning-Glory/p/11754576.html