yukicoder : No.1084 積の積

最近問題投稿者が多いのか、問題が多いし開催頻度も高いね。
https://yukicoder.me/problems/no/1084

問題

整数列Aが与えられる。
このAの部分列のうち積が10^9以下であるものの積を求めよ。

解法

Aに0が含まれる場合解が0なので、以下それ以外の場合を考える。
部分列の左端A[L]を総当たりし、右端Rをどこまで伸ばせるか考えよう。
以下のコードはSegTreeを二分探索しているが、しゃくとり法の方がシンプルにできるようだ。

右端A[L...R]が求まると、長さm=R-L+1に対しA[L+i]は(m-i)回だけ解に掛けられることになる。
あとは各値A[i]が何回解に掛けられるかP[i]を累積和の要領で求めて行こう。
最後にA[i]^P[i]の積を求めればよい。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return min(1LL<<30,l*r);};
	
	SegTree_1(){val=vector<V>(NV*2,1);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return 1;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N;
ll A[101010];
ll B[101010];
ll C[101010];
const ll mo=1000000007;

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

SegTree_1<ll,1<<18> st;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]==0) return _P("0\n");
		st.update(i,A[i]);
	}
	
	FOR(i,N) {
		x=i+1;
		for(j=20;j>=0;j--) {
			y=x+(1<<j);
			if(y>N) continue;
			if(st.getval(i,y)<1000000000) x=y;
		}
		j=x-i;
		B[i]+=j;
		C[i]++;
		C[i+j]--;
	}
	
	ll cur=0;
	int dec=0;
	ll ret=1;
	FOR(i,N) {
		cur+=B[i];
		dec+=C[i];
		ret=ret*modpow(A[i],cur)%mo;
		cur-=dec;
	}
	cout<<ret<<endl;
}

まとめ

本番尺取り法が頭から抜けていた。