给定 , , , 问有多少个序列组 满足:
- 序列 的元素个数为 ;
- 所有元素都在 内;
- , 是 的子序列且 的字典序小于 ;
答案对 取模。
,。
等价于不断插入 之间的元素。
设当前序列为 ,考虑若在 之前插入 ,显然需要满足以下条件中至少一个:
- ;
- ;
- 设 ,;
发现第三种情况等价于在 之前插入 ,那不妨钦定只能有第一种和第二种情况,这样钦定刚好避免算重。
令 ,则只能在比 小的元素前插入。
但是还是不好做,设 表示最终序列中 插入时其后继在最终序列的位置,则 这些区间肯定要么相交要么包含。不妨从 向 连边,这样会形成一棵以 为根的树,只需要对树的方案计数即可。
具体的,对于一棵树,其根 必定是最先插入的;对于 的儿子,我们可以确定一个插入时间的相对顺序,来确定其子树在最终序列中的位置。
也就是说树中每个点的儿子有顺序。
注意到我们只关心树根元素的大小和树的大小,于是设 表示大小为 ,树根元素为 的树的方案数,转移考虑枚举插入时间最早的儿子 (序列中最远离 ),那么有转移:
其中组合数相当于有 个插入的时间可以选择, 和 必定是前两个插入的, 子树中点的插入时间可以任意选择。
使用前缀和优化可以做到 。
代码如下:
#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;
}