E. 2..3...4.... Wonderful! Wonderful! 解题思路

研究算法的都是什么天才，反正我不行

题意

题目链接

给定一个 ，和一个 的数组，对于每个 ，选择长度为 的子序列，并且删除头和尾的 个元素，求执行若干次上述操作（可以是 次）所能得到的最终数组个数

结论

按上式对一个 求出的答案，时间复杂度为 ，可以通过

思路

首先，考虑合法状态

固定 和 ，考虑从初始数组到最终数组的合法状态是怎么样的（以 为例）

初始数组：

最终数组（实例中为合法状态）：

基本定义

最终状态一定是由若干 块 （一段连续的被删除的数字）组成的，就比如上例中的 个块：

且块必然由空（一段连续的未被删除的数字）隔开

简单情况

仅考虑有且仅有 个空（此时必然有 个块）的情况：

若其中某个块的块的大小（块内数字个数）小于 ，考虑若干次操作后的最后一次操作，必然是删最后剩余的 个被删除的数字，此时有两种情况（定义块小的为小块，块大的为大块）：

• 最后剩余的 个待被删除的数字全在大块中：显然非法，此时这 个数正中间没有未被删除的数字，无法通过选择 的子序列删除

• 最后剩余的 个待被删除的数字既在大块也在小块中：显然非法，同上所述，无法在这 个数正中间找到未被删除的数字

若没有某个块的块的大小小于 ，即 个块的块的大小都大于等于 ：必然合法，我们只要保证最后剩余的 个待被删除的数字分别有 个在不同的块中即可，前面的操作我们可以有很多种方法去构造：

如上图所示的 个块（不妨设左块为小块，右块为大块），我们只需让左块的红色部分和右块去删即可，直到左块只剩下蓝色部分，再让右块自己删到剩下 个数（具体而言就是左边取 个右边取 个）

简单情况结论：合法状态当且仅当 个块的大小（块内数字个数）都大于等于

一般情况

我们注意到简单情况结论，其等价形式即为：存在一个空，其左右块大小均大于等于

对于一般情况，对比简单情况，无非就是多了空和块

因此拓展一下：“空的左右块大小均大于等于 ”也可以是“空的左右待删数字个数均大于等于 ”（因为既然块都可以，那若干块当然也可以），由此得到本题的重要结论：

一般情况结论：合法状态当且仅当存在一个空，其左右待删数字个数都大于等于

对于上述结论，考虑反面“不存在空，其左右待删数字个数都大于等于 ”，那么可以按简单情况（若根本不存在空，显然无解）考虑，考虑最后删除的 个数字，此时必然无解（证略），于是便论证了该结论的完备性

其次，考虑计算

固定删除元素的个数（设共删去 个数），计算合法状态个数

正难则反，正着直接计算合法状态情况太多易重复，考虑先计算所有最终状态，再减去非法状态

最终状态总个数：

非法状态：设 表示待删数字，内部数字为编号

非法状态即“不存在空，其左右待删数字个数都大于等于 ”，也就是“即使存在空，其左右待删数字个数都小于 ”，那么也就是仅在 可以存在若干最终状态的数字：

问题转化为将 个数放置在 个格子里（可以放 个）的方案数。经典问题，借物隔板法，得非法状态方案数为：

综上得，当固定删除元素的个数（设共删去 个数）时，合法状态方案数为：

最终对于固定 和 而言，枚举 并累加即可（注意可以一次也不操作，所以原始数组也算一种答案），即得：

枚举 即得对于 的答案

朴实无华的代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
int fac[N],facinv[N];
inline int C(int a,int b){return 1ll*fac[a]*facinv[b]%mod*facinv[a-b]%mod;}

void solve()
{
    int n;
    cin>>n;
    vector<int> ans(n,1);

    for(int k=1;k<=(n-1)/2;k++)
        for(int i=1;i<=n/(2*k);i++)
            ans[k]+=C(n,2*k*i)-C(n-2*i*k+2*k-1,2*k-1),ans[k]%=mod;

    for(int k=1;k<=(n-1)/2;k++)
        cout<<(ans[k]+mod)%mod<<" \n"[k==(n-1)/2];
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);

    fac[0]=1;
    for(int i=1;i<=1000000;i++)
        fac[i]=1ll*i*fac[i-1]%mod;
    facinv[1000000]=490058372;
    for(int i=999999;i>=0;i--)
        facinv[i]=1ll*facinv[i+1]*(i+1)%mod;

    int T=1;
    cin>>T;
    while(T--)
        solve();
    return 0;
}