AtCoder ARC #023 : C - タコヤ木

これは本番かなりの速さで解けた。ミスで2WA取ったけど…。
http://arc023.contest.atcoder.jp/tasks/arc023_3

問題

N個の正の整数からなる数列A[i]が与えられる。
このうち一部の値は不明である(その場所には-1が入れてある)。

A[i]が-1の場所に正の整数を入れて生成できる、単調増加なA[i]の組み合わせ数を求めよ。

解法

既知の値A[x],A[y]に挟まれた"A[x], -1, -1, -1, A[y]"のような部分列を考える。
これはA[x]～A[y]の(A[y]-A[x]+1)通りの数を-1の数(y-x)だけ分配する重複組み合わせである。
よって、-A[x]+1} H_{y-x} = {}_{A[y]-A[x] + y-x} C_{y-x}]を上記部分列を見つけるたびに掛け合わせればよい。
ただしA[x] > A[y]の場合は答えが0になる点に注意。

上記重複組み合わせはy-x < Nなので、1～Nのmod 1000000007における逆数を先に求めておけばO(N)で計算できる。
よって部分列の取得にO(N)、重複組み合わせ計算にO(N)なのでO(N^2)で計算可能。

int N;
ll A[2001];
ll mo=1000000007;

ll combi(ll N_, ll C_) {
	int i;
	const int num=5000;
	static ll rev[num+1],revt[num+1];
	
	if(rev[1]==0) {
		rev[1]=1; for(i=2;i<=num;i++) rev[i]=rev[mo%i]*(mo-mo/i)%mo;
		revt[0]=1; for(i=1;i<=num;i++) revt[i]=revt[i-1]*rev[i]%mo;
	}
	ll ret=revt[C_];
	FOR(i,C_) ret = (ret * ((N_-i)%mo))%mo;
	return ret;
}

ll dodo(ll dif, ll cnt) {
	return combi(dif+cnt-1,cnt);
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll ret=1;
	x=0;
	for(i=1;i<N;i++) {
		if(A[i]>=0) {
			if(A[i]<A[x]) ret=0;
			else {
				ret = ret*dodo(A[i]-A[x]+1,i-x-1)%mo;
				x=i;
			}
		}
	}
	cout << ret << endl;
	
}

まとめ

凡ミス2WAがもったいないな…。