NowCoder 203H – Travel (排列组合)

Table of Contents

题意

地图为一棵树,进行m次旅游,每次游览至少一座城市。为了方便,每次旅游游览的城市必须是连通的。此外,所有城市恰好只浏览一次。求总方案数。

思路

树长什么样根本不影响题解。只要找到$m-1$条边把这棵树断开即可。答案为$$\binom{n-1}{m-1} \times m!$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
ll getInv(ll a, ll p) {
  ll d, x, y;
  exgcd(a, p, d, x, y);
  return d == 1 ? (x + p) % p : -1;
}
 
ll frac[100005] = {};
ll inv[100005] = {};
 
void init() {
  frac[0] = frac[1] = 1;
  for (int i = 2; i <= 100000; ++i) {
    frac[i] = frac[i - 1] * i % modulo;
  }
  for (int i = 0; i <= 100000; ++i) {
    inv[i] = getInv(frac[i], modulo);
  }
}
 
ll C(ll n, ll k) {
  return (frac[n] * inv[k] % modulo) * inv[n - k] % modulo;
}
 
int n = 0, m = 0, tmp = 0;
ll ans = 0;
 
int main() {
  init();
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; ++i) {
      scanf("%d%d", &tmp, &tmp);
    }
     
    ans = C(n-1, m-1) * frac[m] % modulo;
    printf("%lld\n", ans);
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注