AGC024E Sequence Growing Hard 做题记录

给定 $n$, $k$, $m$ , 问有多少个序列组 $(A_0,A_1,\dots,A_n)$ 满足：

• 序列 $A_i$ 的元素个数为 $i$；
• 所有元素都在 $[1,k]$ 内；
• $\forall i\in[0,n-1]$，$A_i$ 是 $A_{i+1}$ 的子序列且 $A_i$ 的字典序小于 $A_{i+1}$；

答案对 $m$ 取模。

$1\le n,k\le 300$，$2\le m\le 10^9$。

等价于不断插入 $[1,k]$ 之间的元素。

设当前序列为 $a$，考虑若在 $a_i$ 之前插入 $x$，显然需要满足以下条件中至少一个：

• $i=n+1$；
• $x>a_i$；
• 设 $to_i=\min\limits_{j>i,a_j\not=a_i}j$，$a_i>a_{to_i}$；

发现第三种情况等价于在 $a_{to_i}$ 之前插入 $x$，那不妨钦定只能有第一种和第二种情况，这样钦定刚好避免算重。

令 $a_{n+1}=0$，则只能在比 $x$ 小的元素前插入。

但是还是不好做，设 $nt_i$ 表示最终序列中 $a_i$ 插入时其后继在最终序列的位置，则 $[i,nt_i]$ 这些区间肯定要么相交要么包含。不妨从 $i$ 向 $nt_i$ 连边，这样会形成一棵以 $n+1$ 为根的树，只需要对树的方案计数即可。

具体的，对于一棵树，其根 $rt$ 必定是最先插入的；对于 $rt$ 的儿子，我们可以确定一个插入时间的相对顺序，来确定其子树在最终序列中的位置。

也就是说树中每个点的儿子有顺序。

注意到我们只关心树根元素的大小和树的大小，于是设 $f_{i,u}$ 表示大小为 $i$，树根元素为 $u$ 的树的方案数，转移考虑枚举插入时间最早的儿子 $v$（序列中最远离 $u$），那么有转移：

$f_{i,u}=\sum\limits_{j=1}^{i-1}\binom{i-2}{j-1}\times f_{i-j,u}\times\sum\limits_{v>u}f_{j,v}$

其中组合数相当于有 $i$ 个插入的时间可以选择，$rt$ 和 $v$ 必定是前两个插入的，$v$ 子树中点的插入时间可以任意选择。

使用前缀和优化可以做到 $O(n^2k)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=305;

int n,k,p;
int C[S][S],f[S][S],sum[S][S];

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

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