Codeforces #581 Div2 E. Natasha, Sasha and the Prefix Sums

これはDiv2Eにしては簡単。
http://codeforces.com/contest/1204/problem/E

問題

1がN個、-1がM個からなる数列Pを考える。
f(P)をprefixの総和の最大値とする。
Pとしてあり得るComb(N+M,N)通りの数列におけるf(P)の総和を求めよ。

解法

Pにおいてi番目の要素が最大値を更新するなら、f(P)が1増えるので、i番目の要素が更新するのは何通りかを考える。
それには、i番目が1であり、i番目までに登場する-1の数よりi番目までに登場する1の数が多ければよい。
O(N^2)でも間に合うので、iを総当たりしつつ、そこまでに出てくる1の数を総当たりすれば十分。

int N,M;
ll mo=998244853;

ll comb(int P_,int Q_) {
	static const int N_=4002;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ret=0;
	for(int ps=1;ps<=N;ps++) {
		ll sum=0;
		for(int step=ps;step<=N+M;step+=2) {
			int np=ps+(step-ps)/2;
			int nm=(step-ps)/2;
			if(np>N || nm>M) continue;
			ll aft=comb(N-np+M-nm,N-np);
			np--;
			ll bef=comb(np+nm,np)-comb(np+nm,np+1)+mo;
			
			//cout<<ps<<step<<np<<nm<<" "<<bef<<" "<<aft<<endl;
			(ret+=aft*bef)%=mo;
			
		}
	}
	cout<<(ret%mo+mo)%mo<<endl;
}

まとめ

今年もお疲れ様でした。