P4099 [HEOI2013]SAO

n-1条边有向弱联通图拓扑序计数

咋做啊?

首先我们应该注意到是树,而不是那个阴间的npc问题

类似于一坨坨的序列合并...我们就要想是整个一坨合并还是插入合并?

这个题显然拓扑序列是可以两个子树之间穿插的,所以我们转移的时候就要用穿插的方式转移

$f_{i,j}$ 表示点i在拓扑序的j号位置的方案数是什么

转移时,对于一条连向儿子的边,u要么能放在v前,要么能放在v后

也就是说.......u.....v......,或者...v.....u......

这个其实限制了状态的转移,也就是那些状态能够转移过来

然后我们要分配儿子,因为我们还有兼具合并v的重任所以上组合数把!

钦定 $v<u$ 硬点u在拓扑序原来的排名为l,而合并之后的排名为k,所以前面的总可能是 $\binom{k-1}{l-1}$ ,就是l-1个点分在原子树里

紧接着会发现我们有 $siz[u]+siz[v]-k$ 个数还没用呢....因为我们枚举了原来的排名为l,所以 $siz[u]-l$ 就是原来放在另外拓扑序后面的数数量,所以我们再 $*\binom{siz[u]+siz[v]-k}{siz[u]-l}$ 表示我们把后面部分选好

f_{u,j}=\sum_{l<siz[v]}\sum_{k<l}f_{u,l}*f_{v,k}*\binom{j-1}{l-1}\binom{siz[u]+siz[v]-k}{siz[u]-l}

就是这个转移方程了

钦定 $v>u$

其实很对称啊,我们会发现之前组合数的部分都不用变,改变的是转移的范围

假设第一维枚举原来的点数,第二维枚举v向前给出多少个点的贡献(就是u新的排名会后移啊.....),因为此时v可能不会再影响u原来的排名后移了

第三维枚举的就是我们实际的比u多的rank,这里一开始自闭了一下, $dp_{v,k}$ 其实也可以表示v比u大k的方案..

总的来说,这个转移共有两个细节

计算新排名时要组合新排名前面的数和新排名之后的数
计算新排名的时候要仔细想想枚举什么,以及对应乘上的dp状态

按理说应该直接枚举新u的排名的,代码没有这样写

最后对了还有一个前缀和优化,仔细看看代码就会感觉是临时加上去的.....

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 1e3 + 7;
const int MAXM = 2e3 + 7;
int n, ccnt, T, home[MAXN], nxt[MAXM], to[MAXM], flg[MAXM];

inline void ct(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	flg[ccnt] = z;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

int dp[MAXN][MAXN], siz[MAXN], f[MAXN][MAXN], C[MAXN][MAXN], sum[MAXN][MAXN];
// ll fac[MAXN], ifac[MAXN];
inline void INIT() {
	C[0][0] = 1;
	for(int i = 1; i < MAXN; ++i) {
		C[i][0] = 1;
		for(int j = 1; j <= i; ++j) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
		}
	}
	return ;
}

inline void init() {
	memset(home, 0, sizeof(home));
	ccnt = 0;
	memset(dp, 0, sizeof(dp));
}

inline void add(int &x, ll y) {
	x += y;
	// printf("?%d?%d?\n", x, y);
	if(x > P)
		x -= P;
}

inline void dfs(int u, int F) {
	siz[u] = 1;
	dp[u][1] = 1;
	// printf("u is :%d?\n", u);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		// printf("u %d and back v %d?\n", u, v);
		for(int k = 1; k <= n; ++k)
			f[u][k] = 0;
		if(flg[i] == 1) {//之前边,u在v之前
			// printf("u is v front front is :%d back is :%d\n", u, v);
			for(int j = 1; j <= siz[u]; ++j) { //枚举u原来点数
				for(int k = 0; k <=  siz[v]; ++k) { //枚举v给出的贡献
					// for(int l = k + 1; l <= siz[v]; ++l) {
					int del = ((sum[v][siz[v]] - sum[v][k]) + P) % P;
					// printf("now we in:%d %d %dhad dp array u:%d v:%d\n", j, k, l, dp[u][j], dp[v][l]);
					add(f[u][j + k],
						1ll * del * dp[u][j] % P
						* C[j + k - 1][j - 1] % P
						* C[siz[u] + siz[v] - j - k][ siz[u] - j] % P);
					// printf("but each size is%d %dget ans:%d\n", siz[u], siz[v], f[u][j + k]);
					// }
				}
			}
		} else {//u在v之后
			// printf("u is v back front is :%d back is :%d\n", v, u);
			for(int j = 1; j <= siz[u]; ++j) { //枚举新u的点数
				for(int k = 1; k <= siz[v]; ++k) {
					// for(int l = 1; l <= k; ++l) {
					int del = ((sum[v][k]) + P) % P;
					// printf("now we in:%d %d %dhad dp array u:%d v:%d\n", j, k, l, dp[u][j], dp[v][l]);
					add(f[u][j + k],
						1ll * del * dp[u][j] % P
						* C[k + j - 1][j - 1] % P
						* C[siz[u] + siz[v] - j - k][siz[u] - j] % P) ;
					// printf("but each size is%d %d\n", siz[u], siz[v]);
					// }
				}
			}
		}
		siz[u] += siz[v];
		for(int k = 1; k <= n; ++k)
			dp[u][k] = f[u][k];
	}
	// printf("%d?\n", u);
	for(int i = 1; i <= n; ++i) {
		sum[u][i] = (sum[u][i - 1] + dp[u][i]) % P;
		// add(sum[u][i], sum[u][i - 1]);
		// add(sum[u][i], dp[u][i]);
		// printf("!%d??%d %d\n", sum[u][i], sum[u][i - 1], dp[u][i]);
	}
	return ;

}
char s[MAXN];
int main() {
	scanf("%d", &T);
	INIT();//大预处理
	// printf("%d %d %d\n", C[10][2], C[5][3], C[6][4]);
	while(T-- > 0) {
		init();
		scanf("%d", &n);
		for(int i = 1, x, y; i < n; ++i) {
			scanf("%d", &x);
			cin >> s;
			scanf("%d", &y);
			++x;
			++y;
			// printf("%d %d\n", x, y);
			//<说明x在y之前打
			if(s[0] == '<') {
				// puts("Y");
				ct(x, y, 1);
				ct(y, x, 0);
				//变向说明y在x之后
			} else {
				// puts("N");
				//x在y之后打
				ct(x, y, 0);
				ct(y, x, 1);
				//说明y在x之前打
			}
		}
		dfs(1, 0);
		int ans = 0;
		for(int i = 1; i <= n; ++i)
			add(ans, dp[1][i]);
		printf("%d\n", ans);
	}
	return 0;
}

zzz

夏晓光(loveJY)的博客

P3515 [POI2011]Lightning Conductor