洛谷P3757 [CQOI2017]老C的键盘

传送门

首先可以直接把整个序列建成一个完全二叉树的结构，这个应该都看得出来

然后考虑树形dp，以大于为例

设$f[i][j]$表示$i$这个节点在子树中排名第$j$位时的总方案数（因为实际只与相对大小有关，与实际数值无关）

我们考虑如果从当前子树中弄出$k$个节点，其他子树中弄出$j-1$个节点，那么当前节点的大小排名就是$k+j$

然后考虑一下，如果我们不看这个子树，根节点排在第$j$个，方案数是$f[i][j]$，如果只看此子树，此子树的根就是根节点的儿子，它在此子树中的排名可能是$1,2,...k$，那么我们就需要记录一下前缀和

然后考虑合并排列

对于小于根节点的，选出$j-1$个非此子树，对于大于根节点的，选出$sum[x]-1$个非此子树里弄出来的，那么就是一个组合问题了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int N=,mod=1e9+;

 int n,tot;char s[N];

 ll f[N][N],g[N][N],tmp[N],c[N][N];

 int head[N],ver[N<<],Next[N<<],sum[N];

 inline void add(int u,int v){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;

 }

 void dfs(int x){

     int l=x<<,r=l|;;

     if(l<=n) add(x,l);

     if(r<=n) add(x,r);

     g[x][]=f[x][]=sum[x]=;

     for(int i=head[x];i;i=Next[i]){

         int v=ver[i];dfs(v);

         memset(tmp,,sizeof(tmp));

         for(int j=;j<=sum[x];++j)

         for(int k=;k<=sum[v];++k){

             if(s[v]=='>')

             tmp[j+k]+=f[x][j]*g[v][k]%mod

             *c[j+k-][j-]%mod*c[sum[x]+sum[v]-j-k][sum[x]-j]%mod;

             else tmp[j+k]+=f[x][j]*(g[v][sum[v]]-g[v][k]+mod)%mod

             *c[j+k-][j-]%mod*c[sum[x]+sum[v]-j-k][sum[x]-j]%mod;

         }

         sum[x]+=sum[v];

         for(int j=;j<=sum[x];++j)

         f[x][j]=tmp[j]%mod,g[x][j]=(g[x][j-]+f[x][j])%mod;

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     scanf("%d%s",&n,s+);

     c[][]=;

     for(int i=;i<=n;++i){

         c[i][]=;

         for(int j=;j<=i;++j)

         c[i][j]=(c[i-][j]+c[i-][j-])%mod;

     }

     dfs();printf("%lld\n",g[][sum[]]);

     return ;

 }