问题 J: [Heoi2013]Sao
时间限制: 3 Sec 内存限制: 256 MB
题目描述
WelcometoSAO(StrangeandAbnormalOnline)。这是一个VRMMORPG，
含有n个关卡。但是，挑战不同关卡的顺序是一个很大的问题。
有n–1个对于挑战关卡的限制，诸如第i个关卡必须在第j个关卡前挑战，或者完成了第k个关卡才能挑战第l个关卡。并且，如果不考虑限制的方向性，那么在这n–1个限制的情况下，任何两个关卡都存在某种程度的关联性。即，我们不能把所有关卡分成两个非空且不相交的子集，使得这两个子集之间没有任何限制。
输入
第一行，一个整数T，表示数据组数。对于每组数据，第一行一个整数n，表示关卡数。接下来n–1行，每行为“i sign j”，其中0≤i,j≤n–1且i≠j，sign为“<”或者“>”，表示第i个关卡必须在第j个关卡前/后完成。
输出
对于每个数据，输出一行一个整数，为攻克关卡的顺序方案个数，mod
1,000,000,007输出。
样例输入
2
5
0 < 2
1 < 2
2 < 3
2 < 4
4
0 < 1
0 < 2
0 < 3
样例输出
4
6
提示
对于100%的数据有T≤5，1≤n≤1000。
明显是效率在N^2左右的树规。设f[i][j]为访问完i为根的子树，i点是第j个被访问的。考虑一棵子树一棵子树向上添加（不然时间效率上过不去）
把边视为无向边，只要分别考虑就行了。
先考虑当前儿子在此节点之前。
枚举x原来的排名为j，然后子节点子树里有k个点在x前面访问。要找出这k个点占了哪几个位置（一个组合数就行了，剩下的位置就给了原来的子树），而在后面的点也同样要确定位置。而这k点的顺序（方案）其实已经算好了。因为有k个点在x前，而son也在x前，所以son满足的状态就是f[son][1~k].用前缀和维护。
在考虑此节点在儿子之前，
改成后缀和就好了，一样的。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define N 1012
#define P 1000000007
using namespace std;
struct road{
int v,next,l;}lu[N*2];
int T,n,e,adj[N],sz[N];ll sum[N][N],f[N][N],g[N],C[N][N];
void add(int u,int v,int l){lu[++e]=(road){v,adj[u],l};adj[u]=e;}
void init()
{for(int i=0;i<=1000;i++)for(int j=0;j<=i;j++)if(j==i||j==0)C[i][j]=1;else C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
}
void dfs(int x,int fa)
{sz[x]=1;f[x][1]=1;for(int i=adj[x];i;i=lu[i].next){int to=lu[i].v;if(to==fa)continue;dfs(to,x);for(int j=1;j<=sz[x]+sz[to];j++)g[j]=0;for(int j=1;j<=sz[x];j++)for(int k=0;k<=sz[to];k++)if(lu[i].l==-1)(g[j+k]+=f[x][j]*sum[to][k]%P*C[j+k-1][j-1]%P*C[sz[to]+sz[x]-j-k][sz[x]-j]%P)%=P;else (g[j+k]+=f[x][j]*(sum[to][sz[to]]-sum[to][k]+P)%P*C[j+k-1][j-1]%P*C[sz[to]+sz[x]-j-k][sz[x]-j]%P)%=P;sz[x]+=sz[to];for(int j=1;j<=sz[x];j++)f[x][j]=g[j];}for(int i=1;i<=sz[x];i++)sum[x][i]=(sum[x][i-1]+f[x][i])%P;
}
char getc(){char ch=getchar();while(ch!='<'&&ch!='>')ch=getchar();return ch;
}
int main()
{scanf("%d",&T);init();while(T--){e=0;memset(adj,0,sizeof(adj));memset(f,0,sizeof(f));memset(sum,0,sizeof(sum));memset(sz,0,sizeof(sz));scanf("%d",&n);char s;for(int i=1,x,y;i<n;i++){scanf("%d",&x);s=getc();scanf("%d",&y);x++;y++;if(s=='<')add(x,y,1),add(y,x,-1);else add(x,y,-1),add(y,x,1);}dfs(1,0);printf("%lld\n",sum[1][sz[1]]);}
}