Codeforces #489 Div2 D. Nastya and a Game

またツメが甘い…。
http://codeforces.com/contest/992/problem/D

問題

N要素の整数列Aが与えられる。
Aの部分列のうち、全要素の積をp、和をsとしたとき、定数kに対しp/s=kとなるのは何通りか。

解法

左端を総当たりし、それに合わせ右端を列挙することを考えよう。
skの上限は2*10^18なので、pが2*(10^18)以上となるケースは考えなくてよい。
とすると、部分列に2以上の値が入るのは高々61個ということになる。

よって、pが増える位置に右端を順に最大61回まで伸ばしてみよう。
今p,sがある値だとする。次にpが増える、すなわちA[i]が2以上の値を部分列に含めるには、右端をa個伸ばせばいいとする。
だとするとp/s,p/(s+1),...,p/(s+a)の中にkがあるかどうかを判定することになる。
これはp/kを求めればO(1)で求められる。

まとめると、左端を総当たりし、右端をpが2*10^18を超えるまで伸ばしながら、pが増えるたびにp/s=kとなるsの有無を数えていけばよい。

int N,K;
ll A[202020];
ll S[202020];
int nex[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	x=N;
	for(i=N-1;i>=0;i--) {
		nex[i]=x;
		if(A[i]!=1) x=i;
	}
	
	ll ret=0;
	FOR(i,N) {
		int R=i;
		ll p=1;
		ll s=0;
		while(R<N) {
			if((double)p*A[R]>3e18) break;
			p*=A[R];
			s+=A[R];
			int add=nex[R]-R-1;
			if(p%K==0) {
				if(s*K<=p && p<=(s+add)*K) ret++;
			}
			
			s+=add;
			R=nex[R];
		}
	}
	
	
	cout<<ret<<endl;
}

まとめ

オーバーフロー判定を適当にやって落とした。