2018 Wannafly summer camp Day3--Travel
2018 Wannafly summer camp Day3--Travel
Enterprise_
发布于 2019-03-01 09:33:59
发布于 2019-03-01 09:33:59
Travel 描述 题目描述： 魔方国有n座城市，编号为1∼n1∼n1\sim n。城市之间通过n-1条无向道路连接，形成一个树形结构。
澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。
澜澜想知道有多少种旅游方案满足条件，两个方案不同当且仅当存在某一次旅游游览了不同的城市。
澜澜不会数数，所以只好让你来帮他数方案。 输入： 第一行一个整数t表示数据组数 (1≤t≤100)(1≤t≤100)(1\leq t\leq 100)。 每组数据第一行两个整数n,m(1≤m≤n≤105,Σn≤106)(1≤m≤n≤105,Σn≤106)(1\leq m\leq n\leq 10^5,\Sigma{n}\leq 10^6)，接下来n−1n−1n-1行每行两个整数ai,bi，ai,biai,bi，ai,bia_i,b_i，ai,bi表示一条道路 (1≤ai,bi≤n)(1≤ai,bi≤n)(1\leq a_i,b_i\leq n)。 输出： 每组数据输出一行一个整数表示方案数对109+7109+710^9+7取模的结果。
样例输入 2 3 1 1 2 1 3 3 2 1 2 1 3 样例输出 1 4
- 一开始看的时候，以为是图论，后面发现其实不是，这里的边其实并没有实际作用。因为题目只是要求在m次旅游中将n个城市都游历玩即可，所以用m-1条边将这个树划分为m个区域，这就代表了m次旅游，然后求其全排列就是答案 所以最终答案C(n-1,m-1)*m!
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 1 << 20;
const int mod = 1000000007;
int t, n, m, ta, tb;
ll c[maxn];
ll PowerMod(ll a, ll b, ll c) {
ll ans = 1;
a = a % c;
while (b>0) {
if (b % 2 == 1)
ans = (ans * a) % c;
b = b / 2;
a = (a * a) % c;
}
return ans;
}
void init(){//先打出阶乘，节省时间
c[1] = 1;
for (int i = 2; i <= maxn; i++)
{
c[i] = c[i - 1] * i%mod;
}
}
ll C(ll n, ll m){return c[n] * PowerMod(c[m] * c[n - m] % mod, mod - 2, mod) % mod;}
int main(void) {
scanf("%d", &t);
init();
while (t-- >0 ) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n - 1; i++)
scanf("%d%d",&ta,&tb);
if (m == 1) {
printf("1\n");
continue;
}
ll ans = C(n - 1, m - 1);
ans = (ans*c[m]) % mod;
cout << ans << endl;
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年08月06日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读