牛客国庆集训派对Day3___H Travel —— 连通 + 组合数

题目链接：点我点我点我

题目大意：

    题目较短，但第一次理解起来可能有点绕脑。最后要求的是不同的旅游方案数，也就是不同路线选取的方案数。

解题思路：

    一开始以为是图论，想了一下好像无从下口，看了一下题解原来是有规律可循，当$m==1$时答案为$1$，当$m>1$时就可以用$m?1$条边将整个图（连通的）分成$m$个区域，恰好对应题目中的$m$次旅游，也就是说每次旅游选取这$m$个区域里的一个，那么很显然结果我们就要乘以这个$m$的全排列，即旅游的顺序不同。
    然后考虑的是怎么选取这$m?1$条边，就是从$n?1$条边中任意选取，也就是$C（n?1，m?1）$，求个组合数。
    最后答案即为 $C（n?1，m?1）$$?$ $m！$

代码思路：

    看到数据范围，$mod$ 为 $1e9+7$，用逆元求组合数即可。

核心：对题目的理解，算得上是一道读题题吧，前提是会一点数论的知识。

#include<bits/stdc++.h>
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;printf("%lld\n", ans);}
}