AGC005F Many Easy Problems

发表于 | 分类于

Description

有一棵\(n\)个点的树，假设有一个常数\(k(1\leq k\leq n)\)，我们从树中任意选出\(k\)个点（这样的方案数显然为\(\binom{n}{k}\)） ，并且选出这\(k\)个点之外的尽可能少的原树点使得这些点和那\(k\)个点的导出子图联通（显然这样的方案唯一），我们称这个导出子图的总点数为这个方案的价值。

对于每个\(k(1\leq k\leq n)\)，求出所有从树中选出\(k\)个点的方案的价值之和。

\(1\leq n\leq 200000\)，答案模\(924844033\)输出。

Solution

ao秒啊，，，

如果考虑那个导出子图中点的贡献，是肥肠苦难滴。那么我们尝试转化成边的贡献。

注意到那个导出子图一定是一棵树，所以点数等于边数加一。那个加一最后做出的总贡献显然为\(\binom{n}{k}\)，因此我们接下来考虑处理边的贡献就行了。

但直接考虑边的贡献还是不可做滴，所以考虑使用补集转换，用所有情况减去不做贡献的情况。不做贡献的话那么选出的\(k\)个点一定在那条边的两侧。因此对于每条边，如果其一侧的子树大小为\(a\)，那么这条边对答案的贡献为\(\binom{n}{k} - \binom{a}{k} - \binom{n - a}{k}\)。

可是要对所有\(k\)都求一遍的话，全都DFS一遍非常的不现实。硬骨头在于减号后面的东西，其意义就是每一个边的一侧大小为\(a\)，那么就要在总答案里减去一个\(\binom{a}{k}\)。因此我们考虑把每个边两侧的子树大小都放到一个桶\(b\)里，其中\(b_i\)表示大小为\(i\)的子树出现了多少次。那么最后答案要在\(n\binom{n}{k}\)的基础上减去一个： \[ a_k = \sum_{i = 1}^n b_i\binom{i}{k} \] 但是这个东西不好递推也不好卷积，我们尝试两边乘\(k\)再整理整理： \[ a_kk!=\sum_{i = 1}^n b_ii!\cdot\frac{1}{(i - k)!} \] 然而这还是一个不好递推也不好卷积的东西……但是我们采用一种传统艺能：把一个串反过来。因此我们定义\(c_i = \frac{1}{(n - i)!}\)，这样原式就化成了： \[ a_kk!=\sum_{i = 1}^n b_ii!c_{n - i + k} \] 显然有\(n - i + k + i = n + k\)，因此这个物事就可以卷积力，，，

但是模数除了是质数以外，好像题里面也没告诉别的。但是通过WolframAlpha可以发现这个模数减一之后是\(2^{21}\)的倍数，并且这个模数本身有一个原根为\(5\)，所以是一个相当优秀的NTT模数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using ll = long long;
const ll ha = 924844033;
const ll bs = 5;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll fac[200005], ifac[200005];
void process() {
  int n = 200000;
  fac[0] = 1;
  for(int i = 1; i <= n; i ++) fac[i] = (ll)i * fac[i - 1] % ha;
  ifac[n] = inv(fac[n]);
  for(int i = n - 1; i >= 0; i --) ifac[i] = (ll(i + 1)) * ifac[i + 1] % ha;
}
ll C(int n, int m) {
  if(n < m) return 0;
  ll ret = fac[n] * ifac[n - m] % ha;
  ret = ret * ifac[m] % ha;
  return ret;
}

int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int f = flip(bi, i);
    if(f < i) std::swap(A[f], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi_n = pow_mod(bs, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi_n = inv(xi_n);
    for(int i = 0; i < n; i += (L << 1)) {
      ll xi = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        A[j] = (x + (y * xi) % ha) % ha;
        A[j + L] = (x - (y * xi) % ha + ha) % ha;
        xi = xi * xi_n % ha;
      }
    }
  }
  if(flag) {
    ll inv_n = inv(n);
    for(int i = 0; i < n; i ++) A[i] = A[i] * inv_n % ha;
  }
}

std::vector<int> G[200005];
void add_edge(int u, int v) {
  G[u].push_back(v);
}
void ins_edge(int u, int v) {
  add_edge(u, v); add_edge(v, u);
}

ll a[800005], b[800005]; int siz[200005], n;
void dfs(int x, int fa = -1) {
  siz[x] = 1;
  for(int v : G[x]) {
    if(v != fa) {
      dfs(v, x);
      b[siz[v]] ++; b[n - siz[v]] ++;
      siz[x] += siz[v];
    }
  }
}

int main() {
  process();
  scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  dfs(1);
  for(int i = 0; i <= n; i ++) {
    b[i] = b[i] * fac[i] % ha;
    a[i] = ifac[n - i];
  }
  int bi = 0, len = 1;
  while(len <= 2 * n) {
    bi ++; len <<= 1;
  }
  NTT(a, bi); NTT(b, bi);
  for(int i = 0; i < len; i ++) a[i] = a[i] * b[i] % ha;
  NTT(a, bi, true);
  for(int i = 1; i <= n; i ++) {
    ll ret = (ll)n * C(n, i) % ha;
    ret = (ret - a[n + i] * ifac[i] % ha + ha) % ha;
    printf("%lld\n", ret);
  }
  return 0;
}