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

· · 题解

先考虑 k=n+1 的情况。

游戏在第 i 轮结束的方案数可以差分，即游戏在 i-1 轮没有结束的方案数 - 游戏在 i 轮没有结束的方案数。于是我们考虑计算游戏在前 i 轮后还没有结束的方案数，也即要求前 i 轮选出的 c_j 互不相同。

我们转化一下问题。现在对于每个人选的 (a_i,b_i) 建一条无向边。克莱尔要做的就是将无向边定向，a_i\to b_i 表示选择 b_i，如果游戏没有结束，则意味着没有任何一个点的入度\ge 2，也就是一个数出现了 2 次。

如果游戏前 i 轮游戏还没有结束，则 (a_j,b_j),j=1,\cdots,i 这 i 条边构成的图中的每个连通块只有以下两种可能：

否则，无论怎么定向，游戏一定会在前 i 轮结束。

并查集维护每个连通块的大小和环的个数即可。

现在我们考虑 k<n+1 的情况。

直接爆搜每一步选择 (a_i,b_i) 的方案。注意到获胜方案数只与【树的大小的集合 S】和【基环树的个数 t】有关，于是将【树的大小的集合 S】和【基环树的个数 t】记忆化。

不同的【树的大小的集合】的数量是 n 的可重整数划分级别的，35 的可重整数划分数大约是 1.5\times 10^4，所以状态数不是很大。

每一步有三种策略：

#include <bits/stdc++.h>
using namespace std;
const int N=40;
int n,k;
int fa[N],sz[N],edge[N];
inline int find_fa(int x){return fa[x]==x?x:fa[x]=find_fa(fa[x]);}
#define ull unsigned long long
#define ll long long
const ull base=233;
#define vec vector<int>
inline ull Hash(vec v,int cnt){
    ull ret=0;
    for(int x:v)ret=ret*base+x;
    return ret*base+cnt;
}
inline ll calc(vec v,int cnt){
    ll ret=1;
    for(int x:v)ret=x*ret;
    return ret<<cnt;
}
unordered_map<ull,ll> mapp;
inline void Max(ll &a,ll b){if(a<b)a=b;}
ll dfs(int pos,vec v,int cnt){
    if(pos>n+1)return 0;
    ull hsh=Hash(v,cnt);
    if(mapp.count(hsh))return mapp[hsh];
    ll ret=0;
    vec nxt;
    for(int i=0;i<v.size();++i){
        if(i>0&&v[i]==v[i-1])continue;
        for(int j=i+1;j<v.size();++j){
            if(j!=i+1&&v[j]==v[j-1])continue;
            nxt=v;
            nxt.erase(nxt.begin()+i);
            nxt.erase(nxt.begin()+j-1);
            nxt.insert(lower_bound(nxt.begin(),nxt.end(),v[i]+v[j]),v[i]+v[j]);
            Max(ret,calc(nxt,cnt-1)-dfs(pos+1,nxt,cnt-1));//树连树 
        }
        nxt=v;
        nxt.erase(nxt.begin()+i);
        if(cnt>=1)Max(ret,calc(nxt,cnt-1)-dfs(pos+1,nxt,cnt-1));//基环树连树 
        Max(ret,calc(nxt,cnt)-dfs(pos+1,nxt,cnt));//树变基环树 
    }
    return mapp[hsh]=ret;
}
ll tot,ans1,ans2,f[N];
bool flag=1;
int main(){
    scanf("%d %d",&n,&k);
    tot=1ll<<(n+1);
    for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1,edge[i]=0;
    f[0]=tot;
    for(int i=1,a,b;i<=k;++i){
        scanf("%d %d",&a,&b);
        int fx=find_fa(a),fy=find_fa(b);
        if(fx!=fy){
            fa[fx]=fy;sz[fy]+=sz[fx];edge[fy]+=edge[fx];
        }
        ++edge[fy];
        f[i]=1ll<<(n+1-i);
        for(int j=1;j<=n;++j){
            if(fa[j]==j){
                if(edge[j]>sz[j]){
                    flag=0;f[i]=0;break;
                }else if(edge[j]==sz[j])
                    f[i]<<=1;
                else f[i]*=sz[j];
            }
        }
        if(!(i&1))ans1+=f[i-1]-f[i];
        else ans2+=f[i-1]-f[i];
    }
    if(!flag)printf("%lld %lld\n",ans1,tot-ans1);
    else{
        vec v;
        int cnt=n+1-k;
        for(int i=1;i<=n;++i)
            if(fa[i]==i){
                if(edge[i]==sz[i])++cnt;
                else v.push_back(sz[i]);
            }
        sort(v.begin(),v.end());
        if(!(k&1))ans1+=dfs(k+1,v,cnt),printf("%lld %lld\n",ans1,tot-ans1);
        else ans2+=dfs(k+1,v,cnt),printf("%lld %lld\n",tot-ans2,ans2);
    }
    return 0;
}