ABC-390-D - Stone XOR · znzryb
## 思路讲解
想这样枚举是会超时的，我们发现其实元素加入顺序其实不重要，重要的是这个元素加入到了哪个组中
```cpp
for (int i=1; i<=N; ++i) {
if(vis[i]) continue;
for(int j=1;j<=groups+1;++j){
sumG[j]+=A[i];
vis[i]=true;
dfs(cur+1,max(groups,j));
sumG[j]-=A[i];
vis[i]=false;
}
}
```
所以说只需要减少枚举维度就行了（不再枚举元素）
```cpp
for(int j=1;j<=groups+1;++j){
sumG[j]+=A[dep];
// vis[dep]=true;
dfs(dep+1,max(groups,j));
sumG[j]-=A[dep];
// vis[dep]=false;
}
```
## AC代码
AC
[https://atcoder.jp/contests/abc390/submissions/62115363](https://atcoder.jp/contests/abc390/submissions/62115363)
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=17;
ull N,T;
ull A[MAXN];
string s;
unordered_set<ull> st;
//bool vis[MAXN];
ull sumG[MAXN];
// dep就是指当前要计算的用掉的总数量，groups是指现在的组数
void dfs(int dep,int groups) {
if(dep>N){
ull res=0;
for (int i=1; i<=groups; ++i) {
res^=sumG[i];
}
st.insert(res);
return;
}
for(int j=1;j<=groups+1;++j){
sumG[j]+=A[dep];
// vis[dep]=true;
dfs(dep+1,max(groups,j));
sumG[j]-=A[dep];
// vis[dep]=false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N;
for(int i=1;i<=N;++i) {
cin>>A[i];
}
dfs(1,0);
cout<<st.size()<<endl;
// cout<<endl;
// for(auto it:st) {
// cout<<it<<endl;
// }
return 0;
}
/*
AC https://atcoder.jp/contests/abc390/submissions/62115363
*/
```
## 心路历程（WA，TLE，MLE……）
TLE
[https://atcoder.jp/contests/abc390/submissions/62115165](https://atcoder.jp/contests/abc390/submissions/62115165)
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=17;
ull N,T;
ull A[MAXN];
string s;
unordered_set<ull> st;
bool vis[MAXN];
ull sumG[MAXN];
// cur就是指当前要计算的用掉的总数量，groups是指现在的组数
void dfs(int cur,int groups) {
if(cur>N){
ull res=0;
for (int i=1; i<=groups; ++i) {
res^=sumG[i];
}
st.insert(res);
return;
}
for (int i=1; i<=N; ++i) {
if(vis[i]) continue;
for(int j=1;j<=groups+1;++j){
sumG[j]+=A[i];
vis[i]=true;
dfs(cur+1,max(groups,j));
sumG[j]-=A[i];
vis[i]=false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N;
for(int i=1;i<=N;++i) {
cin>>A[i];
}
dfs(1,0);
cout<<st.size()<<endl;
// cout<<endl;
// for(auto it:st) {
// cout<<it<<endl;
// }
return 0;
}
/*
*/
```