列表

详情


NC19788. Travel

描述

魔方国有n座城市,编号为。城市之间通过n-1条无向道路连接,形成一个树形结构。
澜澜打算在魔方国进行m次旅游,每次游览至少一座城市。为了方便,每次旅游游览的城市必须是连通的。此外,澜澜希望游览所有城市恰好一次。
澜澜想知道有多少种旅游方案满足条件,两个方案不同当且仅当存在某一次旅游游览了不同的城市。
澜澜不会数数,所以只好让你来帮他数方案。

输入描述

第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。
每组数据第一行两个整数n,m ,接下来n-1行每行两个整数ai,bi表示一条道路 (1≤ ai,bi≤ n)。

输出描述

每组数据输出一行一个整数表示方案数对109+7取模的结果。

示例1

输入:

2
3 1
1 2
1 3
3 2
1 2
1 3

输出:

1
4

原站题解

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

C++11(clang++ 3.9) 解法, 执行用时: 205ms, 内存消耗: 464K, 提交时间: 2020-02-19 12:54:45

#include<iostream>
using namespace std;
const int mod=1e9+7;
int n,m;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		int a,b;
		for(int i=0;i<n-1;++i)
		{
			scanf("%d %d",&a,&b);
			
		}
		long long ans=1;
		for(int i=n-1;i>n-m;--i)
		{
			ans=1ll*i*ans%mod;
		}
		printf("%lld\n",1ll*ans*m%mod);
	}
}

C++14(g++5.4) 解法, 执行用时: 700ms, 内存消耗: 500K, 提交时间: 2020-04-15 00:04:22

#include<bits/stdc++.h>
#define ll long long 
const ll mod=1e9+7;
using namespace std;
int main()
{
    ll n,m,k,x,y;
    cin >> k ;
    while(k--){
    	cin >> n >> m ;
		for(ll i=1;i<n;i++){
			cin >> x >> y ;
		}
		ll t=1;
		for(ll i=n-1;i>n-m;i--){
			t=(t*i)%mod;
		}
		cout << (t*m)%mod << endl ;
	}
    return 0;
}

Pascal(fpc 3.0.2) 解法, 执行用时: 171ms, 内存消耗: 228K, 提交时间: 2018-10-03 20:31:54

const mm=1000000007;
var t,m,n,i,j,x,y,k,ans:longint;
begin
 readln(t);
for k:=1 to t do
 begin
  read(n,m);
for i:=1 to n-1 do
 read(x,y);
if m=1 then writeln(1)
else begin ans:=m;for i:=n-m+1 to n-1 do
 ans:=(ans*i) mod mm;
writeln(ans);end;
end;

end.
 

上一题