题解 P6478 【[NOI Online #2 提高组]游戏】

Daniel_yuan · 2020-04-25 15:50:05 · 题解

不知道怎么公式渲染炸了……可能是不支持两个美元的公式吧（已尽力修改）……可以手动进入博客看看。（造成的不便敬请谅解）

先安利一个二项式反演的公式：

注：十分抱歉，这个公式之前是错的，请注意右侧 (-1) 的指数是 (k-i)，与 n 是无关的，实际上这里的 n 是可以枚举到正无穷的。

不会证明，但是会用就行。

这个题先设 f[i][j] 表示 i 子树内，非平局对为 j 对的方案数。

考虑怎么转移，先不考虑 i，只考虑它的子树，那么方案数就是

直接枚举显然不行，考虑每遍历一棵子树就把答案并进去，那么就是 f[i][j+k]=\sum_{son}f[son][j]\times f[i][k] 。

这个式子乍一看是 n^3 的，但是如果卡 j,k 的上界就会变成 n^2，粗略的证明是每个点对 (x,y) 只会在 \text{LCA}(x,y) 有一个复杂度的贡献。具体的证明可以问问百度。（我也不记得是什么时候看到过这个东西了）

最后的时候再把 i 个贡献加进去，分别设 A[i],B[i] 为 i 子树内小 A/B 的节点个数，假设当前节点是小 A 的节点，那么就有 f[i][j]=f[i][j]+f[i][j-1]\times \max((B[i]-(j-1),0) 。即之前有 j-1 个非平局对，那么就会消耗掉 j-1 个小 B 的节点，所以现在还剩 B[i]-(j-1) 个小 B 的节点可用。类似的，如果当前的节点是小 B 的节点就把上文的 B 换成 A 即可。

至此我们就可以在 n^2 的时间复杂度内算出所有子树内选 k 个非平局对的方案数。

我们先设 G(k)=f[1][k]\times (\frac{n}{2}-k)!，也就是说先固定选出来的 k 个非平局对，然后把剩下的自由组合。

但是这样子会算重，因为自由组合也可能贡献非平局对。我们设 H(i) 表示恰好有 i 个非平局对的方案数，可以发现对于每个 H(i)，它对 G(k) 的贡献是 C_i^k\times H(i)。

举个栗子，假设 i=4,k=3 设这 i 个非平局对的编号为 1,2,3,4，那么就有可能 1,2,3 被计算在 f[1][k] 内，4 是自由组合出来的；也可能是 1,2,4 被计算在 f[1][k] 内，3 是自由组合出来的……即一共有 C_i^k 种情况。

那么我们就有 G(k)=\sum_{i=k}^m C_i^k\cdot H(i) ，回到一开始提到的二项式反演，套进去就可以计算得到 H(i) 。

不太会证明为什么可以这样，我只能通过这种套式子的方法来做，而且我认为 G(k) 是没有实际含义的，只是一个用来反演的工具。（毕竟说它是至少 k 个非平局对过于牵强，因为单拿恰好 k+1 个非平局对来看，就会被算进去 k+1 次）

代码如下：考场代码求轻喷

#include <bits/stdc++.h>
#define RI register int
typedef long long LL;
#define int LL

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

int const mod = 998244353, MAXN = 5005;
int f[MAXN][MAXN], g[MAXN];
int A[MAXN], B[MAXN];
char s[MAXN];
struct Edges { int to, next; } e[MAXN * 2];
int head[MAXN], tot;
int size[MAXN];
int frac[MAXN], invfrac[MAXN], inv[MAXN];

inline LL C(int n, int m) { return frac[n] * invfrac[m] % mod * invfrac[n - m] % mod; }

void Init(int Max) {
  frac[0] = invfrac[0] = 1;
  frac[1] = invfrac[1] = inv[1] = 1;
  for (RI i = 2; i <= Max; ++i) {
    frac[i] = frac[i - 1] * i % mod;
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    invfrac[i] = invfrac[i - 1] * inv[i] % mod;
  }
}

inline void addedge(int from, int to) {
  e[++tot] = (Edges){to, head[from]};
  head[from] = tot;
  e[++tot] = (Edges){from, head[to]};
  head[to] = tot;
}

void Dfs(int now, int fa) {
  if (s[now] == '0') ++A[now];
  else ++B[now];
  for (RI i = head[now]; i; i = e[i].next)
    if (e[i].to != fa) {
      Dfs(e[i].to, now);
      A[now] += A[e[i].to];
      B[now] += B[e[i].to];
    }
}

void Solve(int now, int fa) {
  size[now] = 0;
  f[now][0] = 1;
  for (RI i = head[now]; i; i = e[i].next)
    if (e[i].to != fa) {
      Solve(e[i].to, now);
      for (RI j = 0; j <= size[now] + size[e[i].to]; ++j) g[j] = 0;

      for (RI j = 0; j <= size[now]; ++j)
        for (RI k = 0; k <= size[e[i].to]; ++k)
          g[j + k] = (g[j + k] + f[now][j] * f[e[i].to][k] % mod) % mod;

      size[now] += size[e[i].to];
      for (RI j = 0; j <= size[now]; ++j)
        f[now][j] = g[j];
    }

  if (s[now] == '0') {
    for (RI i = size[now]; i >= 0; --i)
      if (B[now] - i > 0)
        f[now][i + 1] = (f[now][i + 1] + f[now][i] * (B[now] - i) % mod) % mod;
    if (f[now][size[now] + 1]) ++size[now];
  }
  else {
    for (RI i = size[now]; i >= 0; --i)
      if (A[now] - i > 0)
        f[now][i + 1] = (f[now][i + 1] + f[now][i] * (A[now] - i) % mod) % mod;
    if (f[now][size[now] + 1]) ++size[now];
  }
}

signed main() {

  FILEIO("match");

  ios :: sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n; cin >> n; Init(n);
  cin >> (s + 1);
  for (RI i = 1, x, y; i < n; ++i)
    cin >> x >> y, addedge(x, y);
  Dfs(1, 0);
  Solve(1, 0);
  for (RI i = 0; i <= size[1]; ++i)
    g[i] = f[1][i] * frac[n / 2 - i] % mod;
  for (RI i = 0; i <= n / 2; ++i) {
    int Ans = 0;
    for (RI j = i, op = 1; j <= size[1]; ++j, op = op * (mod - 1) % mod)
      Ans = (Ans + op * C(j, i) % mod * g[j] % mod) % mod;
    cout << Ans << " ";
  }
  cout << endl;

  return 0;
}

// created by Daniel yuan