BZOJ3167: [Heoi2013]Sao

所有限制关系无视方向是一棵树，那么任意定一个点为根，做树形DP，f[i][j]表示i在其子树的序列中排第j位的方案数，转移的话组合数弄一下，直接这样转移会发现复杂度很高，但是转移的方程可以转化一下，会发现每个点维护f值的前缀后缀和即可剪掉一维

---

#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int maxn = 1100; const ll Mod = 1e9+7; struct edge { int y,c,nex; edge(){} edge(int _y,int _c,int _nex){y=_y; c=_c; nex=_nex;} }a[maxn<<1]; int len,fir[maxn]; void ins(int x,int y,int c) { a[++len]=edge(y,c,fir[x]); fir[x]=len; a[++len]=edge(x,-c,fir[y]); fir[y]=len; } ll f[maxn][maxn],si[maxn],N[maxn]; ll g[maxn],pres[maxn][maxn],las[maxn][maxn]; int siz[maxn],fa[maxn]; int n; ll pw(ll x,int k) { ll r=1,t=x; for(;k;k>>=1,t=t*t%Mod) if(k&1) r=r*t%Mod; return r; } ll Ni(ll x) { return pw(x,Mod-2); } ll cal(ll n,ll m) { if(!m||n==m)return 1ll; return si[n]*N[n-m]%Mod*N[m]%Mod; } void dfs(int x) { siz[x]=1; f[x][1]=1; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; if(y!=fa[x]) { fa[y]=x; dfs(y); siz[x]+=siz[y]; } } int kn=1; for(int l=fir[x];l;l=a[l].nex) { int y=a[l].y; if(y!=fa[x]) { if(a[l].c==1) { for(int i=1;i<=kn;i++) { for(int k=i+1;k<=i+siz[y];k++) { (g[k]+=f[x][i]*pres[y][k-i]%Mod*cal(k-1,i-1)%Mod*cal(kn+siz[y]-k,kn-i)%Mod)%=Mod; } } } else { for(int i=1;i<=kn;i++) { /* for(int j=1;j<=siz[y];j++) // j>=k-i+1 {*/ for(int k=i;k<=i+siz[y]-1;k++) { (g[k]+=f[x][i]*las[y][k-i+1]%Mod*cal(k-1,i-1)%Mod*cal(kn+siz[y]-k,kn-i)%Mod)%=Mod; } //} } } kn+=siz[y]; for(int i=1;i<=kn;i++) f[x][i]=g[i],g[i]=0; } } for(int i=1;i<=kn;i++) pres[x][i]=(pres[x][i-1]+f[x][i])%Mod; las[x][kn+1]=0; for(int i=kn;i>=1;i--) las[x][i]=(las[x][i+1]+f[x][i])%Mod; } int main() { si[1]=1; for(ll i=2;i<=1000;i++) si[i]=si[i-1]*i%Mod; N[1000]=Ni(si[1000]); for(ll i=999;i>=1;i--) N[i]=N[i+1]*(i+1)%Mod; int t;scanf("%d",&t); while(t--) { memset(fir,0,sizeof fir); len=0; memset(f,0,sizeof f); scanf("%d",&n); for(int i=1;i<n;i++) { char str; int x,y,c; scanf("%d",&x); x++; getchar(); str=getchar(); c=str=='>'?1:-1; scanf("%d",&y); y++; ins(x,y,c); } dfs(1); ll r=0; for(int i=1;i<=n;i++) r+=f[1][i]; r%=Mod; printf("%lld\n",r); } return 0; }