P14561 [CXOI2025] 我常常追忆过去

· · 题解

感觉这个 trick 见过后面就完全没有难度。类似的在 ARC163D。

对于竞赛图来说，SCC 个数与下面问题的答案是相同的：

集合 S 的个数，满足 \varnothing \subset S \subseteq U = \{ 1, 2, \cdots, n \}，且对于 \forall u \in S, v \in U \setminus S，存在 u \to v 的边。

这是为什么，你考虑竞赛图缩点后仍然是竞赛图而且是 DAG，所以长成一个链状物，我们把这个东西重标号为 1 \to 2 \to \cdots \to k。不难发现 1 \sim k 恰好作为 S 的最大元出现一次，这对应了合法 S 有恰好 k 个。

不妨算 SCC 总数然后除以 2^{\binom n 2}，考虑拆贡献。枚举 \lvert S \rvert = i，要使划分合法，S 内部或是 U \setminus S 内部的边方向无所谓，方案数是 2 ^ {\binom i 2 + \binom {n-i} 2}；从 S 到 U \setminus S 的边只能是确定的；同时选出 S 的方案数是 \binom n i。

于是答案是

2^{-\binom n 2} \sum_{i=1}^n \binom n i 2 ^ {\binom i 2 + \binom {n-i} 2}

直接算复杂度是 O(n^2) 的。显然把组合数拆一下变成

2^{-\binom n 2} \cdot n! \sum_{i=1}^n \frac {2^{\binom i 2}} {i!} \times \frac {2^{\binom {n-i} 2}} {(n-i)!}

一个因数只与 i 相关，另一个只与 n - i 相关，卷积一下即可。复杂度是 O(n \log n)。

:::info[代码]

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using arr = array<int, 2>;
using vec = vector<int>;
using pii = pair<int, int>;
const int N = 1 << 22;
const int P = 998244353;
const int i2 = P + 1 >> 1;

int qPow(int x, int y) {
  int res = 1;
  for (; y; x = 1ll * x * x % P, y >>= 1)
    if (y & 1) res = 1ll * res * x % P;
  return res;
}
int add(int x, int y) { if ((x += y) >= P) x -= P; return x; }
int sub(int x, int y) { if ((x -= y) < 0) x += P; return x; }

namespace poly {
  const int G(3), iG(332748118);
  int tot, bit, r[N], itot, qp[N];
  void Init(int l) {
    qp[0] = tot = 1, bit = 0;
    while (tot <= l) tot <<= 1, ++bit;
    itot = qPow(tot, P - 2);
    F(i, 1, tot - 1) r[i] = (r[i >> 1] >> 1) | ((i & 1) << bit - 1);
  }
  void NTT(int *f, bool tp) {
    F(i, 1, tot - 1) if (i < r[i]) swap(f[i], f[r[i]]);
    for (int d = 1; d < tot; d <<= 1) {
      int w = qPow(tp ? iG : G, (P - 1) / (d << 1));
      F(i, 1, d - 1) qp[i] = 1ll * qp[i - 1] * w % P;
      for (int i = 0; i < tot; i += d << 1)
        F(j, 0, d - 1) {
          int x = f[i | j], y = 1ll * qp[j] * f[i | j | d] % P;
          f[i | j] = add(x, y), f[i | j | d] = sub(x, y);
        }
    }
    if (tp) F(i, 0, tot - 1) f[i] = 1ll * f[i] * itot % P;
  }
}

int m, op, fc[N], iv[N];
int f[N], g[N], h[N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> m >> op, fc[0] = 1;
  F(i, 1, m) fc[i] = 1ll * fc[i - 1] * i % P;
  iv[m] = qPow(fc[m], P - 2);
  dF(i, m, 1) iv[i - 1] = 1ll * iv[i] * i % P;
  F(i, 1, m) f[i] = g[i] = 1ll * qPow(2, 1ll * i * (i - 1) / 2 % (P - 1)) * iv[i] % P;
  g[0] = 1;
  poly::Init(m << 1);
  poly::NTT(f, 0), poly::NTT(g, 0);
  F(i, 0, poly::tot - 1) h[i] = 1ll * f[i] * g[i] % P;
  poly::NTT(h, 1);
  F(i, 1, m) {
    int z = qPow(i2, 1ll * i * (i - 1) / 2 % (P - 1));
    h[i] = 1ll * fc[i] * h[i] % P * z % P;
  }
  if (op == 1) F(i, 1, m) cout << h[i] << "\n";
  else {
    int ans = 0;
    F(i, 1, m) ans ^= h[i];
    cout << ans << "\n";
  }
  return 0;
}

:::