题解：AT_agc070_b [AGC070B] Odd Namori

很厉害的题。

对于

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

的方案数之和，则我们有

f(n) = \sum_{i = 1} ^ n \binom{n - 1}{i - 1}f(n - i) (i - 1)! (-1) ^ {i - 1}

简单解释一下，我们枚举

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)

的复杂度解决问题。

CPP

// 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";
}

题解：AT_agc070_b [AGC070B] Odd Namori

文章操作

相关推荐

评论

题解：AT_agc070_b [AGC070B] Odd Namori