【AtCoder Grand 024E】Sequence Growing Hard 题解

题目大意

  求满足以下条件的序列集合 $\{A_0,A_1,...,A_N\}$ 的个数，模 $M$：

1. $A_i$ 长度为 $i$，其中每个元素都是 $[1,K]$ 内的一个正整数。
2. 对于 $i \geq 1$，$A_i$ 是由 $A_{i-1}$ 在某个位置插入一个数得到的。
3. 对于 $i \geq 1$，$A_i$ 字典序大于 $A_{i-1}$

  $N,K \leq 300,~M \leq 10^9$

GG做法

  假设现在有了一个最终的序列 $A_N$，考虑有多少种生成到它的序列集合。
  相当于每次删掉一个数。由于删掉之后字典序要变小，所以对于删的数，要么它右边比它小，要么它右边跟它相等，且一路过去最终比它小，但是为了避免计重，相等的这种情况不用理会。也就是说，对于单调不降的子段，它必须从后往前删。因此，如果把这个最终序列 $A_N$ 分解成若干个单调不降的极长子段，每段长 $len_i$，那么它的方案数就是

$$\frac{N!}{\prod len_i !}$$

  这样就可以 dp 这个 $A_N$ 了。设 $f_{i,j}$ 表示长度为 $i$ 的序列，最后一个元素为 $j$，的方案数。转移就是枚举最后一个极长子段，长度为 $len$，因此转移为

$$f_{i,j}=\sum_{len=1}^N \sum_{j'=2}^{k+1} f_{i-len,j'} \cdot \frac{G_{len,j'-1,j}}{len!}$$

  $G_{len,s,t}$ 是指长度为 $len$，开头小于等于$s$，结尾为 $t$ 的单调不降的序列个数，这个就是个挡板，可以预处理。这个各种优化之后就是 $O(n^2k)$ 的啦！

  一切就绪，编辑器，启动！

  。。。
  。。。
  （一段时间之后。。。

  woc 模数是他给的，不是质数就没有逆元了？？？？？

题解

  所以要搞个不用除法的 dp。。。

  此处搬一下题解。
  就考虑给一个序列插入一个数，同理，它只能插在一个比它小的数的左边。为了方便，假设一开始序列不为空，而是一个 $0$。
  假设把 $x$ 插在 $y$ 左边，那么就在树上把 $y$ 设为 $x$ 的父亲。
  设 $id_x$ 表示 $x$ 这个节点是第几个插入的，$v_x$ 表示它的值。那么这棵树满足儿子的 $id$ 和 $v$ 都比父亲大。
  不同的树与不同的序列集合一一对应，因此就是要求有多少棵树，使得任意儿子的两个权值都比父亲大。
  设 $f_{i,j}$ 表示这棵树大小为 $i$，点的 $id$ 为 $1$~$i$，根节点的 $v$ 值为 $j$，的方案数。显然 $id=1$ 的点一定是根节点，它一定有一个儿子是 $id=2$，因此转移就是枚举 $id=2$ 的这棵子树：

$$f_{i,j}=\sum_{size=1}^{i-1} \sum_{j'=j+1}^{k} f_{i-size,j} \cdot f_{size,j'} \cdot \binom{i-2}{size-1}$$

  这个 $j'$ 的枚举搞个后缀和去掉，因此时间是 $O(n^2k)$。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=305;

int n,k;
LL mo;

LL C[maxn][maxn];
void Pre(int n)
{
	fo(i,0,n)
	{
		C[i][0]=1;
		fo(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	}
}

LL f[maxn][maxn],sf[maxn][maxn];
int main()
{
	scanf("%d %d %lld",&n,&k,&mo);
	
	Pre(n);
	
	fo(j,0,k) f[1][j]=1, sf[1][j]=k-j+1;
	fo(i,2,n+1)
	{
		fo(j,0,k)
		{
			fo(sz,1,i-1) (f[i][j]+=f[i-sz][j]*sf[sz][j+1]%mo*C[i-2][sz-1])%=mo;
		}
		sf[i][k]=f[i][k];
		fd(j,k-1,1) sf[i][j]=(sf[i][j+1]+f[i][j])%mo;
	}
	
	printf("%lld\n",f[n+1][0]);
}