列表

详情

NC215137. Antinomy与紫水宫

描述



沉迷《原初幻想41》的冒险者Antinomy来到了紫水宫——红玉海海底的一座古老宫殿，翠水之民的公主红玉曾被困在这里，光之战士将她解决了出来，并鼓励她带领族人拥抱地面上的变化。

紫水宫附近有许多海沟，Antinomy骑着肥鸡飞的时候发现迷路了。海沟可以看成是一棵树状的结构，共有个结点，每个结点就是一个路口，叶子结点就是走不下去的死胡同路口。

Antinomy想在每个结点上放不同颜色的便携式以太之光水晶，共有种颜色，每种颜色的以太之光的数量都是无限的（生产系玩家有钱），为了摆脱迷路的困境，Antinomy希望对于树上每对结点和，如果到的最短距离小于，那么和上放的以太之光水晶必须是不同颜色的。

Antinomy想知道有多少种满足这个要求的方案，由于答案可能很大，所以请输出答案对取模的结果。

提示：
1. 树上结点间的最短距离在某种意义上是可以直接确定的
2. 考虑用一些排列组合的方法加速运算，每个节点的贡献也许与颜色数量和其子树大小有关
3. 取模运算满足：
(a + b) % p = (a % p + b % p) % p 
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p 
a ^ b % p = ((a % p)^b) % p 
((a+b) % p + c) % p = (a + (b+c) % p) % p 
((a*b) % p * c)% p = (a * (b*c) % p) % p
(a + b) % p = (b+a) % p
(a * b) % p = (b * a) % p
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

输入描述

第一行输入两个整数和，表示有个结点和种颜色的以太之光水晶。
接下来行每行输入两个整数和，表示到相连。




输出描述

输出一行一个整数表示方案数量，由于答案可能很大，所以请输出答案对取模的结果。

示例1

输入: 

4 4
1 2
2 3
2 4

输出: 

24

示例2

输入: 

4 3
1 2
2 3
2 4

输出: 

0

示例3

输入: 

5 7
1 2
2 3
3 4
3 5

输出: 

4200

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 77ms, 内存消耗: 6548K, 提交时间: 2021-12-09 21:40:03 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
vector<int>G[maxn];
int n;
ll m, dp[maxn];

void dfs(int fa, int u,int p) {
	ll k;
	if (p == 1)k = m - 1ll;
	else k = m - 2ll;
	for (auto v : G[u]) {
		if (v == fa)continue;
		dp[v] = k;
		k--;
		dfs(u, v,p + 1);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dp[0] = dp[1] = m;
	dfs(0, 1, 1);
	ll ans = 1;
	for (int i = 1; i <= n; i++) {
		if (dp[i] <= 0)ans = 0;
		else ans = ans * dp[i] % mod;
	}cout << ans << endl;
	return 0;
}

上一题

© 2025 nowcoder.com