Blog Detail

C20250053's blog
省集笔记（4.14~4.18）
C20250053 LV 9 @ 2026-6-7 11:55:49

依旧不放题面，分两次发。

4.14

A

考场上只会树的部分分，对于树的情况，我们自底向上贪心，假设我们当前处理到 $u$ 的子树。

此时如果 $u$ 是关键点，那么下面延伸到 $u$ 的路径全部都能和 $u$ 匹配，然后 $u$ 再继续向上延伸。

否则我们把延伸到 $u$ 的路径两两匹配，如果有落单的那么继续向上延伸。

获得 24pts。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e5 + 10;

int n,m;
char s[MAXN];
vector<int>G[MAXN];

namespace Solve1{
	int L[MAXN],R[MAXN],idx=0;
	int dep[MAXN],f[20][MAXN],id[MAXN];
	vector<PII>Ans;
	int lca(int x,int y){
		if(dep[x]<dep[y]) swap(x,y);
		FR(i,19,0)
			if(dep[f[i][x]]>=dep[y]) x=f[i][x];
		if(x==y) return x;
		FR(i,19,0)
			if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
		return f[0][x];
	}
	void dfs(int u,int fth){
		L[u]=++idx;
		dep[u]=dep[fth]+1,f[0][u]=fth;
		FL(i,1,19) f[i][u]=f[i-1][f[i-1][u]];
		id[u]=-1;
		if(s[u]=='1'){
			for(int v:G[u]){
				if(v==fth) continue;
				dfs(v,u);
				if(id[v]!=-1) Ans.push_back({id[v],u});
			}
			id[u]=u;
		}
		else{
			for(int v:G[u]){
				if(v==fth) continue;
				dfs(v,u);
				if(id[v]!=-1){
					if(id[u]==-1) id[u]=id[v];
					else Ans.push_back({id[v],id[u]}),id[u]=-1;
				}
			}
		}
		R[u]=idx;
	}
	void Get_pth(int u,int v){
		int t=lca(u,v);
		vector<int>V1,V2;
		while(u!=t) V1.push_back(u),u=f[0][u];
		V1.push_back(t);
		while(v!=t) V2.push_back(v),v=f[0][v];
		reverse(V2.begin(),V2.end());
		printf("%d ",(int)V1.size()+(int)V2.size());
		for(auto i:V1) printf("%d ",i);
		for(auto i:V2) printf("%d ",i);
		puts("");
	}
	void solve(){
		Ans.clear();
		int cnt=0;
		FL(i,1,n) cnt+=(s[i]=='1');
		idx=0,dfs(1,0);
		printf("%d 1\n",(int)Ans.size());
		for(auto i:Ans) Get_pth(i.first,i.second);
	}
}

int main(){
	freopen("signal.in","r",stdin);
	freopen("signal.out","w",stdout);
	int ID,Num;
	scanf("%d%d",&ID,&Num);
	while(Num--){
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		FL(i,1,n) G[i].clear();
		FL(i,1,m){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		if(ID==2){
			Solve1::solve();
			continue;
		}

	}
}

然后我们考虑在图上做这个事，首先如果一条边两个端点都是关键点那么我们直接选择它一定是不劣的。

我们发现处理图很麻烦，发现对于一条选择的路径，如果中间经过的节点有关键点，那么一定不优，因为我们可以从这个关键点将这条路径分裂成两条使得答案 $+1$ 。

于是我们会想到分开处理每个非关键点连通块，对于每个关键点，我们把它挂在和它有边相连的非关键点连通块上。

假设一个非关键点的连通块有 $C$ 个相邻的关键点，那么路径条数的理论上界是 $\lfloor\frac{C}{2}\rfloor$ ，这个是容易构造的。

具体地，我们找连通块的一棵 dfs 生成树，自底向上贪心，用横叉边调整度数，那么和树的部分分做法是一样的。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e5 + 10;

int n,m;
char s[MAXN];
vector<int>G[MAXN],P[MAXN];
vector<vector<int> >ans;
bool vis[MAXN]; 

void dfs(int u,int fth){
	vis[u]=1;
	for(int v:G[u]){
		if(v==fth||vis[v]) continue;
		dfs(v,u);
		if(!P[v].empty()) P[u].push_back(v);
	}
	while(P[u].size()>1){
		vector<int>L,R;
		int nw=P[u].back();
		P[u].pop_back();
		while(1){
			L.push_back(nw);
			if(s[nw]=='1') break;
			nw=P[nw][0];
		}
		nw=P[u].back();
		P[u].pop_back();
		while(1){
			R.push_back(nw);
			if(s[nw]=='1') break;
			nw=P[nw][0];
		}
		reverse(L.begin(),L.end());
		vector<int>res=L;
		res.push_back(u);
		res.insert(res.end(),R.begin(),R.end());
		ans.push_back(res);
	}
}

int main(){
	freopen("signal.in","r",stdin);
	freopen("signal.out","w",stdout);
	int ID,Num;
	scanf("%d%d",&ID,&Num);
	while(Num--){
		scanf("%d%d",&n,&m),ans.clear();
		FL(i,1,n) vis[i]=0,G[i].clear(),P[i].clear();
		scanf("%s",s+1);
		FL(i,1,m){
			int u,v;
			scanf("%d%d",&u,&v);
			if(s[u]=='1'&&s[v]=='1') ans.push_back({u,v});
			else if(s[u]=='1'||s[v]=='1'){
				if(s[v]=='1') swap(u,v);
				P[v].push_back(u);
			}
			else G[u].push_back(v),G[v].push_back(u);
		}
		FL(i,1,n)
			if(!vis[i]&&s[i]=='0') dfs(i,0);
		printf("%d 1\n",(int)ans.size());
		for(auto i:ans){
			printf("%d ",(int)i.size()); 
			for(auto j:i) printf("%d ",j);
			puts("");
		}
	}
}

B

原题 QOJ13069

我们发现我们并不关心具体的数值，我们只关心两种数的数量：前面的询问均正确时可能成为答案的数，前面的询问错了一次时可能成为答案的数，记录这两个数量作为状态，发现正好是题目的 $f$ 的定义。

我们应该写一个对 $f$ 打表的程序，我们枚举选了 $x$ 个一类数， $y$ 个二类数进行询问，询问答案是“是”/“否”分别转移到的状态。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e2 + 10;
const int inf = 0x3f3f3f3f; 

int f[MAXN][MAXN];

int dfs(int u,int v){
	if(u+v<=1) return 0;
	if(f[u][v]!=-1) return f[u][v];
	int res=inf;
	FL(x,0,u){
		FL(y,0,v){
			if((!x&&!y)||(x==u&&y==v)) continue;
			res=min(res,max(dfs(x,(u-x)+y),dfs(u-x,x+(v-y)))+1);
		}
	}
	return f[u][v]=res;
} 

int main(){
	memset(f,-1,sizeof(f));
	int lim=20;
	FL(u,0,lim)
		FL(v,0,lim)
			printf("%d%c",dfs(u,v),(v==lim?'\n':' '));
}

你会打出这样一个表：

0 0 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6
0 2 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6
3 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

发现：

$ans=0$ ， $(u,v)=(0,0\sim 1),(1,0)$ 。
$ans=1$ ， $(u,v)=(0,2)$ 。
$ans=2$ ， $(u,v)=(0,3\sim 4),(1,1)$ 。
$ans=3$ ， $(u,v)=(0,5\sim 8),(1,2\sim 4),(2,0)$ 。
$ans=4$ ， $(u,v)=(0,9\sim 16),(1,5\sim 11),(2,1\sim 6)$ （貌似这里应该有 $(3,0\sim 1)$ 但是没有所以我们拟合一下？记录 $mx_k$ 表示 $f_{u,0}\le k$ 时 $u$ 的最大值用于修正答案，也就是取个前缀最大值，有 $mx_0=mx_1=mx_2=1,mx_3=mx_4=2,mx_5=4$ ，观察发现对于 $k\ge 3$ ， $mx_k$ 为 $\le \lfloor\frac{2^k}{k+1}\rfloor$ 的最大偶数）。
$ans=5$ ，$(u,v)=(0,17\sim 32),(1,12\sim 26),(2,7\sim 20),(3,0\sim 14),(4,0\sim 8)$（这里按公式应该有 $(5,0\sim 2)$ ，所以拟合一下）。

然后我们会发现对于 $f(u,v)\le k$ ，需要满足 $u\le mx_k\land (k+1)u+v\le 2^{k}$ 。

于是我们令 $S_k=\{(u,v)|f(u,v)=k\}$ ，对于每个询问，我们把它拆成前缀相减。

于是对于矩阵 $Z=[0,u]\times [0,v]$ ，答案就是 $ans=\sum_k k\cdot |Z\cap S_k|$ ，然后发现乘 $k$ 很麻烦于是考虑变成 $\sum_{k\ge0}|Z\cap S_{>k}|$ 。

枚举 $k$ ，

考虑 $x>r=\min(u,mx_k)$ ，那么 $y$ 取 $[0,v]$ 中的任意值 $f$ 都是 $>k$ 的，所以这样的 $(x,y)$ 的数量是 $(u-r)\times (v+1)$ 。

然后是 $x\le r$ ，我们要统计满足 $y> 2^{k}-(k+1)x$ 的 $y$ 的个数，因为 $y$ 最大是 $v$ ，所以 $x$ 的下界是 $l=\max(0,\lceil\frac{2^k-v}{k+1}\rceil)$ 。

而对于确定的 $x$ ，满足条件的 $y$ 的数量是关于 $x$ 的一次函数 $(v+1)-(2^k-(k+1)x+1)=v-2^k+(k+1)x$ 。

对 $x\in [l,r]$ 等差数列求和：

\frac{(2v-2\cdot 2^{k}+(k+1)(l+r))(r-l+1)}{2}

时间复杂度 $\mathcal{O}(q\log V)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define PII pair<int,int>
using namespace std;
const int MR = 60 + 5;

int q;
ll mx[MR];

ull F(ll u,ll v){
	if(u<0||v<0) return 0;
	ull res=0;
	FL(k,0,60){
		ll l=max(0ll,(((1ll<<k)-v)+k)/(k+1)),r=min(u,mx[k]);
		res+=(ull)(u-r)*(v+1);
		if(l<=r){
			ull t=(v-(1ll<<k))*2+(k+1)*(l+r);
			res+=(i128)(r-l+1)*t/2;
		}
	}
	return res;
}

int main(){
	freopen("puzzle.in","r",stdin);
	freopen("puzzle.out","w",stdout);
	scanf("%d",&q);
	mx[0]=mx[1]=mx[2]=1;
	FL(k,3,60) mx[k]=(1ll<<k-1)/(k+1)*2;
	while(q--){
		ll l0,r0,l1,r1;
		scanf("%lld%lld%lld%lld",&l0,&r0,&l1,&r1);
		printf("%llu\n",F(r0,r1)-F(r0,l1-1)-F(l0-1,r1)+F(l0-1,l1-1));
	}
}

C

原题 QOJ10103

首先你可以用 next_permutation 获得 7pts。

然后考虑 $K=0$ 的时候。

首先如果 $\max\{A\}\not =\max\{B\}$ ，那么肯定是最大值大的一边赢，因为没有人可以把最大值弹出。

否则如果最大值个数不相等那么一定是最大值多的一边胜利。

那我们考虑最大值相等且个数相同的情况，我们不妨假设最大值为 $mx$ 。

那么配对的最大值会把序列分成若干段，我们发现除了最后一段之外，其他段的填数不会影响答案。

（我们保证最大值为 $mx$ ，所以所有 $<mx$ 的数在和作为分界点的 $mx$ 比较时会被弹出，不会影响答案）。

所以问题递归为子问题，比较最后一段中 $mx-1$ 的数量。

所以我们可以从大到小枚举 $mx$ ，此时 $>mx$ 的数已经全部填完且平局了，然后我们枚举 $mx$ 的填法。

我们枚举 $A,B$ 集合在最后一段放置的 $mx$ 的数量 $j,k$ ，那么相当于我们把 $cnt_{A,mx}-j/cnt_{B,mx}-k$ 个数分别分到 $sum_A/sum_B$ 段里，且每段可以为空。

如果 $j>k$ 那么 $A$ 集合胜利， $j<k$ 那么 $B$ 集合胜利，否则继续递归，获得 17pts。

25pts 代码：

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e3 + 10;
const int mod = 998244353;

int n,m,K;

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

namespace Solve1{
	int a[MAXN],b[MAXN];
	void solve(){
		FL(i,1,n) scanf("%d",&a[i]);
		FL(i,1,K) a[n+i]=0;
		n+=K;
		FL(i,1,m) scanf("%d",&b[i]);
		sort(a+1,a+n+1);
		sort(b+1,b+m+1);
		int cnt=0,cntW=0,cntD=0,cntL=0;
		do{
			do{
				cnt++;
				int pa=1,pb=1;
				while(pa<=n&&pb<=m){
					if(!a[pa]||a[pa]==b[pb]) pa++,pb++;
					else if(a[pa]<b[pb]) pa++;
					else pb++;
				}
				if(pa>n&&pb>m) cntD++;
				else if(pa>n) cntL++;
				else cntW++;
			}while(next_permutation(b+1,b+m+1));
		}while(next_permutation(a+1,a+n+1));
		printf("%d\n%d\n%d\n",1ll*cntW*qpow(cnt,mod-2)%mod,1ll*cntL*qpow(cnt,mod-2)%mod,1ll*cntD*qpow(cnt,mod-2)%mod);
	}
}

namespace Solve2{
	int cnta[MAXN<<1],cntb[MAXN<<1];
	int C[MAXN<<1][MAXN<<1];
	void solve(){
		FL(i,0,n+m){
			C[i][0]=C[i][i]=1;
			FL(j,1,i-1) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
		FL(i,1,n){
			int x;
			scanf("%d",&x);
			cnta[x]++;
		}
		FL(i,1,m){
			int x;
			scanf("%d",&x);
			cntb[x]++;
		}
		int suma=0,sumb=0;
		int ansW=0,ansL=0,ansD=1;
		FR(i,n+m,1){
			int tot=1ll*C[suma+cnta[i]][suma]*C[sumb+cntb[i]][sumb]%mod;
			ansD=1ll*ansD*qpow(tot,mod-2)%mod;
			int cntW=0,cntL=0,cntD=0;
			FL(j,0,cnta[i]){
				FL(k,0,cntb[i]){
					int val=1ll*(suma-1+cnta[i]-j<0?1:C[suma-1+cnta[i]-j][cnta[i]-j])*(sumb-1+cntb[i]-k<0?1:C[sumb-1+cntb[i]-k][cntb[i]-k])%mod;
					if(j>k) cntW=(cntW+val)%mod;
					else if(j<k) cntL=(cntL+val)%mod; 
					else cntD=(cntD+val)%mod;
				}
			}
			ansW=(ansW+1ll*ansD*cntW%mod)%mod;
			ansL=(ansL+1ll*ansD*cntL%mod)%mod;
			ansD=1ll*ansD*cntD%mod;
			suma+=cnta[i],sumb+=cntb[i]; 
		}
		printf("%d\n%d\n%d\n",ansW,ansL,ansD);
	}
}

int main(){
	freopen("eon.in","r",stdin);
	freopen("eon.out","w",stdout);
	scanf("%d%d%d",&n,&m,&K);
	if(n+K<=7&&m<=7) Solve1::solve(),exit(0);
	if(!K) Solve2::solve();
}

我们发现 $A$ 胜利的情况比较复杂，因为可能有炸弹没有被弹出。

但是 $B$ 胜利的情况是简单的，因为所有炸弹都被触发，所以我们计算 $B$ 胜利的方案数和平局方案数。

我们同样考虑从大到小插入权值 $v$ 。

在处理权值 $v$ 之前，所有 $>v$ 的数都已经插入，令 $sum_A/sum_B$ 表示 $A/B$ 集合 $>v$ 的数的数量。

此时炸弹相关的段有几类，也就是 $A$ 集合中以炸弹结尾， $B$ 集合中以数结尾的两段的匹配：

$(\times ,?)$ ：表示这个炸弹以后会炸掉 $B$ 集合中的一个数，但还没有确定。
空的 $(\times ,>v)$ ：这个炸弹决定炸掉 $B$ 集合中 $>v$ 的一个数，但是在炸弹前还没有放置 $A$ 集合的数。
非空的 $(\times ,>v)$ ：这个炸弹决定炸掉 $B$ 集合中 $>v$ 的一个数且炸弹前已放置 $A$ 集合的数，此时一定能匹配到目标因为接下来放置的都是 $\le v$ 的数。

显然这三类的总数为 $K$ ，设计 dp 状态，令 $f_{x,y,op}$ 表示空的 $(\times ,>v)$ 有 $x$ 对，非空的 $(\times ,>v)$ 有 $y$ 对， $(\times ,?)$ 有 $z=K-x-y$ 对， $op=0/1$ 表示当前最后一段是平局/ $B$ 胜利时的方案数。

我们称可能影响炸弹触发以及输赢的段为限制段。

我们枚举输赢状态的变化量 $\Delta$ ，显然 $op=0$ 可以转移到 $0/1$ ， $op=1$ 只能保持 $1$ ，于是 $\Delta\in [0,1-[op=1]]$ ，也就是是否消耗一个 $B$ 的 $v$ 使得最后一段从平局变成 $B$ 胜利，然后枚举 $i\in [0,\min(x,cnt_{A,v})],j\in [0,\min(z,cnt_{B,v}-[\Delta=1])],k\in [0,\min(cnt_{A,v}-i,cnt_{B,v}-j-[\Delta=1])]$，分别表示放在空的 $(\times ,>v)$ 之前使其变为非空的 $v$ 的数量，确定为 $(\times ,v)$ 的 $v$ 的数量，插入限制段的 $(v,v)$ 的数量。

（枚举 $k$ 是因为限制段不能单独插入 $v$ ）。

新状态为 $x'=x-i+j,y'=y+i,op'=op+\Delta$ 。

然后考虑转移系数。

我们从 $x$ 中选 $i$ 个，从 $z$ 中选 $j$ 个，然后 $k$ 对 $(v,v)$ 要放在限制段，每段可以为空，限制段有 $x+z+1-op$ （如果最后一段是平局那么单独放置 $v$ 仍旧会影响胜负，所以是限制段）。

然后 $A$ 剩下 $cnt_{A,v}-i-k$ 个 $v$ ，可以放入自由段，每段可以为空，自由段数量为 $sum_A+y'+op$ （ $y'$ 是新的非空段数量，显然本轮因为放了 $v$ 成为非空段的段也是可以放的， $op$ 是因为如果上轮 $B$ 已经赢了那么 $v$ 放进去不影响答案）。

$B$ 剩下 $cnt_{B,v}-j-k-\Delta$ 个 $v$ ，可以放入自由段，每段可以为空，自由段数量为 $sum_B-x+op'$ （ $op'$ 是因为如果本轮 $B$ 已经赢了那么 $v$ 放进去不影响答案）。

上述 $m$ 个数放入 $n$ 个段的系数均为 $\binom{n+m-1}{n-1}$ ，要特判 $m=0$ ，因为不放任何东西总会有一种方案。

因为计算的是方案数，所以我们还需要总方案数，也就是 $A$ 集合排列数乘上 $B$ 集合排列数：

$$\frac{(n+K)!}{K!\prod_vcnt_{A,v}!}\cdot\frac{m!}{\prod_vcnt_{B,v}!}$$

方案数除以总方案数就是概率了。

时间复杂度 $\mathcal{O}((n+m)K^4)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 4e3 + 10;
const int MAXK = 20 + 5; 
const int mod = 998244353;

int n,m,K;
int ansW,ansL,ansD;
int cnta[MAXN],cntb[MAXN];
int fac[MAXN],invf[MAXN],inv[MAXN];
int f[MAXK][MAXK][2],g[MAXK][MAXK][2];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1; 
	}
	return res;
}
int C(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return 1ll*fac[n]*invf[m]%mod*invf[n-m]%mod; 
}
int Ch(int n,int m){
	if(!m) return 1;
	return C(n+m-1,n-1);
}

int main(){
	freopen("eon.in","r",stdin);
	freopen("eon.out","w",stdout);
	scanf("%d%d%d",&n,&m,&K);
	fac[0]=1;
	FL(i,1,MAXN-1) fac[i]=1ll*fac[i-1]*i%mod;
	invf[MAXN-1]=qpow(fac[MAXN-1],mod-2);
	FR(i,MAXN-2,0) invf[i]=1ll*invf[i+1]*(i+1)%mod;
	inv[0]=inv[1]=1;
	FL(i,2,MAXN-1) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	f[0][0][0]=1;
	FL(i,1,n){
		int x;
		scanf("%d",&x);
		cnta[x]++;
	}
	FL(i,1,m){
		int x;
		scanf("%d",&x);
		cntb[x]++;
	}
	int suma=0,sumb=0;
	int Mul=1ll*fac[n+K]*fac[m]%mod*invf[K]%mod;
	FR(V,n+m,1){
		memset(g,0,sizeof(g));
		Mul=1ll*Mul*invf[cnta[V]]%mod*invf[cntb[V]]%mod;
		FL(x,0,K) FL(y,0,K-x) FL(op,0,1) g[x][y][op]=0;
		FL(x,0,K){
			FL(y,0,K-x){
				int z=K-x-y; 
				FL(op1,0,1){
					if(!f[x][y][op1]) continue;
					FL(op2,0,1-op1){
						FL(i,0,min(x,cnta[V])){
							FL(j,0,min(z,cntb[V]-op2)){
								int sum=0;
								FL(k,0,min(cnta[V]-i,cntb[V]-j-op2))
									sum=(sum+1ll*Ch(suma+y+i+op1,cnta[V]-i-k)*Ch(sumb-x+op1+op2,cntb[V]-j-k-op2)%mod*Ch(x+z+1-op1,k)%mod)%mod;
								g[x-i+j][y+i][op1+op2]=(g[x-i+j][y+i][op1+op2]+1ll*sum*C(x,i)*C(z,j)%mod*f[x][y][op1]%mod)%mod;
							}
						}
					}
				}
			}
		}
		FL(x,0,K) FL(y,0,K-x) FL(op,0,1) f[x][y][op]=g[x][y][op];
		suma+=cnta[V],sumb+=cntb[V]; 
	}
	FL(i,0,K) ansL=(ansL+f[i][K-i][1])%mod,ansD=(ansD+f[i][K-i][0])%mod;
	Mul=qpow(Mul,mod-2),ansL=1ll*Mul*ansL%mod,ansD=1ll*Mul*ansD%mod,ansW=((1-ansL-ansD)%mod+mod)%mod;
	printf("%d\n%d\n%d\n",ansW,ansL,ansD);
}

4.15

A

原题 P15721

只能说太神秘我居然场上能过 T1。

考虑最后一次合并，就是你会发现这棵树一定能够从一条边被割开，变成两个连通块，

并且有分界点 $k$ ，使得一个连通块是 $1\sim k$ ，合并到 $k$ ，另一个连通块是 $k+1\sim n$ ，合并到 $k+1$ 。

我们枚举这条边，此时以这条边的两个端点为根形成了两棵子树。

以连通块 $\{1,2,\cdots,k\}$ 为例，我们发现，每次合并的方向都是唯一的， $1\to 2,2\to 3,\cdots,k-1\to k$ ，所以要求所有 $\forall k'\le k$ ，所有权值 $\le k'$ 的点必须形成连通块，也就等价于，叶子到根的路径上，权值要递增。

放到权值从小到大的排列上面，就是父亲要比儿子后出现。

就相当于你要求连通块中以每个节点为根的合法拓扑序数量，合法拓扑序的公式是：

\frac{n!}{\prod siz_u}

然后你做一下换根 dp 就能求出在一个连通块内，以每个点为根的合法拓扑序数量的和。

然后剩下一些需要去重的方案，也就是对于一条长链连接两个连通块的情况，断掉链上任意一条边的操作方案都是合法的。

换句话说，这种染色方案在多种操作方案中合法，但是我们只希望计算一次，所以我们减去。

时间复杂度 $\mathcal{O}(n^2)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 3e3 + 10;
const int mod = 998244353;

int n;
ll ans=0; 
int siz[MAXN];
ll fac[MAXN],inv[MAXN];
vector<int>G[MAXN];
vector<int>Val[MAXN];
vector<int>V;

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

void dfs1(int u,int fth,int id){
	siz[u]=1;
	V.push_back(u);
	for(int v:G[u]){
		if(v==fth||v==id) continue;
		dfs1(v,u,id);
		siz[u]+=siz[v];
	}
}
int K,sum=0;
void dfs2(int u,int fth,int id,int nw){
	sum=(sum+nw)%mod;
	for(int v:G[u]){
		if(v==fth||v==id) continue;
		dfs2(v,u,id,1ll*nw*siz[v]%mod*inv[K-siz[v]]%mod);
	}
}
int Calc(int u,int id){
	V.clear();
	dfs1(u,0,id);
	K=(int)V.size();
	int nw=1;
	for(auto i:V) nw=1ll*nw*siz[i]%mod;
	sum=0,dfs2(u,0,id,qpow(nw,mod-2));
	return 1ll*fac[K]*sum%mod;
}

int Get_val(int v,int u){
	for(int i=0;i<(int)G[u].size();i++)
		if(G[u][i]==v) return Val[u][i];
	assert(0);
}

int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	scanf("%d",&n);
	if(n==1) puts("1"),exit(0);
	fac[0]=1;
	FL(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;
	inv[0]=inv[1]=1;
	FL(i,2,n)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	FL(i,1,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	FL(u,1,n)
		for(int v:G[u])
			Val[u].push_back(Calc(v,u));
	FL(u,1,n)
		for(int v:G[u])
			if(u<v)
				ans=(ans+1ll*Get_val(v,u)*Get_val(u,v)%mod)%mod;
	FL(u,1,n){
		if(G[u].size()==2){
			int v1=G[u][0],v2=G[u][1];
			ans=(ans-1ll*Get_val(v1,u)*Get_val(v2,u)%mod+mod)%mod;			
		}
	}
	printf("%lld\n",2ll*ans%mod);
}

B

显然对于 $x,y$ 我们只需要考虑他们之间的简单路径上的点，设路径长度为 $m$ 。

我们发现距离路径端点距离至少为 $k$ 的点到达的时刻 $\ge k$ ，令 $d_k$ 表示路径上第 $k$ 个点最近的黑点到这个点的距离，那么这个点是可用的必要条件是 $d_k \ge \min(k,m-k)$ 。

我们不妨设子树内没有关键节点的点 $x$ 的 $d_x=\infty$ ，那么 $\not=\infty$ 的 $d_x$ 的和是 $\mathcal{O}(n)$ 的（因为 $d_x=k$ 说明 $x$ 的分支上至少有 $k$ 个节点）。

因为有效的 $d_x$ 是递增的（ $\ge k$ ）所以 $\not=\infty$ 的 $d_x$ 最多有 $\mathcal{O}(\sqrt{n})$ 个。

我们考虑把这些 $d_x$ 拉出来，显然我们肯定是先选择让一边走到全局最小值然后递归另一边进行解决。

于是我们可以对所有点建出最小值的笛卡尔树，然后在树上进行 dp，于是我们得到了一个单组 $\mathcal{O}(n)$ 的解法。

时间复杂度 $\mathcal{O}(qn)$ 。

然后我们考虑如何把找出这 $\mathcal{O}(\sqrt{n})$ 个有黑点可以到达的点。

因为路径是在树上所以考虑树链剖分。

我们用两棵线段树分别维护 $x$ 子树内/子树外的点到 $x$ 的最短距离。

$x$ 子树在 dfn 序上是一段连续的区间 $[L_x,R_x]$ ，这个可以直接查询，然后对于 $x$ 的祖先 $u$ ，我们预处理 $[u,x]$ 这段区间中所有轻子树中的黑点到重链上的点的最短距离，挂在一棵线段树上，维护 $d_u-dep_u$ 。

我们可以对于所有的黑点维护一个 set，按 dfn 序排序，然后对重链的顶端 $top_u$ 进行 lower_bound（重链上是 $u$ 的祖先的点的 dfn 序 $<dfn_u$ ），然后我们不断向后访问直到黑点的 dfn 序 $\ge dfn_u$ ，于是我们可以找出所有的黑点，这个是 $\mathcal{O}(\log n +k)$ 的。

（这个也可以用树状数组上二分 + 链表实现）

所以这部分的时间复杂度是 $\mathcal{O}(n\log^2 n)$ 的。

于是我们找出了这 $\mathcal{O}(\sqrt{n})$ 个点，得到了 $\mathcal{O}(\sqrt{n})$ 个形如 $(t_p,d_p)$ 的点对，其中 $t_p$ 是 $p$ 在 $(x,y)$ 这条简单路径上的坐标。

我们考虑我们什么时候可以在 $(a,a+1)$ 相遇。

此时 $p\le a$ 的点一定是左棋子走到的， $p>a$ 的点一定是右棋子走到的，可以证明这样走一定最优，所以最小步数是固定的，我们处理限制。

具体地，我们按照 $d_x$ 从大到小处理，这样我们每次处理的都是限制最弱的点，

假设当前处理到点 $x$ ，前驱为 $pL$ ，后继为 $pR$ ，此时 $d_{pL},d_{pR}$ 均 $\le d_x$ 。

如果我们希望在边区间 $[pL,x)$ 相遇，那么限制是在 $d_x$ 时刻结束前，左棋子至少要走到 $p_{pL}$ ，右棋子至少要走到 $p_x$ ，因此在 $d_x$ 秒内至少要走 $p_{pL}+(m-p_x)$ 步，

若 $p_{pL}+(m-p_x)>d_x$ 那么我们不能在边区间 $[pL,x)$ 相遇。

同理有若 $p_x+(m-p_{pR})>d_x$ 那么我们不能在边区间 $[x,pR)$ 相遇。

这个可以用差分维护，那么如果存在一条边 $(a,a+1)$ 没有被覆盖，我们可以在这里相遇。

时间复杂度 $\mathcal{O}(q\log^2 n+q\sqrt{n})$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int n,q,Typ;
int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],top[MAXN];
int L[MAXN],R[MAXN],qid[MAXN],idx=0;
vector<int>G[MAXN];
int mnd[MAXN],nxt[MAXN];
bool us[MAXN],col[MAXN];

struct BIT{
	#define lowbit(x) (x&(-x))
	int c[MAXN];
	void update(int x,int k){
		while(x<=n){
			c[x]+=k;
			x+=lowbit(x);
		}
	}
	int query(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
	int find(int rk){
		int x=0;
		for(int k=(1<<17);k;k>>=1)
			if(x+k<=n&&rk>c[x+k])
				rk-=c[x+k],x+=k;
		return x+1;
	}
}T;

struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	struct node{
		int l,r;
		int mn;
	}t[MAXN<<2];
	void pushup(int x){
		t[x].mn=min(t[ls].mn,t[rs].mn);
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].mn=inf;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void update(int x,int p,int k){
		if(t[x].l==t[x].r){
			t[x].mn=k;
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		if(p<=mid) update(ls,p,k);
		else update(rs,p,k);
		pushup(x);
	}
	int query(int x,int l,int r){
		if(l>r) return inf; 
		if(l<=t[x].l&&t[x].r<=r) return t[x].mn;
		int mid=(t[x].l+t[x].r)>>1;
		if(r<=mid) return query(ls,l,r);
		else if(l>mid) return query(rs,l,r);
		else return min(query(ls,l,r),query(rs,l,r));
	}
}T1,T2;

int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return (dep[x]<dep[y]?x:y);
}
int Qry_d(int x){
	return T1.query(1,L[x],R[x]);	
} 
int Qry_d(int x,int y){
	return (!y?Qry_d(x):min(T1.query(1,L[x],L[y]-1),T1.query(1,R[y]+1,R[x])));
}
int Qry_d(int x,int y,int z){
	if(L[y]>L[z]) swap(y,z);
	return min({T1.query(1,L[x],L[y]-1),T1.query(1,R[y]+1,L[z]-1),T1.query(1,R[z]+1,R[x])});
}
int Up(int x,int tar){
	while(dep[top[x]]>tar) x=fa[top[x]];
	return qid[L[x]-(dep[x]-tar)];
}
int Qry_mn(int x){
	int mn=inf,u=x,las=x;
	x=fa[x];
	while(x){
		mn=min({mn,(Qry_d(x,las)-dep[x])-dep[x],T2.query(1,L[top[x]],L[x]-1)});
		las=top[x],x=fa[top[x]];
	}
	return mn+dep[u];
}
int Get_dis(int x,int y){
	return dep[x]+dep[y]-(dep[lca(x,y)]<<1); 
}

void dfs1(int u,int fth){
	dep[u]=dep[fth]+1,fa[u]=fth;
	siz[u]=1,son[u]=0;
	for(int v:G[u]){
		if(v==fth) continue;
		dfs1(v,u);
		if(siz[v]>siz[son[u]]) son[u]=v;
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	L[u]=++idx,qid[idx]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int v:G[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
	R[u]=idx;
}

void Upd(int x){
	while(x){
		mnd[x]=Qry_d(x,son[x]);
		T2.update(1,L[x],(mnd[x]-dep[x])-dep[x]);
		if(mnd[x]<=n&&!col[x]){
			int rk=T.query(L[x]),pL=qid[T.find(rk)],pR=qid[T.find(rk+1)];
			col[x]=1,nxt[pL]=x,nxt[x]=pR,T.update(L[x],1);
		}
		else if(mnd[x]>n&&col[x]){
			int rk=T.query(L[x]),pL=qid[T.find(rk-1)],pR=qid[T.find(rk+1)];
			col[x]=0,nxt[pL]=pR,T.update(L[x],-1);
		}
		x=fa[top[x]];
	}
}

int Mx=500,m,tot=0;
int p[MAXN],d[MAXN],s[MAXN];
int id[MAXN],Le[MAXN],Ri[MAXN];

bool Chk(int ps,int dis){
	if(dis<min(ps,m-ps)) return 0;
	if(dis<=m) tot++,p[tot]=ps,d[tot]=dis;
	return (tot<=Mx);
}
bool Work(int St,int Ed,bool Rev){
	int x=St,las=0,pr=tot;
	while(x!=Ed){
		if(!Chk(dep[St]-dep[x],las?Qry_d(x,las)-dep[x]:0)) return 0;
		int prv=tot;
		for(int y=qid[T.find(T.query((top[x]!=top[Ed]?L[top[x]]-1:L[Ed]))+1)];L[y]<L[x];y=nxt[y])
			if(!Chk(dep[St]-dep[y],mnd[y]-dep[y])) return 0;
		reverse(p+prv+1,p+tot+1),reverse(d+prv+1,d+tot+1);
		las=top[x],x=(top[x]!=top[Ed]?fa[top[x]]:Ed);
	}
	if(Rev){
		reverse(p+pr+1,p+tot+1),reverse(d+pr+1,d+tot+1);
		FL(i,pr+1,tot) p[i]=m-p[i];
	}
	return 1;
}

bool cmp(int p,int q){
	return d[p]>d[q];
}
bool Solve(int x,int y){
	tot=0;
	if(dep[x]<dep[y]) swap(x,y);
	int t=lca(x,y);
	m=Get_dis(x,y);
	if(!Work(x,t,0)) return 0;
	if(y==t) Chk(m,0);
	else if(!Chk(dep[x]-dep[t],min(Qry_d(t,Up(x,dep[t]+1),Up(y,dep[t]+1))-dep[t],Qry_mn(t)))) return 0;
	if(!Work(y,t,1)) return 0;
	FL(i,1,tot) id[i]=i,Le[i]=i-1,Ri[i]=i+1,s[i]=0;
	sort(id+1,id+tot+1,cmp);
	FL(i,1,tot-2){
		int x=id[i],pL=Le[x],pR=Ri[x];
		if(p[pL]+(m-p[x])>d[x]) s[pL]++,s[x]--;
		if(p[x]+(m-p[pR])>d[x]) s[x]++,s[pR]--;
		Ri[pL]=pR,Le[pR]=pL;
	}
	FL(i,2,tot-1) s[i]+=s[i-1]; 
	FL(i,1,tot-1) if(!s[i]) return 1;
	return 0;
}

int main(){
	freopen("meet.in","r",stdin);
	freopen("meet.out","w",stdout); 
	scanf("%d%d%d",&n,&q,&Typ);
	FL(i,1,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1,0),dfs2(1,1);
	T1.build(1,1,n),T2.build(1,1,n);
	FL(i,1,n)
		mnd[i]=Qry_d(i,son[i]),col[i]=(mnd[i]<=n),T.update(L[i],col[i]),T2.update(1,L[i],(mnd[i]-dep[i])-dep[i]);
	L[n+1]=qid[n+1]=n+1; 
	FL(i,1,n)
		if(col[i])
			nxt[i]=qid[T.find(T.query(L[i])+1)];
	int lastans=0;
	while(q--){
		int op,x,y;
		scanf("%d%d",&op,&x);
		if(op==1){
			if(Typ&&lastans) x=(x+lastans)%n+1;
			if(us[x]) us[x]=0,T1.update(1,L[x],inf);
			else us[x]=1,T1.update(1,L[x],dep[x]);
			Upd(x);
		}
		else{
			scanf("%d",&y);
			if(Typ&&lastans) x=(x+lastans)%n+1,y=(y+lastans)%n+1;
			if(Solve(x,y)) puts("Pig"),lastans=x;
			else puts("NPig"),lastans=y;
		}
	}
}

C

首先我们发现，如果有一种合法方案，在第一行放置的点数为 $s$ ，在第二行放置的点数为 $n-s$ ，那么最小答案 $m=\max(s,n-s)$ ，且只与点数有关。

（因为我们考虑如果我们已经成功放置这些点，且第一行有 $s$ 个，第二行有 $n-s$ 个，那我们此时将所有没有节点的空格删去，此时行内节点的相对顺序没有改变，不会影响边的相交关系）。

考虑哪些链是容易挂的，首先是直链，形如：

u-v_1-v_2-\cdots-v_k

此时如果我们将 $u$ 放在第一行，

那么我们可以把 $v_1\sim v_k$ ，放在 $u$ 的左侧/右侧，对第一行贡献 $k$ 。
也可以将 $v_1\sim v_t$ 放在第二行，然后把后缀 $v_{t+1}\sim v_k$ 折回第一行的最左端和最右端（这种情况只能在网格两端，因为如果放在左边/右边那么 $u$ 左边/右边无法连接其他的点）

所以直链对第一行的贡献可以是 $0\sim k$ 个点。

叉链：

$$\quad \quad \quad \quad \quad \quad \quad \quad \quad l_1-l_2-\cdots -l_{k_l}\\ \quad \quad |\\ rt-c\\ \quad \quad |\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad r_1-r_2-\cdots -r_{k_r}\\$$

不妨设 $k_l\le k_r$ ，若我们将 $rt$ 放在第一行，

那么我们可以把 $c$ 放在第二行， $l_1\sim l_{k_l}/r_1\sim r_{k_r}$ ，分别放在 $c$ 的左侧/右侧，对第一行贡献 $0$ 。
也可以将最多其中一条的后缀折回第一行，贡献 $0\sim l/0\sim r$ 个点。

还可以一条链放在第一行，另一条的后缀折回在第一行，贡献 $l+1\sim l+r$ 个点。

也就是这两种链都有在一行内放下的方法，所以我们先把它们全部去除，看剩下的骨架链能否在一行内放下，如果不行那么一定无解。

$f_{i,j,s}$ 表示用了 $i$ 个网格端点位置，用了 $j$ 个根旁边的位置，第一行有 $s$ 个点，是否有解。

$g_{x,y,s}$ 表示已经处理到某个位置，最近两个根的行号分别为 $x,y$ ，第一行有 $s$ 个点，是否有解。

用 bitset 维护一下即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 5e4 + 10;

int n,len=0,ans;
int a[MAXN];
int deg[MAXN],fa[MAXN],cntd[MAXN],cnt[MAXN],sum[MAXN];
bitset<MAXN>f[3][3],g[2][2],h[2][2];
vector<int>G[MAXN],st1[MAXN],st2[MAXN]; 
bool del[MAXN];

void dfs(int u,int fth){
	a[++len]=u;
	for(int v:G[u]){
		if(v==fth) continue;
		dfs(v,u);
	}
}

bitset<MAXN> Get(bitset<MAXN>f,int x){
	return (x>0?f<<x:f>>(-x)); 
}

int main(){
	freopen("draw.in","r",stdin);
	freopen("draw.out","w",stdout); 
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d",&n),len=0,ans=n;
		FL(i,1,n) G[i].clear(),st1[i].clear(),st2[i].clear(),deg[i]=fa[i]=cntd[i]=sum[i]=del[i]=0,cnt[i]=1; 
		FL(i,1,n-1){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
			deg[u]++,deg[v]++;
			fa[u]^=v,fa[v]^=u; 
		}
		if(*max_element(deg+1,deg+n+1)<3){
			printf("%d\n",(n+1)/2);
			continue;
		}
		queue<int>q;
		FL(i,1,n) if(deg[i]==1) q.push(i);
		while(!q.empty()){
			int u=q.front(),v=fa[u];
			q.pop();
			del[u]=1;
			deg[v]--,cntd[v]++,fa[v]^=u,cnt[v]+=cnt[u];
			if(deg[v]==1&&cntd[v]==1) q.push(v);
		}
		FL(u,1,n)
			if(!del[u]&&deg[u]==1&&cntd[u]==2)
				del[u]=1,G[u].erase(find(G[u].begin(),G[u].end(),fa[u]));
		if(!count(del+1,del+n+1,0)){
			printf("%d\n",(n+1)/2);
			continue;
		}
		bool fg=1;
		FL(u,1,n){
			if(del[u]) continue;
			vector<int>V;
			for(int v:G[u]){
				if(!del[v]) V.push_back(v);
				else if(cntd[v]<=1) st1[u].push_back(v),sum[u]+=cnt[v];
				else st2[u].push_back(v),sum[u]+=cnt[v];
			}
			if(V.size()>2){
				fg=0;
				break;
			}
			G[u].swap(V),sum[u]++;
		}
		if(!fg){
			puts("-1");
			continue;
		}
		FL(u,1,n)
			if(!del[u]&&G[u].size()<=1){dfs(u,0);break;}
		FL(i,0,2) FL(j,0,2) f[i][j].reset(),f[i][j].set(1);
		for(int id:st1[a[1]]){
			int x=cnt[id];
			FR(i,2,0){
				FR(j,2,0){
					if(j<2) f[i][j+1]|=Get(f[i][j],x);
					if(i<2){
						f[i+1][j]|=f[i][j];
						FL(y,1,x-1) f[i+1][j]|=Get(f[i][j],y);
					}
				}
			}
		}
		for(int id:st2[a[1]]){
			int l=cnt[G[id][0]],r=cnt[G[id][1]];
			if(l>r) swap(l,r);
			FR(i,1,0){
				bitset<MAXN>t=f[i][2];
				FL(y,1,r) t|=Get(f[i][2],y);
				f[i+1][2]|=t,f[i+1][2]|=(t<<l); 
			}
		}
		if(len==1){
			FL(i,1,n-1)
				if(f[2][2][i])
					ans=min(ans,max(i,n-i));
			printf("%d\n",ans);
			continue;
		}
		g[1][0]=f[1][2],g[1][1]=f[1][1];
		g[0][0].reset(),g[0][1].reset();
		FL(i,0,sum[a[1]])
			g[0][0][sum[a[1]]-i]=g[1][1][i],g[0][1][sum[a[1]]-i]=g[1][0][i];
		FL(ps,2,len-1){
			int u=a[ps];
			FL(i,0,1) FL(j,0,1) h[i][j].reset();
			bitset<MAXN>t,p,q;
			t=g[0][0]<<sum[u]-1,p=t;
			for(int id:st1[u]) p|=Get(t,-cnt[id]);
			h[0][0]|=t,h[0][1]|=p;
			t=g[1][0]<<sum[u]-1,p=q=t;
			for(int id:st1[u]) q|=Get(p,-cnt[id]),p|=Get(t,-cnt[id]);
			h[0][0]|=p,h[0][1]|=q;
			t=g[0][1]<<1,p=q=t;
			for(int id:st1[u]) q|=Get(p,cnt[id]),p|=Get(t,cnt[id]);
			h[1][0]|=q,h[1][1]|=p;
			t=g[1][1]<<1,p=t;
			for(int id:st1[u]) p|=Get(t,cnt[id]);
			h[1][0]|=p,h[1][1]|=t;
			FL(i,0,1) FL(j,0,1) g[i][j]=h[i][j];
		}
		g[0][1]<<=1,g[1][1]<<=1,g[1][1]|=g[0][1];
		f[0][0]=f[1][0]=g[0][1];
		f[0][1]=f[1][1]=f[0][2]=f[1][2]=g[1][1];
		for(int id:st1[a[len]]){
			int x=cnt[id];
			FR(i,1,0){
				FR(j,2,0){
					if(j<2) f[i][j+1]|=Get(f[i][j],x);
					if(i<1){
						f[i+1][j]|=f[i][j];
						FL(y,1,x-1) f[i+1][j]|=Get(f[i][j],y);
					}
				}
			}
		}
		for(int id:st2[a[len]]){
			int l=cnt[G[id][0]],r=cnt[G[id][1]];
			if(l>r) swap(l,r);
			bitset<MAXN>t=f[0][2];
			FL(y,1,r) t|=Get(f[0][2],y);
			f[1][2]|=t,f[1][2]|=(t<<l);
		}
		FL(i,1,n-1)
			if(f[1][2][i])
				ans=min(ans,max(i,n-i));
		printf("%d\n",ans);
	}
}

4.17

A

感觉是漏了一个结论导致的。

首先你会想到走两步，每次 $A$ 走 $1$ 步， $B$ 走 $2$ 步，然后当 $A,B$ 相遇时它们的相遇点一定在环上，不妨设走了 $k$ 步，则有 $k\ge p,q\mid k$ 。

然后你让 $A$ 一步步走直到和 $B$ 重合，这时的步数就是环长 $q$ 。

然后这时我考场上就把 $A,B$ 都移回起点并且让 $B$ 先走 $q$ 步，然后一步一步移 $A,B$ ，当 $A,B$ 第一次重合时步数就是链长 $p$ 。

然后你可以获得 83pts。

然后你研究一下你会发现因为 $k\ge p\land q\mid k$ ，所以第一次相遇的 $k$ 是不小于 $p$ 的最小的 $q$ 的倍数，也就是 $k=\lceil\frac{p}{q}\rceil\times q\le p+q-1$ 。

于是移项可以得到 $k-q<p\le k$ 。

于是你可以只把 $A$ 放回起点并让其走 $k-q$ 步，然后一步一步移 $A,B$ ，第一次重合时 $A$ 的步数就是链长 $p$ 。

（因为此时，它们的步数差恒为 $k-(k-q)=q$ ，所以 $A$ 一旦移动到环上它们就会相遇，此时就是链长 $p$ ）。

#include"meet.h" 
#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;

vector<int>solve(int N,int S){
	int k=0,p=0,q=0;
	while(1){
		move(0,1),move(1,1),k++;
		if(move(1,1)) break;
	} 
	while(1){
		q++;
		if(move(1,1)) break;
	}
	p=k-q;
	move(0,0);
	FL(i,1,p) move(0,1);
	while(1){
		move(0,1),p++;
		if(move(1,1)) break;
	}
	return {p,q};
}

B

就是你可以看出一些显然的网络流模型。

源点向 $m$ 个操作分别连容量为 $1$ 的边，第 $i$ 个操作向给定集合 $S_i$ 的所有元素连容量为 $1$ 的边。

然后我们枚举作为唯一的最大值的元素 $i$ ，假设它在所有 $S$ 中出现了 $exi_i$ 次，

我们肯定希望这些操作都选择 $i$ ，且其余节点被选择的次数严格小于 $exi_i$ 。对于 $j\not =i$ 的元素 $j$ ，我们向汇点连容量为 $exi_i-1$ 的边，对于元素 $i$ ，我们向汇点连容量为 $exi_i$ 的边，记这个流量为 $f_i$ ，则有 $f_x=exi_i-[x\not=i]$ 。

然后就是 $\mathcal{O}(n\cdot Dinic)$ 。

然后你观察 $exi_i$ 的大小和解是否合法的关系，你会发现 $exi_i$ 越大解越容易合法。

于是猜有合法阙值 $K$ ，

满足当我们令所有 $f_i=K-1$ 时的图 $G$ 最大流 $<m$ ，当我们令所有 $f_i=K$ 时的图 $G'$ 最大流 $=m$ 。

于是按照 $exi_i$ 从小到大排序，

对于 $exi_i<K$ 的 $i$ ，因为令所有 $f_i=K-1$ 的 $G$ 都不合法那么显然是不合法的。

对于 $exi_i>K$ 的 $i$ ，因为令所有 $f_i=K$ 的 $G'$ 都合法那么显然是合法的。

对于 $exi_i=K$ 的 $i$ ，我们考虑去找充要条件：

$i$ 合法当且仅当在图 $G$ 跑完最大流之后的残量网络中，存在一条流量不为 $0$ 的从 $S$ 到元素 $i$ 的路径，且图 $G$ 原先的最大流为 $m-1$ 。

（我一开始以为这个阙值是对 $exi_i$ 取没想到是对 $f_i$ 取，感觉如果想到对于 $f_i$ 取那么是容易的）。

于是你二分求出这个 $K$ 然后标记一下图 $G$ 残量网络上 $S$ 可达的点即可。

时间复杂度 $\mathcal{O}(\log m\cdot Dinic)$ ，因为是二分图所以 $Dinic$ 复杂度是 $\mathcal{O}(m^{1.5})$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXM = 2e6 + 10;
const int inf = 0x3f3f3f3f;

int n,m;
int siz[MAXN],exi[MAXN];
vector<int>V[MAXN];

int S,T;
int dis[MAXN];
int head[MAXN],now[MAXN],cnt=1;
struct edge{
	int v,w,nxt;
}e[MAXM<<1];
void Add_edge(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

bool bfs(){
	FL(i,S,T) dis[i]=inf;
	queue<int>q;
	now[S]=head[S],dis[S]=0,q.push(S);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(w&&dis[v]==inf){
				now[v]=head[v],dis[v]=dis[u]+1,q.push(v);
				if(v==T) return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int flow){
	if(u==T) return flow;
	if(!flow) return 0;
	int res=0;
	for(int i=now[u];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		now[u]=i;
		if(w&&(dis[v]==dis[u]+1)){
			int tmp=dfs(v,min(flow,w));
			if(!tmp) dis[v]=inf;
			e[i].w-=tmp,e[i^1].w+=tmp;
			flow-=tmp,res+=tmp;
		}
		if(!flow) break;
	}
	return res;
}
int dinic(){
	int res=0;
	while(bfs()) res+=dfs(S,inf);
	return res;
}

int check(int mid){
	S=0,T=n+m+1,cnt=1;
	FL(i,S,T) head[i]=0;
	FL(i,1,m){
		Add_edge(S,i,1),Add_edge(i,S,0);
		for(int j:V[i])
			Add_edge(i,j+m,1),Add_edge(j+m,i,0);
	}
	FL(i,1,n) Add_edge(i+m,T,mid),Add_edge(T,i+m,0);
	return dinic();
}

bool vis[MAXN];
void Get_vis(){
	FL(i,S,T) vis[i]=0;
	queue<int>q;
	vis[S]=1,q.push(S);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(w&&!vis[v])
				vis[v]=1,q.push(v);
		}
	}
}

int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	int ID,Num;
	scanf("%d%d",&ID,&Num);
	while(Num--){
		scanf("%d%d",&n,&m);
		FL(i,1,n) exi[i]=0;
		FL(i,1,m){
			scanf("%d",&siz[i]),V[i].clear();
			FL(j,1,siz[i]){
				int x;
				scanf("%d",&x);
				V[i].push_back(x);
				exi[x]++;
			}
		}
		int l=1,r=m,K=m;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(mid)==m) K=mid,r=mid-1;
			else l=mid+1;
		}
		int f=check(K-1);
		Get_vis();
		FL(i,1,n){
			if(exi[i]>K) putchar('Y');
			else if(exi[i]<K) putchar('N');
			else{
				if(f==m-1&&vis[i+m]) putchar('Y');
				else putchar('N');
			}
		}
		puts("");
	}
}

4.18

A

发现一次移动只会改变 $x,y$ 坐标中的一个，所以我们考虑将其分成两维。

我们考虑令局面的状态值为 $sg_{x1,x_2}\oplus sg_{y_1,y_2}$ 。

考虑一维辅助游戏的 SG 值怎么计算，令 $sg_{i,j}$ 表示两枚棋子在某一维坐标上分别为 $i,j$ 时的辅助 SG 值。

当 $|i-j|\le 1$ 时，这一维上两枚棋子的坐标相同（另一维坐标一定不同，这一维可以做镜像操作）或相邻（已经没有有效间隔，被限制，看另一维），因此把这一维视为零状态，令 $sg_{i,j}=0$ 。在局面的辅助异或值中，这一维不再产生贡献。

然后对于其余状态有：

$$sg_{i,j}=\mathrm{mex}(\{sg_{k,j}|1\le k<i\}\cup\{sg_{i,l}|1\le l<j\})$$

如果 $sg_{x_1,x_2}\oplus sg_{y_1,y_2}=0$ ，且 $|x_1-x_2|\not=1\or |y_1-y_2|\not=1$ ，也就是不是斜对角相邻，那么 $(x_1,x_2)(y_1,y_2)$ 这个局面就是必败态（因为斜对角相邻可以转移到同行/同列相邻，而同行/同列相邻是必败态，因为两个人可以做镜像操作，所以斜对角相邻是必胜态）。

（因为 SG 的定义保证，从一个状态走到后续状态，SG 值一定改变，所以移动后一定有 $sg_{x_1,x_2}\oplus sg_{y_1,y_2}\not=0$ ，也就是走到必胜态，胜负状态改变）。

时间复杂度 $\mathcal{O}(m^3+nm)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 3e2 + 10;

int n,m;
int sg[MAXN][MAXN];
bool vis[MAXN<<1];

bool Chk(int x1,int y1,int x2,int y2){
	return (sg[x1][x2]==sg[y1][y2]&&(abs(x1-x2)!=1||abs(y1-y2)!=1));
}

int main(){
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	scanf("%d%d",&n,&m);
	FL(i,1,m){
		FL(j,1,m){
			if(abs(i-j)<=1) continue;
			memset(vis,0,sizeof(vis));
			FL(k,1,i-1) vis[sg[k][j]]=1;
			FL(l,1,j-1) vis[sg[i][l]]=1;
			while(vis[sg[i][j]]) sg[i][j]++;
		}
	}
	while(n--){
		int x1,y1,x2,y2,ans=0;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		FL(x,(y1==y2&&x1>x2?x2+1:1),x1-1) ans+=Chk(x,y1,x2,y2);
		FL(x,(y1==y2&&x2>x1?x1+1:1),x2-1) ans+=Chk(x1,y1,x,y2);
		FL(y,(x1==x2&&y1>y2?y2+1:1),y1-1) ans+=Chk(x1,y,x2,y2);
		FL(y,(x1==x2&&y2>y1?y1+1:1),y2-1) ans+=Chk(x1,y1,x2,y);
		printf("%d\n",ans); 
	}
}

B

原题 ddcc2019_final_e

首先你可以想到变成二分图并按照 $B=\sqrt{V}$ ，设计权值，左部点处理 $kB$ ，右部点处理 $\bmod B$ 余数，此时的构造显然是正确的。

（此时你如果想到构造只有中间 $B\times B$ 条边有值的图，会比较容易推广）。

但显然不够优，考虑优化，我们考虑按照长度为 $4$ 的小块处理，如果当前 $S$ 中还没处理的最小值是 $t$ ，那么考虑 $[t,t+3]$ 的状态。

把 $t,t+1,t+2,t+3$ 出现的情况用二进制状态 $T$ 表示，将 $t$ 加入 $T$ 代表的集合，然后继续处理 $S$ 集合中 $>t+3$ 的第一个数。

于是我们在终点前设置 $3$ 个偏移点 $n-3,n-2,n-1$ ，分别提供权值 $3,2,1$ ，此时设我们处理的 $t$ 中状态为 $T$ 的有 $cnt_T$ 个，显然 $\sum cnt_T\le \lfloor\frac{V}{4}\rfloor$ 。

然后我们依旧想构造二分图，我们枚举左部点数量 $i$ ，然后第 $i$ 个点要新建 $\sum_{T\sube \{0,1,2,3\}}\lceil\frac{cnt_T}{i}\rceil$ 个右部点（也就是一共 $i\times \lceil\frac{cnt_T}{i}\rceil$ 条边，且只有这些边有值，其余边的权值均为 $0$ ），找使得点数最小的 $i$ 即可。

然后 $1$ 向 $i$ 个点连权值为 $0$ 的边，对于每个状态 $T$ ，如果 $T$ 的第 $i$ 位为 $1$ ，那么我们向对应的偏移点 $n-i$ 连权值为 $0$ 的边。

然后新建 $\lceil\frac{cnt_T}{i}\rceil$ 个右部点，和 $i$ 个左部点连边，边的权值为 $T$ 集合中的值。

时间复杂度 $\mathcal{O}(V)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e3 + 10;
const int inf = 0x3f3f3f3f;

int L;
int cnt,num,now=1;
int S,T;
bool vis[MAXN];
vector<int>P[16];
vector<array<int,3> >Edg;

int main(){
	freopen("death.in","r",stdin);
	freopen("death.out","w",stdout); 
	scanf("%d",&L);
	FL(i,1,L){
		int x;
		scanf("%d",&x),vis[x]=1;
	}
	FL(i,1,MAXN-1){
		if(vis[i]){
			int S=0;
			FL(j,i,i+3)
				if(vis[j]) S|=(1<<j-i);
			P[S].push_back(i),i+=3;
		}
	}
	cnt=inf,num=-1;
	FL(i,1,40){
		int nw=i+5;
		FL(S,1,(1<<4)-1) nw+=((int)P[S].size()+i-1)/i;
		if(nw<cnt) cnt=nw,num=i;
	}
	assert(num!=-1);
	S=1,T=cnt;
	FL(i,1,num) now++,Edg.push_back({S,now,0});
	FL(S,1,(1<<4)-1){
		while(!P[S].empty()){
			now++;
			FL(i,0,3)
				if((S>>i)&1) Edg.push_back({now,cnt-i,0});
			int j=1;
			while(j<=num){
				Edg.push_back({j+1,now,P[S].back()});
				P[S].pop_back(),j++;
				if(P[S].empty()) break; 
			}	
		}
	}
	Edg.push_back({T-3,T,3}),Edg.push_back({T-2,T,2}),Edg.push_back({T-1,T,1});
	printf("%d %d\n",cnt,(int)Edg.size());
	for(auto i:Edg) printf("%d %d %d\n",i[0],i[1],i[2]);
}

C

我们发现如果给定一个拓扑序，我们一定可以给图定向，也就是对于每条边，拓扑序靠前的指向靠后的，而每种无环定向对应唯一一种拓扑序。

所以所有合法定向方案的拓扑序数量之和是 $(2n)!$ ，此时我们要求这张二分图的无环定向方案数 $ans$ 。

发现一个无环定向图一定存在拓扑序，于是可以把点分成若干层 $B_1,B_2,\cdots,B_k$ ，要求每条边从前面的层指向后面的层，也就是说每个 $B_i$ 必须是独立集。

那么有 $ans=\sum_kA_k(-1)^kk!$ ，其中 $A_k$ 表示把所有点划分为 $k$ 个无序非空独立集的方案数。

因为图是二分图，所以左部点/右部点内部都没有边，所以左部点/右部点的划分天然是独立集，考虑先枚举左边 $n$ 个点被划分成多少个集合，然后再计算右边点怎么放进去。

左边只有 $n\le 13$ 个点，集合划分数量是 Bell 数， $B_{13}=27644437$ 。

然后令 $cnt_i$ 表示 $i$ 可以放入的左部点集合数量，有 $cnt_i=|\{j|N(i)\cap L_j=\varnothing\}|$ 。

令 $F_j$ 表示选 $j$ 个右部点让它们加入已有的左部点集合的方案，有 $F_{j}=\sum_{|T|=j}\prod_{i\in T} cnt_i$ ，构造多项式 $F(x)=\prod_{i=1}^n(cnt_ix+1)$ ，则 $F_j=[x^j]F(x)$ 。

然后剩下 $n-j$ 个要划分进 $k$ 个不区分的集合里，就是第二类 stirling 数 $\genfrac{\{}{\}}{0pts}{}{i}{j}$ 。

我们预处理 $W_{m,j}$ 表示当左边已经有 $m$ 个集合，且有 $j$ 个右点加入已有左集合时，剩余右部点随便划分产生的总容斥贡献，有：

$$W_{m,j}=\sum_{k=0}^{n-j}\genfrac{\{}{\}}{0pts}{}{n-j}{k}(-1)^{m+k}(m+k)!$$

然后这种左部点划分的答案就是 $\sum_{j=0}^n F_j\cdot W_{m,j}$ ，发现这个式子的值只和序列 $c$ 和 $m$ 有关，所以用 hash 把这些值压缩，同样的序列 $c$ 和 $m$ 只用算一次。

最后答案就是 $(2n)!\cdot ans^{-1}$ 。

时间复杂度 $\mathcal{O}(B_n\cdot n^2+K\cdot n^2)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int MAXN = 13 + 5;
const int mod = 998244353;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,m,ans=0;
int E[MAXN],Ed[MAXN];
int fac[MAXN<<1],S[MAXN][MAXN],W[MAXN][MAXN];
int cnt[MAXN],F[MAXN];
ull val[MAXN<<1];
map<ull,int>mp;

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

ull Get_hs(int tot){
	ull res=val[tot+n];
	FL(i,1,n){
		cnt[i]=0;
		FL(j,1,tot)
			cnt[i]+=(!((Ed[j]>>i-1)&1));
		res+=val[cnt[i]];
	}
	return res;
}

void dfs(int d,int tot){
	if(d>n){
		ull hs=Get_hs(tot);
		if(mp.find(hs)==mp.end()){
			int res=0;
			FL(i,0,n) F[i]=0;
			F[0]=1;
			FL(i,1,n)
				FR(j,i,1)
					F[j]=(F[j]+1ll*F[j-1]*cnt[i]%mod)%mod;
			FL(i,0,n)
				res=(res+1ll*F[i]*W[tot][i]%mod)%mod;
			mp[hs]=res;
		}
		ans=(ans+mp[hs])%mod;
		return ;
	}
	FL(i,1,tot+1){
		int prv=Ed[i];
		Ed[i]|=E[d];
		dfs(d+1,max(tot,i));
		Ed[i]=prv;
	}
}

int main(){
	freopen("night.in","r",stdin);
	freopen("night.out","w",stdout);
	scanf("%d%d",&n,&m);
	FL(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v),v-=n;
		E[u]|=(1<<v-1);
	}
	S[0][0]=1;
	FL(i,1,n)
		FL(j,1,i)
			S[i][j]=(S[i-1][j-1]+j*S[i-1][j]%mod)%mod;
	fac[0]=1;
	FL(i,1,(n<<1)) fac[i]=1ll*fac[i-1]*i%mod;
	FL(i,1,n)
		FL(j,0,n)
			FL(k,0,n-j)
				W[i][j]=(W[i][j]+1ll*S[n-j][k]*(((i+k)&1)?(mod-1):1)%mod*fac[i+k]%mod)%mod;
	FL(i,0,(n<<1)) val[i]=rnd();
	dfs(1,0);
	printf("%lld\n",1ll*fac[(n<<1)]*qpow(ans,mod-2)%mod);
}

省集笔记（4.14~4.18）

4.14

A

B

C

4.15

A

B

C

4.17

A

B

4.18

A

B

C

Status

Development

Support

About

省集笔记（4.14~4.18）

4.14

A

B

C

4.15

A

B

C

4.17

A

B

4.18

A

B

C

Status

Development

Support

About

SIGN IN