[AGC024E] Sequence Growing Hard 题解

题目链接

点击打开链接

题目解法

考虑如何添加数，使得 \(\{a_1,...,a_i\}\) 到 \(\{a_1,...,x,a_j,...,a_i\}\) 是合法的
需要手玩一会才能发现合法条件很简单：\(x>a_j\)

考虑对这个进行计数
一个一个添元素是难维护的，现在假设有最终的序列，每个位置有 \((v,dfn)\)，分别为值和添加的次序
合法条件是显然的：\(\forall i\in[1,n],v_i>v_{\min\{j,j>i\and dfn_j<dfn_i\}}\) 如果不存在 \(j\)，可以默认 \(j=n+1\)，\(n+1\) 处为 \((0,0)\)

下面的一步还是比较妙的（参考 tzc 的做法）
我们考虑建树，即由 \(j\to i\) 连边，建出来的树在 tzc 的博客中可以看到
一个添数的方案可以一一对应一棵合法的树
而这棵树仅需满足：父亲的 \(v<\) 儿子的 \(v\)，且父亲的 \(dfn<\) 儿子的 \(dfn\)
这是可以 \(dp\) 的
令 \(f_{i,j}\) 表示大小为 \(i\) 的树，且根的 \(v\) 为 \(j\) 的方案数
转移考虑枚举 \(i\) 的子树中 \(dfn\) 第二小的子树大小 \(k\)
转移是显然的：\(f_{i,j}=\sum\limits_{q=1}^{j-1} f_{i-q,j}\binom{i-2}{q-1}\sum\limits_{l=j+1}^k f_{q,l}\)
不难用前缀和优化成 \(O(n^3)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=310;
int n,k,Mod,f[N][N],C[N][N],s[N][N];
inline void inc(int &x,int y){ x+=y;if(x>=Mod) x-=Mod;}
int main(){
    n=read(),k=read(),Mod=read();
    F(i,0,n+1){ C[i][0]=C[i][i]=1;F(j,1,i-1) C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;}
    DF(i,k,0) f[1][i]=1,s[1][i]=(s[1][i+1]+1)%Mod;
    F(i,2,n+1) DF(v,k,0){
        F(j,1,i-1) inc(f[i][v],1ll*s[j][v+1]*f[i-j][v]%Mod*C[i-2][j-1]%Mod);
        s[i][v]=(s[i][v+1]+f[i][v])%Mod;
    }
    printf("%d\n",f[n+1][0]);
    return 0;
}