题解：P9316 [EGOI 2021] Double Move / 二选一游戏

· · 题解

二元操作关系，我们不妨直接考虑建图。容易发现若把每次操作的 (u,v) 连边后，由于每条边需要对应一个点，则每个连通块的边数不超过点数。且根据连通块定义，边数至少是点数 -1。即每个连通块为树或基环树。

令连通块点集为 S，容易发现树的定向方案数为 |S|（钦定某个点还未被选择），基环树的定向方案数为 2（钦定某条边方向后其余确定）。由此可知，我们并不关心连通块的具体形状，只关心其边数与点数。

对于前 k 次操作，每次相当于合并两棵树，把一棵树变成基环树或合并一棵树和基环树。不属于以上操作的均会直接导致游戏结束。则我们简单模拟并计算方案即可。

对于后 k 次操作，同样也只有以上三种操作有效。但我们发现由于一棵基环树内的点必然已经被完全选择，因此合并一棵树和一棵基环树的操作等价于直接在树内部选点变基环树。这也告诉我们基环树对我们目前状态已经无用。因此我们只需要记录目前每棵树的大小即可。

状态数等价于选出可重集 S，使得 \sum S \le n，当 n=35 时状态数完全可以接受。因此我们暴力记录此状态后暴力枚举每次操作进行对抗搜索即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=40;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int n,k,X[N],Y[N],fa[N],siz[N],a[N];
long long sum=1;
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
struct fac{
    long long a,b;
    inline bool operator<(const fac c)const{
        return a*c.b<b*c.a;
    }
    inline fac operator*(fac c){
        fac g={a*c.a,b*c.b};
        long long now=__gcd(g.a,g.b);
        assert(now);
        return{g.a/now,g.b/now};
    }
};
inline fac operator-(long long x,fac a){
    fac g={x*a.b-a.a,a.b};
    long long now=__gcd(g.a,g.b);
    return{g.a/now,g.b/now};
}
map<vector<int>,fac>f;
inline fac dfs(int pos,vector<int>v){
    // cerr<<pos<<' '<<v[1]<<' '<<v[2]<<' '<<v[3]<<endl;
    if(pos==n+1)return {0,1};
    if(f.count(v))return f[v];
    f[v].a=-1,f[v].b=1;
    vector<int>t=v;
    for(int i = 1;i<=n;++i){
        if(!v[i])continue;
        t[i]--;
        f[v]=max(f[v],(fac){2,i}*((1ll<<n+1-pos)-dfs(pos+1,t)));
        for(int j = i;j<=n;j++){
            if(!t[j])continue;
            t[j]--;t[i+j]++;
            f[v]=max(f[v],(fac){i+j,i*j}*((1ll<<n+1-pos)-dfs(pos+1,t)));
            t[j]++;t[i+j]--;
        }
        t[i]++;
    }
    // cerr<<pos<<' '<<v[0]<<' '<<v[1]<<' '<<f[v].a<<' '<<f[v].b<<endl;
    return f[v];
}
int main(){
    n=read(),k=read();
    long long ans = 0;
    for(int i = 1;i<=n;++i)fa[i]=i,siz[i]=1;
    vector<int>v(n+1);
    for(int i = 1;i<=k;i++){
        X[i]=find(read()),Y[i]=find(read());
        if(X[i]==Y[i]){
            a[X[i]]++;
            if(a[X[i]]>siz[X[i]]){
                if(i%2==0)ans+=sum*(1ll<<n+1-i+1);
                printf("%lld %lld\n",ans,(1ll<<n+1)-ans);return 0;
            }
            if(i%2==0)ans+=(1ll<<n+1-i+1)*sum/siz[X[i]]*(siz[X[i]]-1);
            sum/=siz[X[i]];sum*=2;
        }
        else{
            if(a[X[i]]==siz[X[i]]&&a[Y[i]]==siz[Y[i]]){
                if(i%2==0)ans+=sum*(1ll<<n+1-i+1);
                printf("%lld %lld\n",ans,(1ll<<n+1)-ans);return 0;
            }
            if(siz[X[i]]>a[X[i]]){
                if(i%2==0)ans+=(1ll<<n+1-i)*(sum/siz[X[i]]*(siz[X[i]]-1));
            }
            else{
                if(i%2==0)ans+=(1ll<<n+1-i)*sum;
            }
            if(siz[Y[i]]>a[Y[i]]){
                if(i%2==0)ans+=(1ll<<n+1-i)*(sum/siz[Y[i]]*(siz[Y[i]]-1));
            }
            else{
                if(i%2==0)ans+=(1ll<<n+1-i)*sum;
            }
            if(siz[X[i]]>a[X[i]])sum/=siz[X[i]];
            else sum/=2;
            if(siz[Y[i]]>a[Y[i]])sum/=siz[Y[i]];
            else sum/=2;
            fa[X[i]]=Y[i],siz[Y[i]]+=siz[X[i]];a[Y[i]]+=a[X[i]]+1;
            if(siz[Y[i]]>a[Y[i]])sum*=siz[Y[i]];
            else sum*=2;
        }
    }
    // cout<<ans<<endl;
    for(int i = 1;i<=n;i++)if(fa[i]==i&&siz[i]>a[i])v[siz[i]]++;
    auto[x,y]=dfs(k+1,v);
    if((k+1)&1)ans+=sum*x/y;
    else ans+=sum*(1ll<<n+1-k) - sum*x/y;
    printf("%lld %lld\n",ans,(1ll<<n+1)-ans);   
    return 0;
}