树上拓扑序计数

至至子的公司排队

https://ac.nowcoder.com/acm/contest/38630/F

F

较好的观感

树上拓扑序计数|树形DP

https://ac.nowcoder.com/acm/contest/38630/F

思路

每个公司是一棵树,然后每个公司可以看做连在一个虚拟的根上。每个公司的计算方案实际上就是计算这棵树的拓扑序的个数。用树形DP求解。

f[u]f[u] : 以u为根的子树的拓扑序数

sz[u]sz[u] : 以u为根的子树的大小(节点的数量)

当树为二叉树时,将两个子树v1,v2进行合并:即先把各子树的方案数乘起来算出总方案,然后考虑各子树元素的相对排列顺序,即在总的节点个数中选sz[v1]排在前面的sz[v1]个位置,剩下的排在后面,保证每颗子树的相对拓扑序不变。

f[u]=f[v1]f[v2]C(sz[v1]+sz[v2],sz[v1])f[u] = f[v1] \cdot f[v2] \cdot C(sz[v1] + sz[v2], sz[v1])

例子:u节点有四颗子树,子树大小分别为a, b, c, d,则方案数为:

f[u]=f[a]f[b]f[c]f[d]C(a+b+c+d,a)C(b+c+d,b)C(c+d,c)f[u] = f[a]\cdot f[b]\cdot f[c]\cdot f[d]\cdot C(a+b+c+d, a)\cdot C(b+c+d, b)\cdot C(c+d,c)

=f[a]f[b]f[c]f[d](a+b+c+d)!a!(b+c+d)!(b+c+d)!b!(c+d)!(c+d)!c!d!=f[a]\cdot f[b]\cdot f[c]\cdot f[d]\cdot \frac{(a+b+c+d)!}{a!(b+c+d)!}\cdot \frac{(b+c+d)!}{b!(c+d)!}\cdot \frac{(c+d)!}{c!d!}

=f[a]f[b]f[c]f[d](a+b+c+d)!a!b!c!d!=f[a]\cdot f[b]\cdot f[c]\cdot f[d]\cdot \frac{(a+b+c+d)!}{a!b!c!d!}

推广到一般树:

f[u]=(vson(u)f[v])(sz[u]1)!vson(u)sz[v]!f[u] = (\prod \limits_{v \in son(u)} f[v] ) \cdot \frac{(sz[u] - 1)!}{\prod \limits_{v \in son(u)}sz[v]!}

换一下形式:

f[u]=(sz[u]1)!vson(u)f[v]sz[v]!f[u] = (sz[u] - 1)! \cdot \prod \limits_{v \in son(u)} \frac{f[v]}{sz[v]!}

拓扑序数量还可以这样计算:

n!i=1n1sz[i]n! \cdot \prod \limits_{i = 1} ^ n \frac{1}{sz[i]}

代码1

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;

ll fac[N], inv[N];
ll ksm(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res % mod;
}
void solve()
{
	int n;
	cin >> n;

	ll ans = 1, tot = 1;
	int cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		int c;
		cin >> c;
		cnt += c;
		vector<vi> g(c);

		for(int j = 1; j < c; j++)
		{
			int u;
			cin >> u;
			u--;
			g[u].push_back(j);
		}

		vi sz(c, 1);
		vl f(c, 1);
		function<void(int)> dfs = [&](int u)
		{
			for(auto v : g[u])
			{
				dfs(v);
				sz[u] += sz[v];
				(f[u] *= f[v] * inv[sz[v]] % mod) %= mod;
			}
			(f[u] *= fac[sz[u] - 1]) %= mod;
		};
		dfs(0);
		(tot *= f[0] * inv[c] % mod) %= mod;
	}
	ans = ans * tot % mod * fac[cnt] % mod;
	cout << ans << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	fac[0] = 1;
	for(int i = 1; i < N; i++)
		fac[i] = fac[i - 1] * i % mod;
	inv[N - 1] = ksm(fac[N - 1], mod - 2);
	for(int i = N - 2; i >= 1; i--)
		inv[i] = (i + 1) * inv[i + 1] % mod;

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;

// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
template<class T>
T power(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm(x % mod)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(mod - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, mod - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = ll(x) * rhs.x % mod;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

void solve()
{
	int n;
	cin >> n;

	Z ans = 1;
	int tot = 0;
	for(int i = 0; i < n; i++)
	{
		int c;
		cin >> c;

		for(int j = 0; j < c; j++)
			ans *= ++tot;

		vector<vi> g(c);
		for(int j = 1; j < c; j++)
		{
			int u;
			cin >> u;
			u--;
			g[u].push_back(j);
		}

		vi sz(c, 1);

		function<void(int)> dfs = [&](int u)
		{
			for(auto v : g[u])
			{
				dfs(v);
				sz[u] += sz[v];
			}
			ans /= sz[u];
		};
		dfs(0);
	}

	cout << ans << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

拓扑序计数相关题目:

HDU4661 : http://acm.hdu.edu.cn/showproblem.php?pid=4661

全部评论

相关推荐

牛客928043833号:在他心里你已经是他的员工了
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
9
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务