题解 P4099 【[HEOI2013]SAO 】

# 要开 UNSIGNED LONG LONG！！！ _不是因为爆 long long 而是因为这题开了 long long 常数太大导致TLE_ ~~(可见这题卡常数之丧心病狂)~~ #### 树形动态规划 先说一下蜜汁题意，给你一只树形图，求它有多少种不同的拓扑序。 然后如果你把这题看成拓扑图来做，多半你已经凉了……，正确的做法是，既然树形图和树没啥大区别，我们把这只树形图看成树就行了，在这上面跑树形dp，再去考虑边方向的限制。 那么我们发现按照一般传统的套路来讲，我们设dp\[i]表示“以i为根的子树拓扑序方案数”。 那么我们可以认为，每个dp数组代表的是一个长度为siz\[i]的序列(siz\[i]表示以i为根的子树中点的个数)。 那么我们可以这样来更新dp，我们对整棵树进行dfs，如果我们dfs到了点u，已经dfs完了u一个儿子v，那么我们可以认为，更新的过程，等价于将dp\[u]代表的序列和dp\[v]的代表的序列"融合”的过程，当我们不断dfsu的每一个儿子vi时，我们相当于把它儿子的序列一个一个加进去，当dfsu完成时，它刚好成为了一个长度为siz\[u]的子序列，同时，融合后，原来个 下面是 u在v 前的情况 。。。。u。。。v。。。。 我们发现，单凭一个dp\[i]我们不能知道这个序列长啥样，更准确的说，我们不能知道u前有多少个元素，u，v之间有多少元素，v后有多少元素，所以我们需要一个辅助维，来帮助我们"定位"这个序列 那么一个很自然的想法是，加入j，表示i在拓扑序中的排名，这样的话，虽然我们还是没有办法确定u，v间的元素个数，也没办法确定v后元素个数，但是，我们却可以把整个序列按照u劈成两半，其中前半部分属于u的元素个数确定，后半部分属于u的元素个数确定，前半部分总元素个数确定，后半部分总元素个数确定。 似乎，我们可以知道这个序列大致长什么样了。 设当前要合并的状态为dp\[u]\[i],和dp\[v]\[j],合并后，u前的总元素个数为k 那么我们会发现，u前总元素个数为k-1，u前属于u的元素个数为i-1，所以前面的总可能为c\[i-1]\[k-1],(为什么？因为我们要保证属于u的相对元素位置不变，所以我们一旦从前k-1个位置选出了i-1个位置，那么我们就只有dp\[u]\[i]种填法，因为我们必须按顺序填进去)同理后边属于u的元素个数为siz\[u]-i,总元素个数为siz\[u]+siz\[v]-k,所以后面的位置总可能有c\[siz\[u]-i]\[siz\[u]+siz\[v]-k]种 所以我们可以得到一个状态转移方程 dp\[u]\[k]=dp\[u]\[i]\*dp\[v]\[j]\*c\[i-1]\[k-1]\*c\[siz\[u]+siz\[v]-k] 然后就是枚举的范围了，如果u在v前，为了保证状态合法，我萌要保证j的范围在(k-i,siz\[v])之间 如果u在v后那么我们为了保证状态合法，我们要保证j的范围在(1,k-i)之间 最后上一个前缀和优化(因为你发现最后一层循环的j，可以用乘法分配律提出来，所以就可以前缀和了)，每个点对在lca出计算一波复杂度，总体复杂度O(N^2)，注意，转移方程的四个数，乘起来爆long long,需要两两分开乘，膜三遍 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std; typedef unsigned long long ll; const int N=2010; ll mod=1e9+7;bool book[N]; int n;ll dp[N][N];ll sumdp[N][N];int siz[N]; ll c[N][N];int cnt;int alist[N]; struct data{int v;int nxt;int tw;}edge[2*N]; inline void add(int u,int v,int tw) {edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].tw=tw;} inline void clear()//多组询问的clear { for(int i=0;i<=n;i++) {alist[i]=0;book[i]=false;siz[i]=1;dp[i][1]=1;sumdp[i][1]=0; for(int j=2;j<=n;j++){dp[i][j]=0;sumdp[i][j]=0;}}cnt=0; } int t; inline void dfs(int x) { book[x]=true;int nxt=alist[x]; while(nxt) { int v=edge[nxt].v;int tw=edge[nxt].tw; if(book[v]==false) { dfs(v); if(tw==0)//U在v前 { for(int k=siz[x]+siz[v];k>=1;k--) { ll sum=0; for(int i=1;i<=min(siz[x],k);i++) { int l=k-i;int r=siz[v];ll del=(sumdp[v][r]+mod-sumdp[v][l])%mod; if(l<r)//前缀和优化，记得分开膜 { ll p=(dp[x][i]*del)%mod;ll q=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[v]-k])%mod; p*=q;p%=mod;sum+=p;sum%=mod; } } dp[x][k]=sum; } } else//同理，注意范围 { for(int k=siz[x]+siz[v];k>=1;k--) { ll sum=0; for(int i=1;i<=min(siz[x],k-1);i++) { int r=min(siz[v],k-i); ll p=(dp[x][i]*sumdp[v][r])%mod;ll q=(c[i-1][k-1]*c[siz[x]-i][siz[x]+siz[v]-k])%mod; p*=q;p%=mod;sum+=p;sum%=mod; } dp[x][k]=sum; } }siz[x]+=siz[v]; } nxt=edge[nxt].nxt; } for(int i=1;i<=siz[x];i++)//处理前缀和 {sumdp[x][i]=(sumdp[x][i-1]+dp[x][i])%mod;} return; } int main() { scanf("%d",&t);c[0][0]=1; for(int i=1;i<=1005;i++)//打表组合数 { c[0][i]=1; for(int j=1;j<i;j++) {c[j][i]=(c[j][i-1]+c[j-1][i-1])%mod;} c[i][i]=1; } for(int z=1;z<=t;z++) { scanf("%d",&n);ll res=0;clear(); for(int i=1;i<n;i++) { int u;int v;char op[15]; scanf("%d%s%d",&u,op,&v);//加边 u+=1;v+=1; if(op[0]=='<'){add(u,v,0);add(v,u,1);} else {add(u,v,1);add(v,u,0);} } dfs(1); for(int i=1;i<=n;i++){res=(res+dp[1][i])%mod;} printf("%lld\n",res); }return 0;//拜拜程序~ } ```