abc 390 D(暴搜 复杂度用 bell数 证明 n 的集合的划分方法的数目）

D题意：
将 长度为 N 的数组 划分为集合 有多少种不同的 异或和
这道题做出来和bell 数没什么关系，如果要证明复杂度那么就需要bell 数

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long 
int n;
unordered_set<int>se;
int a[14];
int b[14];// 存放已经的划分集合
//int cnt=0;
// 考虑第pos 位，再次之前已经有了cnt 个集合
void dfs(int pos,int cnt)
{if (pos>n){   int t=0;for (int i=1;i<=cnt;i++){t^=b[i];}se.insert(t);return;}// 新开一个集合b[cnt+1]=a[pos];dfs(pos+1,cnt+1);// 放到前面已经有的集合中for (int i=1;i<=cnt;i++){b[i]+=a[pos];dfs(pos+1,cnt);b[i]-=a[pos];}}
void solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dfs(1,0);cout<<se.size()<<"\n";
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin>>t;while (t--){solve();}return 0;
}