洛谷P4099 [HEOI2013]SAO

@Pelom  October 12, 2021

题意

给出一个连成树的有向图,求拓扑序数量

数据范围:$1 \le n \le 1000$

题解

树形$dp$,用$f[i][j]$表示以$i$为根的子树中,节点$i$的排名为$j$的方案数
考虑转移,对于$u$为$v$的父节点,$x$在原序列中排名为$p_1$,新序列中排名为$p_3$;$y$在原序列中排名为$p_2$,新序列中排名为$p_4$,从$f[u][p_1]$与$f[v][p_2]$转移到$f[u][p_3]$,先考虑$p_3$的范围:

  • 若$u$的拓扑序小于$v$,有$p_3 < p_4$,同时$p_1$左边的节点仍在$p_3$左边($p_1 \le p_3$),$p_2$左边的节点有一部分可以在$p_3$左边(但必须留至少$1$个,因为题目要求子集必须相交),即$$p_1 \le p_3 \le p_1+p_2-1$$
  • 若$u$的拓扑序大于$v$,有$p_3 > p_4$,同时$p_1,p_2$左边的节点都在$p_3$左边($p_1+p_2 \le p_3$),但最多有$p_1+siz[v]$个点,即$$p_1+p_2 \le p_3 \le p_1+siz[v]$$

由于选择,还要乘组合数:

  • $$C_{p_3-1}^{p_1-1}$$$p_3$左边的$p_3-1$个点中一定有$p_1-1$个来自$u$的原序列
  • $$C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}$$$p_3$右边的$siz[u]+siz[v]-p_3$个点中一定有$siz[u]-p_1$个来自$u$的原序列

状态转移方程即为$$f[u][p_3]+ \!\! =\sum_{p_1}\sum_{p_2}\sum_{p_3} C_{p_3-1}^{p_1-1}C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}f[u][p_1]f[v][p_2]$$
但这样每次转移有$3$层循环,考虑优化
发现$p_2$在求和中只出现一次并且连续,可以用前缀和优化;先将$p_2$与$p_3$交换(注意更改限制条件)

$$ \begin{aligned} f[u][p_3]+ \!\! &=\sum_{p_1}\sum_{p_3}\sum_{p_2} C_{p_3-1}^{p_1-1}C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}f[u][p_1]f[v][p_2] \\ &= \sum_{p_1}\sum_{p_3} C_{p_3-1}^{p_1-1}C_{siz[u]+siz[v]-p_3}^{siz[u]-p_1}f[u][p_1]\sum_{p_2} f[v][p_2] \end{aligned} $$

这时可以直接把$dp$数组存为前缀和

注: 这样看似是$O(n^3)$的(外$dfs$遍历点$\times$内$2$层循环),但实际上内$2$层循环可以看作枚举点对$(p_1,p_3)$,而每对点最多枚举$1$次,因此总复杂度为$O(n^2)$

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000+10;
const int mod=1e9+7;
int t,n,u,v;
char c;
struct edge{
    int nxt,to,w;
} e[N<<1];
int cnt;
int head[N],C[N][N],siz[N],dp[N][N],tmp[N];
inline void add(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}
void dfs(int u){
    siz[u]=1;
    dp[u][1]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(siz[v])
            continue;
        dfs(v);
        memcpy(tmp,dp[u],sizeof(tmp));
        memset(dp[u],0,sizeof(dp[u]));
        if(e[i].w){
            for(int p1=1;p1<=siz[u];p1++)
                for(int p3=p1;p3<=p1+siz[v]-1;p3++)
                    (dp[u][p3]+=1ll*C[p3-1][p1-1]*C[siz[u]+siz[v]-p3][siz[u]-p1]%mod*tmp[p1]%mod*(dp[v][siz[v]]-dp[v][p3-p1])%mod)%=mod;
        }
        else{
            for(int p1=1;p1<=siz[u];p1++)
                for(int p3=p1+1;p3<=p1+siz[v];p3++)
                    (dp[u][p3]+=1ll*C[p3-1][p1-1]*C[siz[u]+siz[v]-p3][siz[u]-p1]%mod*tmp[p1]%mod*(dp[v][p3-p1])%mod)%=mod;
        }
        siz[u]+=siz[v];
    }
    for(int i=1;i<=siz[u];i++)
        (dp[u][i]+=dp[u][i-1])%=mod;
}
int main(){
    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]+C[i-1][j-1])%mod;
    }
    scanf("%d",&t);
    for(;t--;){
        cnt=0;
        memset(head,0,sizeof(head));
        memset(siz,0,sizeof(siz));
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d %c %d",&u,&c,&v);
            u++,v++;
            add(u,v,c=='<');
            add(v,u,c=='>');
        }
        dfs(1);
        printf("%d\n",(dp[1][n]%mod+mod)%mod);
    }
    return 0;
}

添加新评论