think-cell Round 1 : E. 2..3...4.... Wonderful! Wonderful!

こっちもコードが短め。
https://codeforces.com/contest/1930/problem/E

問題

整数N,Kが与えられる。

以下の問題を考える。

A[i]=iであるN要素の整数列がある。
ここから、連続する2K+1要素を選び、頭K要素と後ろK要素を削除する、ということを繰り返せるとする。
残されたAは何通りあるか。

K=1～N/2のそれぞれについて、上記問題に答えよ。

解法

削除を行う回数xを総当たりする。
削除されるのは連続するK要素が2x個なので、残る要素が(2x+1)箇所の領域に分配されると考えると、H(2x+1,N-2xK)が解に計上される。
ただし、うち2K箇所に残る要素が固まってしまうとダメなので、H(2K,N-2xK)だけ引く。

int T,N;
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=5400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		for(k=1;k<=(N-1)/2;k++) {
			ll ret=1;
			for(i=1;i*2*k<N;i++) {
				//中に(i-1)*2*k+1個以上
				ret+=hcomb(1+i*2*k,N-i*2*k);
				ret-=hcomb(2*k,N-i*2*k);
			}
			ret=(ret%mo+mo)%mo;
			cout<<ret<<" ";
		}
		cout<<endl;
	}
}

まとめ

こういうのは綺麗に数え上げられるといいよね。