洛谷 P4099 – SAO

大家好，欢迎来到IT知识分享网。

upd 21.9.14：今天被 lxr 叉掉了，我这个做法是三方的（但是跑不满所以过去了）。。。。遇到问题出大锅，锅不出在复杂度证明上，而出在由代码到复杂度式子上。观察代码发现复杂度应该是 \(\mathrm O\!\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^{|son_i|}sz_{son_{i,j}}\sum\limits_{k=1}^{j}sz_{son_{i,k}}\right)\) 而非 \(\mathrm O\!\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^{|son_i|}sz_{son_{i,j}}\sum\limits_{k=1}^{j-1}sz_{son_{i,k}}\right)\)，前者是三方，后者是平方。

emmm… tzc 说是好题，那肯定是好题，因为 tzc 英语带师！

洛谷题目页面传送门

给定一个基图为树的有向图，求它的拓扑序个数。答案对 \(10^9+7\) 取模。本题多测。

\(n\in[1,1000],T\in[1,5]\)。

考虑树形 DP。很自然的想到 \(dp_{i,j}\) 表示子树 \(i\) 中节点 \(i\) 在拓扑序列中的序数为 \(j\) 的拓扑序列数。

那么在转移的时候，要把一个节点的所有儿子都考虑进去，这个极不好控制，是指数级的。不难发现，儿子与儿子之间没有直接联系，只是 \(i\) 与儿子们各有一个联系。于是可以将儿子一个一个算入转移中，而非同时转移，这样能使时间复杂度得以控制在多项式级别。具体地，大概就加个一维 \(dp_{i,j,k}\)，\(j\) 表示考虑到 \(i\) 的第 \(j\) 个儿子了，\(k\) 为原 \(j\)。这样看起来状态数增加了一级，其实不然，因为 \(\sum\limits_{i=1}^n|son_i|=\mathrm O(n)\)。还是 \(\mathrm O\!\left(n^2\right)\)。

目标：\(\sum\limits_{i=1}^ndp_{1,|son_1|,i}\)；边界：\(dp_{i,0,1}=1\)。

接下来考虑如何转移。当前要计算 \(dp_{i,j}\)，我们设 \(h=dp_{i,j},f=dp_{i,j-1},g=dp_{son_{i,j},\left|son_{son_{i,j}}\right|}\)，那么显然是 \(f\) 和 \(g\) 共同算出 \(h\)。然后设 \(sz_h,sz_f,sz_g\) 分别为所对应的 size。根据 \(i\) 和 \(son_{i,j}\) 之间边的方向，分两种情况，分别为在拓扑序中 \(son_{i,j}\) 在 \(i\) 前和后。现在先讨论前者。

考虑枚举 \(h\) 中在 \(i\) 前面有几个 \(g\) 中的点。那么此时 \(i\) 在 \(f\) 中的排名已经确定了，用在 \(h\) 中的排名减去前面在 \(g\) 中的点数即可。那么 \(son_{i,j}\) 在 \(g\) 中的排名呢？它需要在 \(i\) 前面，于是在 \(1\) 到「\(h\) 中在 \(i\) 前面有几个 \(g\) 中的点」均可。\(f\) 和 \(g\) 内部的排列方案数定下来了，然后再很自然地给 \(f\) 和 \(g\) 分配相对位置，\(i\) 左边和右边各乘上一个组合数即可。于是得到前者的状态转移方程：

类似地可以得到后者的方程（比较恶心一点）：

此时总时间复杂度是 \(\mathrm O\!\left(n^4\right)\) 的（平方状态，平方转移）。考虑优化。

显然，两个方程中的第二个 \(\sum\) 可以用前缀和优化掉，此时三方，继续优化。然后定睛一看：写成前缀和形式之后，展开组合数，发现一派常数一派关于 \(j\) 一派关于 \(i-j\)，那不就是个卷积吗？！我当时害怕极了，我不会 FFT 呀！而且即使优化了，也是平方对数，还要乘个 \(T\)，也是过不去的样子。

然后发现这个三方的复杂度很虚伪，它实际上是 \(\mathrm O\!\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^{|son_i|}sz_{son_{i,j}}\sum\limits_{k=1}^{j-1}sz_{son_{i,k}}\right)\)，很跑不满三方。然后拿链、菊花、蒲公英、毛毛虫、随机树都试一遍，发现没有一个被卡掉的。事实上它是平方的。下面归纳证明 \(\mathrm T(n)\leq n^2\)。

1. 显然 \(\mathrm T(0)=0\)。
2. 假设 \(\forall i\in[0,x),\mathrm T(i)\leq i^2\)。设大小为 \(x\) 的树的树根的儿子子树大小分别为 \(a_{1\sim m}\)，则显然有 \(\mathrm T(x)=\sum\limits_{i=1}^m\mathrm T(a_i)+\sum\limits_{i=1}^ma_i\left(\sum\limits_{j=1}^{i-1}a_j+1\right)\)。根据假设有 \(\mathrm T(x)\leq \sum\limits_{i=1}^ma_i^2+\sum\limits_{i=1}^ma_i\left(\sum\limits_{j=1}^{i-1}a_j+1\right)=\sum\limits_{i=1}^ma_i\left(\sum\limits_{j=1}^ia_j+1\right)\leq \sum\limits_{i=1}^ma_ix\leq x^2\)。

综上，得证。

代码（要很多次取模，常数比较大，要开 \(\mathrm O_2\)）：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define X first
#define Y second
#define pb push_back
const int mod=1000000007;
const int N=1000;
int n;
int comb[N+1][N+1];
vector<pair<int,bool> > nei[N+1];
int dp[N+1][N+2];
int nw[N+1];
int sz[N+1];
void dfs(int x=1,int fa=0){
	sz[x]=1;
	dp[x][1]=1;
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i].X;bool z=nei[x][i].Y;
		if(y==fa)continue;
		dfs(y,x);
		sz[x]+=sz[y];
		if(z){
			for(int j=1;j<=sz[y];j++)(dp[y][j]+=dp[y][j-1])%=mod;
			for(int j=1;j<=sz[x];j++)nw[j]=0;
			for(int j=1;j<=sz[x];j++)for(int k=0;k<=sz[y]&&k<j;k++)
				(nw[j]+=1ll*dp[x][j-k]*dp[y][k]%mod*comb[j-1][k]%mod*comb[sz[x]-j][sz[y]-k]%mod)%=mod;
			for(int j=1;j<=sz[x];j++)dp[x][j]=nw[j];
		}
		else{
			for(int j=sz[y];j;j--)(dp[y][j]+=dp[y][j+1])%=mod;
			for(int j=1;j<=sz[x];j++)nw[j]=0;
			for(int j=1;j<=sz[x];j++)for(int k=0;k<=sz[y]&&k<=sz[x]-j;k++)
				(nw[j]+=1ll*dp[x][j+k-sz[y]]*dp[y][sz[y]-k+1]%mod*comb[sz[x]-j][k]%mod*comb[j-1][sz[y]-k]%mod)%=mod;
			for(int j=1;j<=sz[x];j++)dp[x][j]=nw[j];
		}
	}
}
void mian(){
	cin>>n;
	for(int i=1;i<=n;i++)nei[i].clear();
	memset(dp,0,sizeof(dp));
	for(int i=1;i<n;i++){
		int x,y;char z;
		cin>>x>>z>>y;
		x++,y++;
		if(z=='<')nei[x].pb(mp(y,0)),nei[y].pb(mp(x,1));
		else nei[x].pb(mp(y,1)),nei[y].pb(mp(x,0));
	}
	dfs();
	int ans=0;
	for(int i=1;i<=n;i++)(ans+=dp[1][i])%=mod;
	cout<<ans<<"\n";
}
int main(){
	comb[0][0]=1;
	for(int i=1;i<=N;i++)for(int j=0;j<=i;j++)comb[i][j]=((j?comb[i-1][j-1]:0)+(j<i?comb[i-1][j]:0))%mod;
	int testnum;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}