Description
Stack has an array $ a $ of length $ n $ such that $ a_i = i $ for all $ i $ ( $ 1 \leq i \leq n $ ). He will select a positive integer $ k $ ( $ 1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor $ ) and do the following operation on $ a $ any number (possibly $ 0 $ ) of times.
- Select a subsequence $ ^\dagger $ $ s $ of length $ 2 \cdot k + 1 $ from $ a $ . Now, he will delete the first $ k $ elements of $ s $ from $ a $ . To keep things perfectly balanced (as all things should be), he will also delete the last $ k $ elements of $ s $ from $ a $ .
Stack wonders how many arrays $ a $ can he end up with for each $ k $ ( $ 1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor $ ). As Stack is weak at counting problems, he needs your help.
Since the number of arrays might be too large, please print it modulo $ 998,244,353 $ .
$ ^\dagger $ A sequence $ x $ is a subsequence of a sequence $ y $ if $ x $ can be obtained from $ y $ by deleting several (possibly, zero or all) elements. For example, $ [1, 3] $ , $ [1, 2, 3] $ and $ [2, 3] $ are subsequences of $ [1, 2, 3] $ . On the other hand, $ [3, 1] $ and $ [2, 1, 3] $ are not subsequences of $ [1, 2, 3] $ .
\(3\leq n\leq 10^6\) .
Solution
不妨设 \(x\) 为总共删的数的个数，\(p_i\) 表示 \(i\) 是否被删，考虑什么样的序列是合法的。
-
\(x=2k\)，则充要条件为存在 \(i\) 使得 \(p_i=0\) 且 \(i\) 之前和之后都有恰好 \(k\) 个 \(1\)。
-
\(x>2k\)，则如果不存在一个 \(i\) 使得 \(p_i=0\) 且 \(i\) 之前和之后都有至少 \(k\) 个 \(1\)，那么最后一步一定不合法。如果一定存在，那么可以先把左右两边的 \(1\) 的个数删成 \([k,3k)\) 然后就必然合法。
所以一个序列合法的条件为存在一个 \(i\) 使得 \(p_i=0\) 且 \(i\) 之前和之后都有至少 \(k\) 个 \(1\)。
考虑用总数减去不合法的方案数，先把 \(2x\) 个 \(1\) 插进去，然后每个 \(0\) 只能插入左右各 \(k\) 个空，总方案数即为：
\[\binom{n}{x}-\binom{n-x+2k-1}{2k-1} \]时间复杂度：\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
const int kMaxN = 1e6 + 5, kMod = 998244353;
int n;
int fac[kMaxN], ifac[kMaxN], inv[kMaxN];
constexpr int qpow(int bs, int64_t idx = kMod - 2) {
int ret = 1;
for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
if (idx & 1)
ret = (int64_t)ret * bs % kMod;
return ret;
}
inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }
int C(int m, int n) {
if (m < n || m < 0 || n < 0) return 0;
return 1ll * fac[m] * ifac[n] % kMod * ifac[m - n] % kMod;
}
void prework() {
fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
for (int i = 2; i <= 1e6; ++i) {
inv[i] = 1ll * (kMod - kMod / i) * inv[kMod % i] % kMod;
fac[i] = 1ll * i * fac[i - 1] % kMod;
ifac[i] = 1ll * inv[i] * ifac[i - 1] % kMod;
}
}
int solve(int n, int k) {
int ret = 1;
for (int i = 2 * k; i <= n; i += 2 * k) {
inc(ret, sub(C(n, i), C(n - i + 2 * k - 1, 2 * k - 1)));
}
return ret;
}
void dickdreamer() {
std::cin >> n;
for (int i = 1; i <= (n - 1) / 2; ++i)
std::cout << solve(n, i) << ' ';
std::cout << '\n';
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
std::cin >> T;
prework();
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}