2..3...4.... Wonderful! Wonderful!_cf1930E分析与解答

https://codeforces.com/problemset/problem/1930/E

一开始没有思路的话，来考虑对一个确定的k，这个问题如何解答，倒着想，用一个01序列s表示最终数组a中每个元素在还是不在：
s_i=0代表a_i还在 

s_i=1代表a_i被删去

接着如果可以判断哪些s是可以达到的就好了，或者判断哪些s是不能达到的，想想后者有哪些特征？从现在起，考虑执行删去操作的次数大于0的情况，也就是不考虑最终数组a是其原本的情况，执行最后一次删除时，一个会在s中的一个点 i 左边创造k个0，右边创造k个0，那么，在最后的s中，一定能找到一个点i，其左边0的个数>=k，右边0的个数>=k，如果找不到就说明s一定不合法，另外，比较容易发现的一点时，最终s中0的个数一定是2k的倍数，这是因为每次执行删除操作删除2k个数。

最终的s合法的必要条件：
1.在整个s序列从左往右第k个0的位置i和从右往左第k个0的位置j之间，即(i,j)区间存在1

2.s中0的个数是2k的倍数

以上两个s合法的必要条件其实也是s合法的充分条件：考虑如何通过最终的s序列还原到全部是1的序列，在(i,j)中任意取一个1，之后不再关注s序列中其他的1（以下将他们从s中删去），我们用这个1就足以倒着一步一步让s序列变为全部为1的序列，此时的s序列为：
000....000(p个0）1 000....000(q个0），中间的1是我们关注的(i,j)内的那个1，现有p>=k且q>=k且p+q是2k的倍数，如果p=q，那么由于p+q是2k的倍数，得到p是k的倍数，且q是k的倍数，不断以1为中心复原就可以得到全部是1的序列，如果p不等于q，不妨让p>q，在q中先复原最靠右的k个0，这次操作复原的是p中哪些0待定，也就是放着这些0不变，之后得到 0...0(p中的0）1 000...00 (q中剩余的0） 1111..1(k个1），此时(p中的0+q中剩余的0)的个数一定是k+2k*t (t是大于等于0的整数)：

然后发现，由于r>t，刚才那次复原操作可以在p中取一段连续的k个0变成1， 之后使得这段左边的0的个数和右边的0个个数相等，并且是k的整数倍，那么复原方法就和p=q的情况类似了。

这是充分性的证明。

不满足以上两个条件的s序列有多少个？如果在s序列中有x个1，则这些1一定在 [i,j] 外，将[i,j]看成一个0，剩余的0有2(k-1)个，0共有y=2k-1个，将1与这些0排列，共C(x+y,x)种排列方式。总的s的排列方式有多少个？在n个数里选x个位置放1，共C(n,x)种方式，对于一个确定的k，x的个数为n-2k*t (t是大于0的整数，因为单独考虑不改变序列a的情况，所以t至少为1），也就是x有大约n/(2k)个值，而k按照有n个来算的话，对所有的k，x一共有大约n/1+n/2+n/3+..n/n个，这个和的值大约是nlogn，所以复杂度估计为nlogn。

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;const ll N=1e6+5,mod=998244353;
ll fact[N+5],inv[N+5];ll binpow(ll a,ll n){ll res=1;a%=mod;while(n){if(n&1) res=res*a%mod;a=a*a%mod;n>>=1;}return res;
}ll com(ll n,ll m){if(m<0 || m>n) return 0;if(n==m || m==0) return 0;ll res=fact[n]*inv[m]%mod*inv[n-m]%mod;return res;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);fact[0]=1;for(ll i=1;i<=N;i++) fact[i]=fact[i-1]*i%mod;for(ll i=0;i<=N;i++) inv[i]=binpow(fact[i],mod-2);//cout<<com(5,3)<<"\n";ll T;cin>>T;while(T--){ll n;cin>>n;for(ll k=1;k<=(n-1)/2;k++){ll ans=1;for(ll t=1;n-2*k*t>=0;t++){ll x=n-2*k*t;ans=((ans+com(n,x))%mod-com(x+2*k-1,2*k-1))%mod;}cout<<(ans+mod)%mod<<" ";}cout<<"\n";}return 0;
}