square869120Contest #2 : F - Range Sum Queries

妙に手間取った。
http://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_f

問題

整数A,B,Cが与えられる。
A要素からなる配列aの初期値をa[i]=B^iとしよう。

配列a[i]を直前のsum(a[0..i])で置き換える、という動作をC回行う。
動作完了後、aの最後の要素はいくつになるか。

解法

a[i]が最終的にa[N-1]にどれだけ寄与するかを考えると、回寄与することがわかる。
(パスカルの三角形を少し傾けた形)

よってを答えればよい。
Combinationを愚直に計算すると間にあわないので、累乗計算を適度にサボっておこう。

ll A,B,C;
ll mo=1000000007;
map<ll,ll> PH;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	return PH[P_]*modpow(PH[Q_])%mo*modpow(PH[P_-Q_])%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>A>>B>>C;
	
	ll a=1;
	FOR(i,403030) {
		PH[i]=a;
		a=a*(i+1)%mo;
	}
	
	if(C>=302020) {
		a=1;
		for(i=C-101010;i<=C+101010;i++) {
			PH[i]=a;
			a=a*(i+1)%mo;
		}
	}
	
	ll tot=0;
	ll NB=1;
	FOR(x,A) {
		tot += NB*(comb(C-1+A-1-x,A-1-x)%mo)%mo;
		NB=NB*B%mo;
	}
	cout<<tot%mo<<endl;
}

まとめ

なんかこのコンテスト妙に手こずるなぁ。