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 总数然后除以

\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

。

于是答案是

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

直接算复杂度是

O(n^2)

的。显然把组合数拆一下变成

\frac {n!} {\binom n 2} \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)

。

代码

CPP

#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;
}

P14561 [CXOI2025] 我常常追忆过去

文章操作

相关推荐

评论

P14561 [CXOI2025] 我常常追忆过去