M_sea

洛谷4099 [HEOI2013]SAO
Luogu分析树形 $\mathrm{DP}$ 。显然所有限制条件构成一个树形图,考虑以 $1$ 为根跑 $\ma...
扫描右侧二维码阅读全文
26
2019/04

洛谷4099 [HEOI2013]SAO

Luogu

分析

树形 $\mathrm{DP}$ 。

显然所有限制条件构成一个树形图,考虑以 $1$ 为根跑 $\mathrm{DP}$ 。

设 $f[i][j]$ 表示以 $i$ 为根的子树, $i$ 在子树内排名为 $j$ 的方案数。

转移的话,每次把一颗子树 $v$ 合并进来,也就是把 $f[v][k]$ 算到 $f[u][i]$ 里去。分两种情况:

  • $v$ 在 $u$ 的前面

枚举一个 $j$ 表示 $v$ 的子树中有 $j$ 个在 $u$ 前面。

那么当前的方案数是 $C_{i+j-1}^{i-1}\times f[u][i]\times f[v][k]\times C_{sz[u]+sz[v]-i-j}^{sz[u]-i}$ ,把它累加到 $f[u][i+j]$ 里去。

考虑怎么优化转移。现在的转移是这个样子(忽略 $\mathrm{long\ long}$ 的问题):

for (re int i=1;i<=sz[u];++i)
    for (re int k=1;j<=sz[v];++k)
        for (re int j=k;j<=sz[v];++j)
            add(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);

把 $j$ 和 $k$ 换一下,变成:

for (re int i=1;i<=sz[u];++i)
    for (re int j=1;j<=sz[v];++j)
        for (re int k=1;k<=j;++k)
            add(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);

那么只要记一下 $f[v]$ 的前缀和就能去掉 $k$ 那一维,实现 $O(1)$ 转移了。

  • $v$ 在 $u$ 的后面

和上面的情况类似:

for (re int i=1;i<=sz[u];++i)
    for (re int j=0;j<=sz[v];++j)
        for (re int k=i+1;k<=sz[v];++k)
            add(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);

记 $f[v]$ 的后缀和同样能够实现 $O(1)$ 转移。


最后的答案为 $\sum\limits_{i=1}^nf[1][i]$ 。总时间复杂度为 $O(n^2)$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline 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=1000+10;
const int mod=1000000007;

struct Edge { int v,w,nxt; } e[N<<2];
int head[N],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int n,sz[N];
int f[N][N],g[N],pre[N][N],suf[N][N];
int C[N][N];

inline void add(int& x,int y) { x=(x+y)%mod; }

inline void dfs(int u,int fa) {
    sz[u]=f[u][1]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        dfs(v,u),sz[u]+=sz[v];

        memset(g,0,sizeof(g));
        if (w) {
            for (re int j=sz[u]-sz[v];j;--j)
                for (re int k=0;k<=sz[v];++k)
                    add(g[j+k],1ll*f[u][j]*C[j+k-1][k]%mod*C[sz[u]-j-k][sz[v]-k]%mod*pre[v][k]%mod);
        } else {
            for (re int j=sz[u]-sz[v];j;--j)
                for (re int k=0;k<=sz[v];++k)
                    add(g[j+k],1ll*f[u][j]*C[j+k-1][k]%mod*C[sz[u]-j-k][sz[v]-k]%mod*suf[v][k+1]%mod);
        }
        memcpy(f[u],g,sizeof(g));
    }
    pre[u][0]=suf[u][sz[u]+1]=0;
    for (re int i=1;i<=sz[u];++i) pre[u][i]=(pre[u][i-1]+f[u][i])%mod;
    for (re int i=sz[u];i>=1;--i) suf[u][i]=(suf[u][i+1]+f[u][i])%mod;
}

inline void init() {
    memset(head,0,sizeof(head)),cnt=0;
    memset(f,0,sizeof(f));
}

inline void solve() {
    init(); n=read();
    for (re int i=1;i<n;++i) {
        int u,v; char op[2];
        u=read()+1,scanf("%s",op),v=read()+1;
        if (op[0]=='<') addEdge(u,v,0),addEdge(v,u,1);
        else addEdge(u,v,1),addEdge(v,u,0);
    }
    dfs(1,0);
    int ans=0;
    for (re int i=1;i<=n;++i) add(ans,f[1][i]);
    printf("%d\n",ans);
}

int main() {
    C[0][0]=1;
    for (re int i=1;i<=1000;++i) {
        C[i][0]=1;
        for (re int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    
    int T=read();
    while (T--) solve();
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 41 PM

发表评论