首页 > 代码库 > BZOJ 3167: [Heoi2013]Sao

BZOJ 3167: [Heoi2013]Sao

Description

一个排列,满足一些限制,形成一个树形结构,求方案数\(T\leqslant 5,n\leqslant 1\times 10^3\)

Solution

树形DP.

\(f[i][j]\)表示\(i\)是在他的子树中排名为\(j\).

也是暴力合并信息,复杂度分析同上题.

Code

/**************************************************************    Problem: 3167    User: BeiYu    Language: C++    Result: Accepted    Time:8336 ms    Memory:18580 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;typedef pair<int,int> pr;const int N = 1050;const LL p = 1e9+7; #define mpr make_pair#define x first#define y second int T,n;vector<pr> h[N];LL fac[N<<1],ifac[N<<1];LL f[N][N],g[N][N],sz[N],tmp[N]; LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }void Add(LL &x,LL y) { x=(x+y)%p; }void init(int n) {    fac[0]=1;    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p;    ifac[n]=Pow(fac[n],p-2),ifac[0]=1;    for(int i=n-1;i;--i) ifac[i]=ifac[i+1]*(i+1)%p;}LL C(int n,int m) { return n<m?0:fac[n]*ifac[m]%p*ifac[n-m]%p; }void AddEdge(int fr,int to,int v) { h[fr].push_back(mpr(to,v)); }void clr() {    memset(f,0,sizeof(f));    memset(g,0,sizeof(g));    for(int i=0;i<N;i++) h[i].clear();}void DFS(int u,int fa) {    sz[u]=1,f[u][1]=1;    for(int t=0,v;t<(int)h[u].size();t++) if((v=h[u][t].x)!=fa){        DFS(v,u);        for(int i=0;i<=sz[u]+sz[v];i++) tmp[i]=0;        if(h[u][t].y) for(int i=1;i<=sz[u];i++) for(int j=1;j<=sz[v];j++)             Add(tmp[i+j],f[u][i]*g[v][j]%p*C(i+j-1,j)%p*C(sz[u]+sz[v]-i-j,sz[v]-j)%p);        else for(int i=1;i<=sz[u];i++) for(int j=0;j<=sz[v];j++)             Add(tmp[i+j],f[u][i]*(g[v][sz[v]]-g[v][j]+p)%p*C(i+j-1,j)%p*C(sz[u]+sz[v]-i-j,sz[v]-j)%p);        sz[u]+=sz[v];        for(int i=1;i<=sz[u];i++) f[u][i]=tmp[i];    }    for(int i=1;i<=sz[u];i++) g[u][i]=(g[u][i-1]+f[u][i])%p;     /*  cout<<"------"<<endl;    cout<<u<<" "<<fa<<" "<<sz[u]<<endl;    for(int i=1;i<=sz[u];i++) cout<<f[u][i]<<" ";cout<<endl;*/}int main() {    for(scanf("%d",&T),init(2000);T--;) {        clr();scanf("%d",&n);        for(int i=1;i<n;i++) {            int u,v;char opt[5];            scanf("%d%s%d",&u,opt,&v);            u++,v++;            if(opt[0]==‘<‘) AddEdge(u,v,0),AddEdge(v,u,1);            else AddEdge(u,v,1),AddEdge(v,u,0);        }DFS(1,1);        LL ans=0;        for(int i=1;i<=n;i++) Add(ans,f[1][i]);        printf("%lld\n",ans);    }return 0;}

  

BZOJ 3167: [Heoi2013]Sao