题解：AT_agc070_b [AGC070B] Odd Namori

chroneZ · 2025-02-06 19:20:11 · 题解

很厉害的题。

对于 C^k 形式的贡献，有经典技巧是将其拆成 \sum \limits_{i = 0} ^ k \binom k i (C - 1)^{i}，从而转化为钦定 i \in [0, k] 个结构并带上 (C - 1)^i 的系数计算方案数的问题。

对于本题同理，我们考虑计算钦定若干个奇环的形态时，图 G 的方案数之和，容易发现这等价于题目所求。

但是还有一个限制是“图 G 中不存在偶环”，我们发现这不好处理，所以考虑对这个条件容斥，每个偶环有 -1 的容斥系数。那么干脆就同时钦定奇环和偶环的形态，假设我们钦定了 x 个奇环和 y 个偶环，那么带有 (-1)^y 的系数，对所有情况求和，即可解决 2^c 的贡献形式和“不存在偶环”这一限制。

也有一种思路是我们最后的贡献是 2^x\red{0^y}，然后这个东西可以转化为 (\sum\binom x i 1^i)(\sum \binom y i (-1)^i)，和上文中奇环带有系数 1，偶环带有系数 -1，然后转化为钦定意义下的问题是等价的。

假设我们钦定了点集 S 中的点形成了若干个环，则点集外的点的连边方案数是 (n - 1) ^ {n - |S|}（在 1 \notin S 的情况下是 (n - 1)^{n - |S| - 1}n）。问题来到怎么计算 S 内的点的方案数（每个偶环还要贡献 -1 的系数）。

注意到原题中“图 G 中不存在边 i \to p_i”的限制此刻比较棘手，大概率还需要一个容斥，因此我们先忽略这个限制试试。记 f(n) 表示 n 个点的集合 S 的方案数之和，则我们有

简单解释一下，我们枚举 i 表示钦定 S_1 所在的置换环的大小，\binom{n - 1}{i - 1} 是除 S_1 外的点选法的方案数，(-1)^{i - 1} 是偶环的系数，(i - 1)! 是长度为 i 的只有一个置换环的排列数。

一件令人惊喜的事情是，f(0) = 1, f(1) = 1, f(n) = 0(n \geq 2)。证明考虑归纳，对于 n \geq 2，有 f(n) = (n - 1)f(1)(n - 2)!(-1) ^ {n - 2} + f(0)(n - 1)!(-1) ^ {n - 1} = 0。也就是说，在不限制 i \to p_i 边的情况下，S 内部的方案数即为 [|S|\leq 1]。

现在再来考虑加上原限制。对于这条限制我们同样考虑容斥，即钦定一个边集 E'（E' 是点集 S 导出子图的边集的子集），容斥系数 (-1)^{|E'|}，由于我们需要 S 形成若干个环，所以显然 E' 应该构成了若干条链。显然可以将链缩成点，我们发现此时问题和刚才不限制 i \to p_i 边时完全一致（当然链长的奇偶性会导致一些系数变化），那么刚才的结论现在也是可以用的！即将链缩为点后，如果剩下的点数大于等于 2，则方案数为 0。

剩余点数等于 1 的情况对应的情况是简单的，即 E' 将 S 中的所有点连成了一条链。如果 S 大小为奇数，那么 |E'| 大小为偶数，最终的系数是 1，反之最终的系数也是 1。因此，当且仅当 S 在原图上形成了一条链，S 内部的方案数为 1。

我们统计原图上长为 k 的不含有 1 的链的数量 s_k，则这部分答案为 \sum \limits_{i = 1} ^ {n - 1} s_i (n - 1) ^ {n - i - 1}n。记 d_i 为 i 点的深度，d_1 = 0，则含有 1 的链对答案的贡献是 \sum \limits_{i = 1} ^ n (n - 1) ^ {n - d_i - 1}。注意还有 S = \varnothing 的情况，贡献是 (n - 1) ^ {n - 1} n。至此我们可以以 \Theta(n) 的复杂度解决问题。

// Such a destiny was not desired.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int mod = 998244353, N = 1e5 + 5;
namespace basic {
  template<typename T>
  inline int add(T x, T y) {return (x + y >= mod ? x + y - mod : x + y);}
  template<typename T, typename... P>
  inline int add(T x, P... y) {return add(x, add(y...));}
  inline int dec(int x, int y) {return (x - y < 0 ? x - y + mod : x - y);}
  inline void ad(int &x, int y) {x = add(x, y);}
  inline void de(int &x, int y) {x = dec(x, y);}

  inline int qpow(int a, int b) {
    int r = 1;
    while(b) {
      if(b & 1) r = 1ll * r * a % mod;
      a = 1ll * a * a % mod; b >>= 1;
    }
    return r;
  }
  inline int inv(int x) {return qpow(x, mod - 2);}

  int fac[N], ifac[N];
  inline void fac_init(int n = N - 1) {
    fac[0] = 1;
    for(int i = 1; i <= n; i++)
      fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = inv(fac[n]);
    for(int i = n - 1; i >= 0; i--)
      ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
  }
  int invx[N];
  inline void inv_init(int n = N - 1) {
    invx[1] = 1;
    for(int i = 2; i <= n; i++)
      invx[i] = 1ll * (mod - mod / i) * invx[mod % i] % mod;
  }
  inline int binom(int n, int m) {
    if(n < m || m < 0) return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
  }
}
using namespace basic;

int Pow[N];
int n, p[N], d[N], s[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  cin >> n;
  Pow[0] = 1;
  for(int i = 1; i <= n; i++) {
    Pow[i] = (ll)Pow[i - 1] * (n - 1) % mod;
  }
  for(int i = 2; i <= n; i++) {
    cin >> p[i];
    d[i] = d[p[i]] + 1;
    s[d[i]]++;
  }
  int ans = 0;
  for(int i = n - 1; i >= 1; i--) {
    s[i] += s[i + 1];
    ad(ans, (ll)s[i] * Pow[n - i - 1] % mod * n % mod);
  }
  ad(ans, (ll)Pow[n - 1] * n % mod);
  for(int i = 1; i <= n; i++) {
    ad(ans, Pow[n - d[i] - 1]);
  }
  cout << ans << "\n";
}