CF1930E 题解

· · 题解

\textbf{CF1930E *2400}

  • 给你 n,k，有一个长度为 n 的数组 a，初始时 a_i=i。一次操作可以选择一个长度为 2k+1 的子序列，删除前后 k 个元素，留下中间的一个。对于 k \in [1,\lfloor \dfrac{n-1}{2} \rfloor]，求出如果进行任意次操作，能得到多少不同的数组，模 998244353。

容易发现 k 固定时，删除的元素数量 x 是 2k 的倍数。也就是说我们可以枚举 x 的值，复杂度将是调和级数的 \mathcal O(n \log n)。

考虑对于固定的 n,k,x，计算方案数量。我们思考一个问题：给你数组 a，判断它是否可以通过初始状态进行任意此操作得到。我们把删除记为 1，保留记为 0。

寻找充要条件。从 x=2k 入手，此时只需要存在一个 p，满足 a_p = 0 且小于 p 大于 p 都有恰好 k 个 1。

当 x > 2k 时，我们猜测上面的条件仍然充要，即存在一个 p，满足 a_p = 0 且小于 p 大于 p 都有至少 k 个 1。下面给出证明。

  • 必要性。

删除一些 1 不会增加 0 的数量，也不会增加 0 两边 1 的数量。故如果初始不存在 p 操作至 x=2k 时一定也不会存在 p，不合法。

  • 充分性。

我们找到 p 的位置。如果某一侧有 \ge 3k 个 1，显然我们可以从一边删除 2k 个。这样两边都会剩下 [k,3k) 个 1。因为两边 1 数量的总和是 2k 的倍数，所以一定存在一种方案把两边都删到恰好 k 个 1，再进行一次操作即可。

这个条件不好直接计数，考虑用总数 \dbinom{n}{x} 减去不合法的。考虑长度为 x 的全 1 串，往里插入 n-x 个 0。我们发现 0 只能插在两边 k-1 个 1 的旁边，否则插在中间 0 就会成为满足条件的 p。也就是说，0 有 2k 个位置可以插。那么我们就是要把 n-x 个 0 放入 2k 个位置，这是经典的组合数学问题，插板易得方案数量为 \dbinom{2k-1+n-x}{2k-1}。可以 \mathcal O(n) 预处理后 \mathcal O(1) 计算。

总时间复杂度 \mathcal O(n \log n)。

/**
 *    author: sunkuangzheng
 *    created: 15.02.2024 22:43:43
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e6+5,mod = 998244353;
using namespace std;
int T,n,f[N],g[N];
int qp(int a,int b){
    int r = 1;
    for(;b;b >>= 1,a = 1ll * a * a % mod) if(b & 1) r = 1ll * r * a % mod;
    return r; 
}void los(){
    auto C = [&](int n,int m){
        return (n < 0 || m < 0 || n < m ? 0 : 1ll * f[n] * g[m] % mod * g[n - m] % mod); 
    };
    cin >> n;
    for(int i = 1;i <= (n - 1) / 2;i ++){
        int ans = 0;
        for(int j = i * 2;j <= n;j += i * 2)
            ans = ((ans + C(n,j)) % mod - C(2 * i + n - j - 1,2 * i - 1) + mod) % mod;
        cout << ans + 1 << " ";
    }cout << "\n";
}int main(){
    f[0] = g[0] = 1,n = 1e6;
    for(int i = 1;i <= n;i ++) f[i] = 1ll * f[i - 1] * i % mod;
    g[n] = qp(f[n],mod - 2);
    for(int i = n - 1;i >= 1;i --) g[i] = 1ll * g[i + 1] * (i + 1) % mod;
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}