これは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; }
まとめ
今年もお疲れ様でした。