2026 NOI 做题记录（十七）

$\text{By DaiRuiChen007}$

A. [CF2187F2] Al Fine (5)

设 $a=[1,2,\dots,n]$，那么一棵子树的结构应该是满足 $\max b[l,r]=b_l+r-l$ 的区间 $[l,r]$。

直接递归，$f_{l,r}$ 表示 $[l,r]$ 构成森林的方案数，每次枚举 $l$ 所属的区间做到 $\mathcal O(n^3)$。

考虑观察性质优化，注意到 $a=b$ 时答案是卡特兰数，也就是 $n+1$ 个点生成的无标号树个数。

观察递归的过程，求 $f_{l,r}$ 时找到最大的 $p$ 使得 $b[l,p]$ 合法，那么 $[l,p],(p,r]$ 必定属于不同子树，可以直接划分，即 $p<r$ 时 $f_{l,r}=f_{l,p}\times f_{p+1,r}$。

对于 $p=r$ 的情况，按所有 $[l,q]$ 合法的 $q$ 把序列分成若干段 $(q_{i-1},q_i]$，每段 $[x,y]$ 满足 $b[x,y]$ 值域等于 $[b_l-l+x,b_l-l+y]$，且长度 $>1$ 时 $b_x\ne x$。

手玩一下分裂子树的过程，如果所有区间长度都是 $1$，那么可以以任意顺序分裂，假设分成了 $[v_1+1,v_2-1],[v_2+1,v_3-1],\dots,[v_{k}+1,v_{k+1}-1]$，其中 $v_1=l,v_{k+1}=r+1$，那么把 $v_1\sim v_k$ 看成 $l-1 $ 的儿子，然后递归儿子的划分过程，这样就得到了一棵无标号树，可以发现方案数就是卡特兰数。

而对于一个长度 $>1$ 的区间 $[x,y]$，如果分裂为 $[l,x),[x,r]$，那么由于 $b_x\ne \min b[x,r]$，则 $b[x,r]$ 不合法，那么我们会不断按上述找 $p$ 的过程分裂。

此时可以发现按该过程分裂若干次后，我们会得到 $b(y,r]$ 以及 $b[x,y]$ 内部分裂出的若干区间，证明考虑如果存在合法区间 $b[u,v]$ 满足 $x\le u\le y<v$，显然 $x<u$，则 $b[u,y]$ 值域是 $[b_l-l+u,b_l-l+y]$，从而 $b[l,u)$ 合法，序列应该分成 $[x,u),[u,y]$ 两个线段，所以在 $b[x,r]$ 内找 $p$ 等价于在 $b[x,y]$ 内找 $p$。

因此这种情况下贡献就是 $f_{y,r}\times f_{x+1,y}$。

所以说对于这些长度大于 $1$ 的区间，我们一定会分裂出 $f_{x+1,y}$ 的贡献，然后我们要考虑这若干个区间之间的分裂顺序，还是按刚才的方法建树，但是如果根的某个儿子是 $y-x>1$ 的 $x$，那么我们会立刻分裂出 $(x,y]$，也就是说 $x$ 在树上必定对应一个叶子。

那么我们就解决了 $f_{l,r}$，先算出 $\prod f_{x+1,y}$，然后对于内部的合并，看成按 dfs 序插入若干个点，有一些点必须当叶子的方案数，直接顺序 dp，只要维护当前点深度即可转移。

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

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,MOD=998244353;
int n,a[MAXN],ia[MAXN],f[MAXN][MAXN],h[MAXN];
vector <int> g[MAXN];
int dp(int l,int r) {
	if(l>=r) return 1;
	if(~f[l][r]) return f[l][r];
	int m=upper_bound(g[l].begin(),g[l].end(),r)-g[l].begin()-1;
	if(g[l][m]<r) return f[l][r]=1ll*dp(l,g[l][m])*dp(g[l][m]+1,r)%MOD;
	int z=1;
	for(int i=1;i<=m;++i) z=1ll*z*dp(g[l][i-1]+1,g[l][i])%MOD;
	h[1]=1;
	for(int i=1;i<=m;++i) {
		if(g[l][i-1]<g[l][i]-1) {
			for(int j=i;~j;--j) h[j]=(h[j]+h[j+1])%MOD;
		} else {
			for(int j=i+1;j>=1;--j) h[j]=(h[j+1]+h[j-1])%MOD;
			h[0]=0;
		}
	}
	for(int i=1;i<=m+1;++i) h[0]=(h[0]+h[i])%MOD,h[i]=0;
	f[l][r]=1ll*z*h[0]%MOD,h[0]=0;
	return f[l][r];
}
void solve() {
	cin>>n;
	for(int l=1;l<=n;++l) for(int r=l;r<=n;++r) f[l][r]=-1;
	for(int i=1,x;i<=n;++i) cin>>x,ia[x]=i;
	for(int i=1,x;i<=n;++i) cin>>x,a[i]=ia[x];
	for(int i=1;i<=n;++i) {
		g[i].clear();
		for(int j=i,o=0;j<=n&&a[j]>=a[i];++j) {
			o=max(o,a[j]);
			if(o-a[i]==j-i) g[i].push_back(j);
		}
	}
	cout<<dp(1,n)<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--) solve();
	return 0;
}

DaiRuiChen007

2026 NOI 做题记录（十七）

A. [CF2187F2] Al Fine (5)

B. [CF2180F2] Control Car (1.5)

C. [CF2183H] Minimise Cost (4)

D. [CF2190E] Median Permutation (4)

E. [CF2162H] Beautiful Problem (2)

*F. [CF2181K] Knit the Grid (7.5)

*G. [CF2178H] Create or Duplicate (7)

H. [CF2157H] Keygen 3 (3)

I. [CF2180G] Balance (1.5)

J. [CF2190G] Maximize Determinant (6)

K. [CF2187E] Doors and Keys (4.5)

L. [CF2172C] Circles Are Far from Each Other (3.5)

M. [CF2174D] Secret Message (1.5)

N. [CF2174E2] Game of Scientists (4)

O. [CF2172G] Gene Editor (5)

*P. [CF2165F] Arctic Acquisition (7)

Q. [CF2161H] Cycle Sort (5.5)

R. [CF2165E] Rainbow Branch (4.5)

S. [CF2159E] Super-Short-Polynomial-San (4)

T. [CF2178I] Numbers or Fireworks (4)

U. [CF2161F] SubMST (3)

*V. [CF2159F] Grand Finale: Snakes (8)

W. [CF2183G] Snake Instructions (4)

*X. [CF2187G] Many Cartesian Trees (7.5)

Y. [CF2161G] Bitwise And Equals (5)

Z. [CF2157G] Isaac's Queries (3.5)

*AA. [CF2190F] Xor Product (7.5)

*AB. [CF2158F2] Distinct GCDs (7)

公告