自动搬运

查看原文

来自洛谷，原作者为

	harryzhr AFO

搬运于2025-08-24 22:47:17，当前版本为作者最后更新于2025-08-05 17:03:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑 $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$ 条边构成的图中的每个连通块只有以下两种可能：

• 一棵树，有 $|T|$ 种定向方法，即以每一个点为根的外向树
• 一棵基环树，有 $2$ 种定向方法，即环上任意定向，环外为外向树。

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

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

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

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

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

每一步有三种策略：

• 选择两个 $S$ 中的树，合并成一个树；
• 选择一个 $S$ 中的树，在这个树上加一条边变成一个基环树，基环树数量 $+1$；
• 选择一个 $S$ 中的树，和基环树相连，变成一个新的基环树，基环树数量不变。

#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;
}