$loj$ 上没有此题,$bzoj$ 上是权限题,对于不上 $yzoj$ 的我来说只能去洛谷做题了:转送门

我们先不考虑边的权值(<与>),这样子 $n-1$ 条边组成的就是树了,很显然是需要我们求出这棵树的合法拓扑序的个数,考虑使用 $\rm{DP}$ ,对于边的方向(即<,>) ,我们分类讨论即可。

首先的一个想法就是设 $f_u$ 表示点 $u$ 的子树的合法拓扑序的总数,但是这个时候如何计算呢,对于一个 $u$ 的儿子 $v$ ,我们虽然知道 $u$ 和 $v$ 的攻克的前后关系,但是合并答案貌似并不好合并。这个时候我们增加一维 $j$ ,$f_{u,j}$ 表示 $u$ 的子树的所有合法拓扑序中 $u$ 在第 $j$ 位上的总状态数。

也就是说,对于一个必须在 $u$ 前面攻克的关卡 $v$ ,我们考虑枚举一个 $j$ ,$v$ 子树中 $j$ 个结点在合并 $u,v$ 后放到 $u$ 前面,另外 $sz_v-j$ 个放到 $u$ 后面,然后枚举一个 $k$ ,表示当前的 $v$ 排在 $v$ 子树的拓扑序中的第 $k$ 位,只有 $k\leq j$ 的时候 $v$ 才可以转移 $u$ ,因为这个时候 $v$ 在 $u$ 前面。

现在再来考虑$“$ $j$ 个结点放在 $u$ 前面 $"$ 的方案数和$“$ $sz_v-j$ 个结点放在 $u$ 后面的方案数$"$,这个显然可以用组合数算,合并 $v$ 的子树后,$u$ 的排名从 $i$ 变成了 $i+j$ ,也就是说我们需要将 $j$ 个乱序插入到 $u$ 前面 $i+j-1$ 个数中,方案数显然为 $C_{i+j-1}^{j}$ ,那么现在总节点数显然为 $sz_u+sz_v$ (现在 $sz_u$ 和 $sz_v$ 还没有并在一起) ,$u$ 后面理所当然有 $sz_u+sz_v-i-j$ 个位置,将 $sz_v-j$ 个数插进去的方案数显然为 $C_{sz_u+sz_v-i-j}^{sz_v-j}$ 个,这两个数再乘上 $f_{u,i}$ 和 $f_{v,k}$ 就好了,这一次合并后 $u$ 的位置显然到了 $i+j$ ,所以 $f_{u,i+j}$ 显然要加上这一组贡献。

经整理后的转移方程如下:

$$pls(f_{u,i+j},f_{u,i}\cdot f_{v,k}\cdot C_{i+j-1}^{j}\cdot C_{sz_u+sz_v-i-j}^{sz_v-j})$$

代码就是这样写:

for i=1 to sz[u]
    for j=1 to sz[v]
        for k=1 to j
            pls(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][j]*C[sz[u]+sz[v]-i-j][sz[v]-j])

这是 $n^3$ 的,过不去。考虑前缀和优化,几下 $f_v$ 的前缀和,最后的一层循环就可以直接丢掉了。

这个就是 $v$ 要在 $u$ 前面的情况,$u$ 在 $v$ 前面的情况和这个差不多,不过转移的时候 $j$ 就要从 $0$ 开始了,因为那个时候 $u$ 前面是可以不多放任何东西的,还有就是 $u$ 在 $v$ 前面的时候注意 $k\geq j$ 时才可以转移 !

最后的答案就是 $\sum\limits_{i=1}^{n} f_{1,i}$ 啦。

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e3+9;
const int mod=1e9+7;

int head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1];
int C[N][N],f[N][N],pre[N][N],suf[N][N],sz[N],g[N];

void add(int u,int v,int w) {
    G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u,w^1},head[v]=cnt;
}

namespace OI {
    void pls(int&x,int y) {x+=y;if(x>=mod)x-=mod;}
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace OI;

void dfs(int u,int fa) {
    sz[u]=f[u][1]=1;
    for(int l=head[u];l;l=G[l].nxt) {
        int v=G[l].to,w=G[l].val;
        if(v==fa) continue;
        dfs(v,u);
        memset(g,0,sizeof(g));
        if(w) {
            for(int i=1;i<=sz[u];++i)
                for(int j=1;j<=sz[v];++j)
                    pls(g[i+j],1ll*f[u][i]*pre[v][j]%mod*C[i+j-1][j]%mod
                    *C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
        } else {
            for(int i=1;i<=sz[u];++i)
                for(int j=0;j<=sz[v];++j)
                    pls(g[i+j],1ll*f[u][i]*suf[v][j+1]%mod*C[i+j-1][j]%mod
                    *C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
        }
        sz[u]+=sz[v];
        memcpy(f[u],g,sizeof(g));
    }
    pre[u][0]=suf[u][sz[u]+1]=0;
    for(int i=1;i<=sz[u];++i) pre[u][i]=(pre[u][i-1]+f[u][i])%mod;
    for(int i=sz[u];i>=1;--i) suf[u][i]=(suf[u][i+1]+f[u][i])%mod;
}

int solve() {
    memset(head,0,sizeof(head)),cnt=0;
    memset(f,0,sizeof(f));
    int n;IN(n);
    for(int i=1;i<n;++i) {
        int u,v;char sign;
        IN(u),sign=getchar(),IN(v);
        add(u+1,v+1,sign=='<'?0:1);
    }
    dfs(1,0);
    int ans=0;
    for(int i=1;i<=n;++i) pls(ans,f[1][i]);
    return ans;
}

int main() {
    /*预处理组合数*/
    for(int i=0;i<=N-2;++i) C[i][0]=1;
    for(int i=1;i<=N-2;++i)
        for(int j=1;j<=N-2;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    int T;IN(T);
    while(T--) printf("%d\n",solve());
    return 0;
}

可能有人会问,如果 $u$ 的儿子 $v$ 下面的边全都是 $>$ ,并且 $u$ 连向 $v$ 的边也是 $>$ ,那么这个时候 $v$ 以及其子树的所有点都必须在 $u$ 前面完成,在转移的时候为什么可以 $“$ 提出 $j$ 个结点放到 $u$ 前面 $"$ 呢?

其实想想就可以明白,在向上统计答案的时候对于一个 $v$ 的儿子 $a$ ,我们只统计了合并后 $a$ 在 $v$ 前面的情况,同样在 $u$ 统计 $v$ 时也只是统计了合并后 $v$ 在 $u$ 前面的情况,所有我们也只是统计了 $“$ $a$ 在 $v$ 前面且 $v$ 在 $u$ 前面 $"$ 的情况,所有被统计的情况一定是合法的。

最后修改:2019 年 05 月 30 日 03 : 24 PM