AGC067D Unique Matching 做题记录

定义 $n$ 个区间 $[l_i,r_i]$ 构成的序列是好的，当且仅当：

• $1\le l_i\le r_i\le n$；
• 存在唯一的一个 $n$ 的排列 $p$ 使得 $l_i\le p_i\le r_i$；

给定 $n,p$，求好的区间序列个数，对素数 $p$ 取模。

$1\le n\le 5000$，$10^9\le p\le 1.01\times 10^9$。

首先钦定 $p_i=i$，最后答案再乘上 $n!$，那么这样有 $l_i\le i\le r_i$。

考虑将 $l_i$ 和 $r_i$ 分开做，那么限制相当于不存在 $i<j$ 使得 $l_j\le i,r_i\ge j$，否则就可以交换 $i,j$。

十分智慧地，考虑二维平面。对于每个 $i$，加入线段 $(i,i),(i,r_i)$ 和线段 $(i,i),(l_i,i)$，那么限制转化为这些线段不能在除 $(i,i)$ 外的地方相交。

那么考虑先画出横着的线段，将 $(i,i+1),(i,r_i)$ 下方的区域涂上颜色，竖着的线段的限制就是不能进入被涂色的区域：（图来自 luogu @隔壁泞2的如心 的题解）

不难发现，对于最右边的未被涂色的列，则其左侧和右侧是独立的；而若不存在这样的列，最下面一行除了 $(1,1)$ 外一定都被涂色，相当于一个 $n-1$ 的子问题：

考虑 dp，设 $f_{n}$ 表示大小为 $n$ 的答案，$g_n$ 表示大小为 $n$ 且最下面一行除了 $(1,1)$ 外都被涂色的答案，则有转移：

$g_{n}=(n-1)\times g_{n-1}+\sum\limits_{i=2}^{n-1}f_{i-1}\times g_{n-i}\times i\times (n-i)\\ f_{n}=g_n+\sum\limits_{i=2}^{n}f_{i-1}\times g_{n-i+1}\times i$

$f$ 的转移是枚举最右边的未被涂色的列在哪里；$g$ 的转移则是枚举第 $2$ 行最右边的未被涂色的列在哪里，从而确认 $r_1$ 的最小值。

边界 $f_1=g_1=1$，时间复杂度 $O(n^2)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=5005;

int n,p;
int g[S],f[S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	scanf("%d%d",&n,&p);
	g[1]=1,f[1]=1;
	for(int i=2;i<=n;i++)
	{
		g[i]=1ll*(i-1)*g[i-1]%p;
		for(int j=2;j<=i-1;j++)
		{
			add(g[i],1ll*f[j-1]*g[i-j]%p*j%p*(i-j)%p);
		}
		f[i]=g[i];
		for(int j=2;j<=i;j++)
		{
			add(f[i],1ll*f[j-1]*g[i-j+1]%p*j%p);
		}
	}
	int fra=1;
	for(int i=1;i<=n;i++) fra=1ll*fra*i%p;
	printf("%d\n",1ll*f[n]*fra%p);
	return 0;
}