AGC024E Sequence Growing Hard 做题记录

给定 nn, kk, mm , 问有多少个序列组 (A0,A1,,An)(A_0,A_1,\dots,A_n) 满足:

  • 序列 AiA_i 的元素个数为 ii
  • 所有元素都在 [1,k][1,k] 内;
  • i[0,n1]\forall i\in[0,n-1]AiA_iAi+1A_{i+1} 的子序列且 AiA_i 的字典序小于 Ai+1A_{i+1}

答案对 mm 取模。

1n,k3001\le n,k\le 3002m1092\le m\le 10^9

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

设当前序列为 aa,考虑若在 aia_i 之前插入 xx,显然需要满足以下条件中至少一个:

  • i=n+1i=n+1
  • x>aix>a_i
  • toi=minj>i,aj=aijto_i=\min\limits_{j>i,a_j\not=a_i}jai>atoia_i>a_{to_i}

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

an+1=0a_{n+1}=0,则只能在比 xx 小的元素前插入。

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

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

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

注意到我们只关心树根元素的大小和树的大小,于是设 fi,uf_{i,u} 表示大小为 ii,树根元素为 uu 的树的方案数,转移考虑枚举插入时间最早的儿子 vv(序列中最远离 uu),那么有转移:

fi,u=j=1i1(i2j1)×fij,u×v>ufj,vf_{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}

其中组合数相当于有 ii 个插入的时间可以选择,rtrtvv 必定是前两个插入的,vv 子树中点的插入时间可以任意选择。

使用前缀和优化可以做到 O(n2k)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;
}