Luogu

LOJ

分析

为什么 17 年省选还出 13 年的题的弱化版啊

设 $dp_{u,i}$ 表示以 $u$ 为根的子树,$u$ 的排名为 $i$ 的方案数。

转移时将 $v$ 合并到 $u$ 中,在 $i+j-1$ 个比 $u$ 小的数中选出 $j$ 个放在 $v$ 子树中,在 $sz_u+sz_v-i-j$ 个比 $u$ 大的数中选出 $sz_v-j$ 个放在 $v$ 子树中,即乘上两个组合数,再乘上 $dp_{v,x}$ 的前 / 后缀和。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;
const int mod=1e9+7;

int n,C[N][N]; char s[N];

int sz[N],dp[N][N],tmp[N],pre[N][N],suf[N][N];
void dfs(int u) {
    vector<int> ch;
    if ((u<<1)<=n) ch.emplace_back(u<<1);
    if ((u<<1|1)<=n) ch.emplace_back(u<<1|1);
    sz[u]=dp[u][1]=1;
    for (int v:ch) {
        dfs(v);
        for (int i=1;i<=sz[u]+sz[v];++i) tmp[i]=0;
        for (int i=1;i<=sz[u];++i)
            for (int j=0;j<=sz[v];++j) {
                if (s[v]=='<')
                    tmp[i+j]=(tmp[i+j]+1ll*dp[u][i]*suf[v][j+1]%mod
                    *C[i+j-1][j]%mod*C[sz[u]+sz[v]-i-j][sz[v]-j])%mod;
                else
                    tmp[i+j]=(tmp[i+j]+1ll*dp[u][i]*pre[v][j]%mod
                    *C[i+j-1][j]%mod*C[sz[u]+sz[v]-i-j][sz[v]-j])%mod;
            }
        sz[u]+=sz[v];
        for (int i=1;i<=sz[u];++i) dp[u][i]=tmp[i];
    }
    for (int i=1;i<=sz[u];++i) pre[u][i]=(pre[u][i-1]+dp[u][i])%mod;
    for (int i=sz[u];i;--i) suf[u][i]=(suf[u][i+1]+dp[u][i])%mod;
}

int main() {
    n=read(),scanf("%s",s+2);
    for (int i=C[0][0]=1;i<=n;++i)
        for (int j=C[i][0]=1;j<=n;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    dfs(1); int ans=0;
    for (int i=1;i<=n;++i) ans=(ans+dp[1][i])%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 06 月 17 日 08 : 15 PM