CF1874F Jellyfish and OEIS 做题记录

给定一个长 $n$，值域 $[0,n]$ 的序列 $m$，求有多少个 $n$ 的排列 $p$，满足 $\forall r\le m_l$ 的 $p_{[l,r]}$ 不构成 $[l,r]$ 的排列。对 $10^9+7$ 取模。

$1\le n\le 200$。

为什么有一大堆题解都没提到第二次容斥？注意力太强了。

钦定 $\sum m_l-l+1$ 个区间的一个区间子集 $S$ 使得 $\forall [l,r]\in S$，$p_{[l,r]}$ 构成排列，容斥系数为 $(-1)^{|S|}$。

若两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 有交但不是包含关系，不妨假设 $l_1<l_2\le r_1<r_2$，则 $p_{[l_2,r_1]}$ 构成排列，同理 $p_{[l_1,l_2-1]}$ 和 $p_{[r_1+1,r_2]}$ 也构成排列。并且这是双射的，若 $p_{[l_1,l_2-1]}$、$p_{[l_2,r_1]}$ 和 $p_{[r_1+1,r_2]}$ 均构成排列，则 $p_{[l_1,r_1]}$ 和 $p_{[l_2,r_2]}$ 构成排列。

那么这两个区间可以拆成三个区间。

所以现在 $S$ 需要满足内部区间包含或相离，套路地使用树形结构描述，每个区间对应一个节点，其儿子是被之包含的若干个极长区间。则每个点的方案数是区间内散点的数量的阶乘。

问题在于容斥系数，若一个点 $[l_u,r_u]$ 有一些儿子区间是相邻的，即 $r_i=l_{i+1}-1$，则容斥系数不显然。因为我们要计算的是在 $[l_u,r_u]$ 中选若干个（假设选了 $k$ 个）满足 $r\le m_l$ 的子区间 $[l,r]$ 使得它们不断拆开能恰好得到 $u$ 的所有儿子区间，所有这样方案的 $(-1)^k$ 的和，不妨称这些区间为原始区间。

考虑继续容斥，对于每个连续段分别考虑，我们的目标是将容斥系数放到每个儿子区间上。假设当前连续段是 $[r_0+1,r_1][r_1+1,r_2][r_2+1,r_3]\dots[r_{k-1}+1,r_k]$，显然仅需满足每个儿子区间都被某个原始区间包含，且所有原始区间的左端点 $\in \{r_i+1|0\le i<k\}$，右端点 $\in \{r_i|1\le i\le k\}$。

那么钦定 $t$ 个儿子区间不被任何原始区间包含，容斥系数为 $(-1)^t$。考虑剩下任选的方案数，不难发现，若没有任何合法的原始区间可选，则方案数为 $1$，否则方案数就是 $\sum\limits_{i=0}^k\binom{k}{i}(-1)^i=0$，其中 $k$ 为可选的原始区间个数。

而由于原始区间是形如 $[l,[l,m_l]]$ 这样的，故这相当于要求除去钦定的儿子区间外，剩余的儿子区间都满足 $r>m_l$，而钦定的儿子区间则每个贡献 $-1$ 的系数，这对于多个连续段的情况依然是成立的。

那么考虑对于一个儿子区间 $[l,r]$，若 $r>m_l$ 则其会贡献 $-1+1=0$ 的系数（钦定是 $-1$，未被钦定则是 $1$），故 $u$ 的所有儿子区间都必须满足 $r\le m_l$，并会带来 $-1$ 的系数。

那么考虑区间 dp，设 $f_{l,r}$ 表示区间 $[l,r]$ 的子树的答案；$g_{l,r,k}$ 表示区间 $[l,r]$ 内且散点个数为 $k$ 时儿子的 $f$ 的乘积（计算了容斥系数但未计算 $k!$ 的系数），转移 $O(n^4)$ 即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=205;

#define p 1000000007

int fra[S];
int n,a[S];
int g[S][S][S],f[S][S];

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

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(a[1]==n) return puts("0"),0;
	for(int i=0;i<=n;i++) g[i+1][i][0]=1;
	for(int len=1;len<=n;len++)
	{
		for(int l=1;l<=n-len+1;l++)
		{
			int r=l+len-1;
			for(int k=0;k<=len;k++)
			{
				for(int x=r;x>=l+1;x--)
					if(r<=a[x])
						add(g[l][r][k],
							p-1ll*g[l][x-1][k]*f[x][r]%p);
				if(k>0) add(g[l][r][k],g[l][r-1][k-1]);
			}
			for(int k=0;k<=len;k++)
				add(f[l][r],1ll*fra[k]*g[l][r][k]%p);
			if(r<=a[l]) add(g[l][r][0],p-f[l][r]);
		}
	}
	printf("%d\n",f[1][n]);
	return 0;
}