AT_abc390_d [ABC390D] Stone XOR

· · 题解

Link

先 E 后 D，我还是太唐了。

你真的会搜索吗？不错的搜索剪枝题。

我们考虑这样的一种搜索方式，相当于有 n 个盒子，我们把这 n 个数随便扔到某个盒子里面去，然后计算答案。

这样时间复杂度大概是 O(n\times n^n) 状物，非常倒闭。

但是我们注意到不少状态是重复的。

我们可以注意到对于第一个数，我们放在任意一个盒子，是同一个效果，所以我们钦定放在第一个，第二个数只有放在第一个或第二个才有效果。

所以我们对于第 i 个数，只用枚举放在前 i 个盒子里面。这样我们就优化到了 O(n\times n!)，还是不够。

其实还能再优化一下，我们只能放到第一个为 0 的位置，往后放效果都是一样的。

计算一次答案是 O(n) 级别的，还是很浪费时间。继续考虑优化，就是你边加数边计算，根据 x \oplus x=0 性质即可。

然后标记数字直接用 umap 即可，我开始用 map 没过。

然后就过了，经过最后一次的优化后，方案数是贝尔数级别的，n=12 可以通过，虽然我不知道为啥。

这就是实现精细些的巨大效果。如何呢。

#include<bits/stdc++.h>
using namespace std;
const int N =1e3+10;
#define int long long 
double eps=1e-7;
vector<int> g[N];
int a[N],Ans,n,Now[N];
unordered_map<int,int> mp;
void dfs(int dis,int preans){
    if(dis==n+1){
        if(!mp.count(preans))   Ans++,mp[preans]=true;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(Now[i]==0&&Now[i-1]==0)  break;
        int lst=preans;
        preans^=Now[i],Now[i]+=a[dis],preans^=Now[i];
        dfs(dis+1,preans);
        Now[i]-=a[dis],preans=lst;
    }
}
signed main(){
    cin>>n,Now[0]=100;
    for(int i=1;i<=n;i++)   cin>>a[i];
    dfs(1,0);
    cout<<Ans<<endl;
    return 0;
}