Codeforces #604 Div1 C. Beautiful Mirrors with queries

まーたCodeforcesの記事が遅れてる…。
http://codeforces.com/contest/1264/problem/C

問題

Nマスの双六がある。
さいころを振ると、各マスiでP[i]パーセントの確率で次に進める。
残りのケースでは、直前のチェックポイントマスまで戻される。

クエリとして、チェックポイントの有無の切り替えが行われる。
切り替え後の双六において、ゴールに至るさいころ回数の期待値を求めよ。

解法

2つのマスを連続して通り抜けるのにかかるさいころ回数の期待値を求める合成の仕方を考えれば、SegTreeを用いて区間に関する合成も可能になる。
これを用いて、チェックポイントのあるマスから、次のチェックポイントに至るマスまでの区間を抜ける期待値の総和を求めよう。
クエリ毎に区間が分割か併合されるので、その差分の変化だけを適宜求めればよい。

const ll mo=998244353;

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;
}


template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		if(l.second==0) return r;
		if(r.second==0) return l;
		V P;
		P.first=(l.first+l.second*r.first)%mo;
		P.second=l.second*r.second%mo;
		return P;
	};
	
	SegTree_1(){val=vector<V>(NV*2,{0LL,0LL});};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {0LL,0LL};
		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]);
	}
};
SegTree_1<pair<ll,ll>,1<<18> st;
int N,Q;

ll count(int a,int b) {
	auto p=st.getval(a,b);
	return p.first*modpow(p.second)%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	
	FOR(i,N) {
		cin>>x;
		st.update(i,{1LL,x*modpow(100)%mo});
	}
	set<int> S;
	S.insert(0);
	S.insert(N);
	ll ret=count(0,N);
	
	FOR(i,Q) {
		cin>>x;
		x--;
		if(S.count(x)) {
			auto it=S.find(x);
			int a=*prev(it);
			int b=*next(it);
			ret-=count(a,x);
			ret-=count(x,b);
			S.erase(x);
			ret+=count(a,b);
		}
		else {
			auto it=S.lower_bound(x);
			int b=*it;
			int a=*prev(it);
			ret-=count(a,b);
			S.insert(x);
			ret+=count(a,x);
			ret+=count(x,b);
		}
		ret=(ret%mo+mo)%mo;
		cout<<ret<<endl;
	}
	
}

まとめ

これミラー云々とかの設定要るんかな…。