yukicoder : No.2512 Mountain Sequences

なるほど。
https://yukicoder.me/problems/no/2512

問題

yukicoder : No.2511 Mountain Sequence - kmjp's blog
の発展問題。
上記問題が最大200000問与えられるので順次答えよ。

解法

g(N,M)の定義を考えると、以下が成り立つ。

• g(N,M+1)=g(N,M)+f(N,M+1)
• g(N,M)+g(N+1,M)=Comb(2*M,N+1)

よってg(N,M)から、N,Mを1増減させたときの値を計算するのはO(1)で可能。
そこでクエリを並べ替え、Mo's Algorithmで処理していこう。

int T;
int N[202020],M[202020];
vector<pair<int,int>> ev[505];
ll ret[202020];
const ll mo=998244353;



ll comb(ll N_, ll C_) {
	const int NUM_=1430001;
	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 F(ll n,ll m) {
	ll ret=0;
	for(int i=1;i<=m;i++) ret+=comb(2*(i-1),n-1);
	return ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(i,T) {
		cin>>N[i]>>M[i];
		ev[M[i]/500].push_back({N[i],i});
	}
	FOR(i,500) {
		sort(ALL(ev[i]));
		int CN=-1,CM=-1;
		ll cur=0;
		FORR2(n,e,ev[i]) {
			if(CN==-1) {
				CN=N[e];
				CM=M[e];
				cur=F(CN,CM);
			}
			else {
				while(CN<N[e]) {
					cur=(comb(2*CM,CN+1)-cur+mo)*(mo+1)/2%mo;
					CN++;
				}
				while(CM<M[e]) {
					(cur+=comb(2*CM,CN-1))%=mo;
					CM++;
				}
				while(CM>M[e]) {
					CM--;
					(cur+=mo-comb(2*CM,CN-1))%=mo;
				}
			}
			ret[e]=cur;
		}
	}
	FOR(i,T) cout<<ret[i]<<endl;
	
}

まとめ

クエリをMoで並べ替えるの、どうも見落としがち。