设数字 \(i\) 第一次拿到的时间为 \(t_i\),所求即为 \(E(\max\limits_{i = 1}^m t_i)\)。
施 min-max 容斥,有:
\[\begin{aligned}E(\max\limits_{i = 1}^m t_i) & = \sum\limits_{T \subseteq [1, m] \land T \ne \varnothing} (-1)^{|T| - 1} E(\min\limits_{j \in T} t_j) \\ & = \sum\limits_{T \subseteq [1, m] \land T \ne \varnothing} (-1)^{|T| - 1} \frac{n}{\sum\limits_{j \in T} a_j} \end{aligned}
\]
设 \(\sum\limits_{j \in T} a_j = k\) 的集合 \(T\) 的容斥系数 \((-1)^{|T| - 1}\) 之和为 \(f_k\),那么:
\[ans = \sum\limits_{i = 1}^n \frac{n}{i} \times s_i
\]
套路地,考虑生成函数 \(F(x) = -\prod\limits_{i = 1}^n (-x^{a_i} + 1)\),那么 \(f_i = [x^i] F(x)\)。而 \(F(x)\) 可以分治 NTT 求出。具体就是递归求 \(\prod\limits_{i = l}^r (-x^{a_i} + 1)\),然后得到 \([l, mid]\) 和 \([mid + 1, r]\) 的答案再合并,总时间复杂度就是 \(O(n \log^2 n)\)。
好像有先 exp 再求逆的 \(O(n \log n)\) 做法,但是我既不会 exp 也不会求逆,开摆。
code
// Problem: G - Collect Them All
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331)
// URL: https://atcoder.jp/contests/abc331/tasks/abc331_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
const ll mod = 998244353, G = 3;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, a[maxn], f[maxn], inv[maxn], r[maxn];
typedef vector<ll> poly;
inline poly NTT(poly a, int op) {
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
if (i < r[i]) {
swap(a[i], a[r[i]]);
}
}
for (int k = 1; k < n; k <<= 1) {
ll wn = qpow(op == 1 ? G : qpow(G, mod - 2), (mod - 1) / (k << 1));
for (int i = 0; i < n; i += (k << 1)) {
ll w = 1;
for (int j = 0; j < k; ++j, w = w * wn % mod) {
ll x = a[i + j], y = w * a[i + j + k] % mod;
a[i + j] = (x + y) % mod;
a[i + j + k] = (x - y + mod) % mod;
}
}
}
if (op == -1) {
ll inv = qpow(n, mod - 2);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * inv % mod;
}
}
return a;
}
inline poly operator * (poly a, poly b) {
a = NTT(a, 1);
b = NTT(b, 1);
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
a[i] = a[i] * b[i] % mod;
}
a = NTT(a, -1);
return a;
}
inline poly mul(poly a, poly b) {
int n = (int)a.size() - 1, m = (int)b.size() - 1, k = 0;
while ((1 << k) <= n + m + 1) {
++k;
}
for (int i = 1; i < (1 << k); ++i) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
poly A(1 << k), B(1 << k);
for (int i = 0; i <= n; ++i) {
A[i] = a[i];
}
for (int i = 0; i <= m; ++i) {
B[i] = b[i];
}
poly res = A * B;
res.resize(n + m + 1);
return res;
}
inline poly dfs(int l, int r) {
if (l == r) {
poly res(a[l] + 1);
res[0] = 1;
res[a[l]] = mod - 1;
return res;
}
int mid = (l + r) >> 1;
return mul(dfs(l, mid), dfs(mid + 1, r));
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld", &a[i]);
}
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
poly res = dfs(1, m);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + n * inv[i] % mod * res[i]) % mod;
}
ans = (mod - ans) % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Collect Thembeginner atcoder contest them beginner atcoder contest collect contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 334 beginner atcoder contest 328