题解 P4099 【[HEOI2013]SAO 】

λᴉʍ · 2019-03-05 20:14:25 · 题解

P4099 [HEOI2013]SAO

贼板子有意思的一个题～～～我（）竟然没看题解

没卡就暂时这题rk1了来写一发题解

有一张连成树的有向图，球拓扑序数量。

树形dp，设f[i][j]表示i在子树中i拓扑序上排名为j的方案数。

难就难在转移，现在有两个树x和y，其中x是父亲，x的拓扑序小于y的，从f[x][p1],f[y][p2]转移到newf[x][p3]：x在原序列中排名p1，新序列中p3；y在原序列中排名p2，新序列中p4，那么限制是p3<p4

那么x子树中，p1左边的点也一定在p3左边（因为是和同一个点x比较）

又有限制p3<p4，所以y的原序列中排名为[p2,siz_y]都在p3右边，[1,p2-1]可以有一些在p3右边，有一些在左边

所以p3的左边数的数量限制是：p1-1\leq p3-1\leq p1-1+p2-1，也就是p1\leq p3\leq p1+p2-1

还有一种情况就是新序列中x在y右边的，也是同理推，转移方程一样，唯一的区别是p3的取值范围是p1+p2\leq p3\leq p1+siz_x。

然后就解决了，然而是O(n^3)的，考虑优化

当然把式子写出来啊（还是以新序列中x在y左边为例）

for p1 in [1,siz_x]
    for p2 in [1,siz_y]
        for p3 in [p1,p1+p2-1]
            转移

观察一下转移方程，好像p2只出现了一次，还是连续的，于是调换循环顺序（省去对循环范围的推倒）：

for p1 in [1,siz_x]
    for p3 in [p1,p1+siz_y-1]
        for p2 in [p3-p1+1,siz_y]
            转移

那么把循环转移成了p2最后一个循环，就可以用前缀和优化转移了，然后这题切了。。。

就是新序列中x在y右边的情况直接看代码。

#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 1000000007
typedef long long ll;
il ll gi(){
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int fir[1010],dis[2010],nxt[2010],w[2010],id;
il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
int f[1010][1010],g[1010],siz[1010];
int C[1010][1010];
il vd dfs(int x){
    siz[x]=1;f[x][1]=1;
    for(int i=fir[x];i;i=nxt[i]){
        if(siz[dis[i]])continue;
        dfs(dis[i]);
        memcpy(g,f[x],sizeof g);
        memset(f[x],0,sizeof f[x]);
        if(w[i]==1){
            for(int p1=1;p1<=siz[x];++p1)
                for(int p3=p1;p3<p1+siz[dis[i]];++p3)
                    f[x][p3]=(f[x][p3]+1ll*C[siz[x]+siz[dis[i]]-p3][siz[x]-p1]*C[p3-1][p1-1]%mod*g[p1]%mod*(f[dis[i]][siz[dis[i]]]-f[dis[i]][p3-p1]+mod))%mod;
        }else{
            for(int p1=1;p1<=siz[x];++p1)
                for(int p3=p1+1;p3<=p1+siz[dis[i]];++p3)
                    f[x][p3]=(f[x][p3]+1ll*C[siz[x]+siz[dis[i]]-p3][siz[x]-p1]*C[p3-1][p1-1]%mod*g[p1]%mod*f[dis[i]][p3-p1])%mod;
        }
        siz[x]+=siz[dis[i]];
    }
    for(int i=1;i<=siz[x];++i)f[x][i]=(f[x][i]+f[x][i-1])%mod;
}
int main(){
#ifdef XZZSB
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    C[0][0]=1;
    for(int i=1;i<=1000;++i){
        C[i][0]=1;
        for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    int T=gi();
    while(T--){
        id=0;memset(fir,0,sizeof fir);memset(siz,0,sizeof siz);
        int n=gi(),a,b;char ch;
        for(int i=1;i<n;++i){
            scanf("%d %c %d",&a,&ch,&b);++a,++b;
            link(a,b,ch=='<');link(b,a,ch=='>');
        }
        dfs(1);
        printf("%d\n",f[1][n]);
    }
    return 0;
}