D · Divide and Conquer：中文题面与个人代码

时限 2 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

考虑深度为 $n$ 的满二叉树，根的深度为零，共 $2^{n+1}-1$ 个结点。根编号为 $1$ ，内部结点 $u$ 的左右儿子分别为 $2u,2u+1$ 。

叶子编号为 $2^n,\ldots,2^{n+1}-1$ ，其权值必须恰好构成 $1,\ldots,2^n$ 的一个排列。每个内部结点的权值等于两个儿子权值的最大值。另给出 $q$ 个约束 $(u_i,x_i)$ ，要求结点 $u_i$ 的权值恰为 $x_i$ 。

求满足全部约束的叶子排列数，对 $998244353$ 取模。叶子排列确定后，所有内部结点也唯一确定。

输入、输出与约束 #

本题只有一组数据。首行 $1\le n\le18$ 、 $0\le q\le2^{n+1}-1$ 。随后 $q$ 行输入 $1\le u_i<2^{n+1}$ 、 $1\le x_i\le2^n$ 。题面没有承诺约束中的结点互不相同，重复或矛盾约束都必须处理。输出一个整数。

样例 #

输入 1 #

2 1
2 2

输出 1 #

输入 2 #

2 2
1 4
2 4

输出 2 #

输入 3 #

2 2
2 3
4 4

输出 3 #

输入 4 #

4 2
1 2
1 3

输出 4 #

样例说明 #

样例一要求左子树最大值为 $2$ ，所以左边两片叶子只能放 $1,2$ ，右边放 $3,4$ ，共 $2!\times2!=4$ 种。样例二要求 $4$ 在左半边，共 $2\times3!=12$ 种。样例三要求一个祖先最大值为 $3$ 、其后代却为 $4$ ，无解；样例四对根同时指定 $2,3$ ，也无解。

个人代码：按最大值处理受限区间 #

令 $N=2^n$ 。b[u] 记录结点 $u$ 覆盖的叶子区间。树上这些区间要么相离，要么包含。代码额外加入根约束 $(1,N)$ ，再按指定最大值升序排列；同值时按结点编号降序，让后代先于祖先处理。

fa 是“下一个尚未分配的叶子位置”的并查集。处理一个区间时，用它找出并删除其中所有空位，数量记为 s。cnt 统计当前最大值范围内尚未使用的数字数目；指定值上升时增加新进入范围的数字。

若当前指定值是新出现的 $w$ ，必须把 $w$ 放入这批空位之一：选位置有 $s$ 种，其余位置从剩余 cnt-1 个数中做排列，贡献

$s\,P(\mathrm{cnt}-1,s-1),\qquad P(x,y)=\frac{x!}{(x-y)!}.$

如果指定值与上一条相同，它应已放在包含链更深的区间中；当前新增空位只需填较小的剩余数字，贡献 $P(\mathrm{cnt},s)$ 。同值区间若相离，一个数字不可能同时成为两区间最大值，答案为零。末尾 dfs 检查指定值是否小于后代已有的指定值。

这种计数解释依赖“可用数字和空位数量合法”等前提；当前原稿在无解分支没有及时结束，存在以下边界问题，不能把它作为无条件安全模板。

无解输入中的负下标 #

合法输入 1 1，下一行 1 1，要求两片叶子的最大值为 $1$ ，显然无解。原稿再加入根约束 $(1,2)$ 后：第一条约束使用两个空位，cnt 降到 $-1$ ，ans 已变为零；处理第二条时没有新空位，调用 A(-1,-1)。函数的 x<y 检查不成立，于是读取 in[-1]，属于未定义行为。随后乘以零并不能消除前面的非法读取。

给独立诊断副本的 A 加入参数检查后，该输入实际触发了 invalid A arguments: -1 -1。公开下载仍保留原始代码，没有把诊断副本冒充用户提交。修复方向是在不可能分配时直接返回零，并保证排列数函数只对 $0\le y\le x$ 取阶乘下标。

复杂度与验证 #

令 $M=10^6$ ，原稿对每个阶乘单独快速幂求逆元，预处理为 $O(M\log 998244353)$ ，并非通常的线性逆阶乘预处理。后续排序 $O(q\log q)$ ；每片叶子删除一次，但这里是仅路径压缩的定向并查集，采用保守的 $O((N+q)\log N)$ 界；树遍历 $O(N)$ ，数组空间 $O(M)$ 。可改为只求一次最高阶乘逆元，再向下递推。并查集 get 仍为递归实现，需要另行留意调用栈。

本地结果： 四组样例通过；36 组深度不超过三的约束实例与全部叶子排列暴力计数一致；深度 18、无约束输入输出 $546362027$ ，与 $262144!\bmod998244353$ 一致。以上测试不撤销已定位的负下标问题，也不等同于本份文件的 OJ 提交记录。

原始 C++ 文件 #

下载 D.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：8b53e9f27e4d3ba35f81c634537c623931ffd5c4291555bb7576407655835ba1。

#include<bits/stdc++.h>
#define int long long
#define pa pair<int,int>
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
using namespace std;
int read(){
	int x;scanf("%lld",&x);
	return x;
}
int mi(int x,int y){
	int ans=1,base=x;
	while(y){
		if(y&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		y>>=1;
	}
	return ans;
}
int n,q,in[1000005],inv[1000005],ans;
int fa[1000005],N;
int c[1000005];
pa b[1000005];
int A(int x,int y){
	if(x<y)return 0;
	return in[x]*inv[x-y]%mod;
}
pa a[1000005];
int get(int x){
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
int dfs(int x){
	if(x>(1<<n+1)-1)return 0;
	int w=max(dfs(x*2),dfs(x*2+1));
	if(c[x]&&c[x]<w)ans=0;
	return max(w,c[x]);
}
void solve(){
	n=read();q=read();
	int N=(1<<n);
	for(int i=1;i<=q;i++)a[i].fi=read(),a[i].se=read();
	q++;
	a[q]={1,N};
	sort(a+1,a+1+q,[](pa a,pa b){
		if(a.se!=b.se)return a.se<b.se;
		return a.fi>b.fi;
	});
	for(int i=1;i<=N+1;i++)fa[i]=i;
	for(int i=N;i<=(1<<n+1)-1;i++)b[i]=pa{i-N+1,i-N+1};
	for(int i=N-1;i>=1;i--)b[i]=pa{b[i*2].fi,b[i*2+1].se};
	int cnt=0;ans=1;
	for(int i=1;i<=q;i++){
		if(a[i-1].fi==a[i].fi&&a[i-1].se==a[i].se)continue;
		if(a[i-1].se==a[i].se){
			if(b[a[i-1].fi].se<b[a[i].fi].fi||b[a[i-1].fi].fi>b[a[i].fi].se){
				ans=0;
				break;
			}
		}
		int x=a[i].fi,w=a[i].se;
		cnt+=w-a[i-1].se;
		int l=b[x].fi,r=b[x].se;
		int s=0;
		for(int j=get(l);j<=r;j=get(j+1)){
			s++;
			fa[get(j)]=get(j+1);
		}
		if(a[i-1].se!=a[i].se)ans=(ans*A(cnt-1,s-1)%mod*s%mod)%mod;
		else ans=ans*A(cnt,s)%mod;
		cnt-=s;
	}
	for(int i=1;i<=q;i++)c[a[i].fi]=a[i].se;
	int k=dfs(1);
	printf("%lld\n",ans);
}
signed main(){
//	freopen("a.in","r",stdin);
//	freopen("a.ans","w",stdout);
	in[0]=1;
	for(int i=1;i<=1e6;i++)in[i]=(in[i-1]*i)%mod;
	inv[0]=1;
	for(int i=1;i<=1e6;i++)inv[i]=mi(in[i],mod-2);
	int t=1;
	while(t--)solve();
}