Hardにしては簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=17921
問題
数列Xに対するハッシュ値を、h(X) = sum(X[i]*10^i)%1000000007で定める。
今N個のマスをC種の色で塗ることを考える。
初期状態は全マス0番の色で塗られている。
以下のクエリQ回分に順次答え、求めたハッシュ値からなる数列のハッシュ値を求めよ。
- 区間[L,R]のマスを色QCで上塗りする。
- 数列Pを、P[c] := 色cで塗られたマスの数 とし、そのハッシュ値を求めよ。
解法
クエリ毎にハッシュ値の差分更新をすることを考える。
色が変わるマス数を求められれば、Pの更新分だけハッシュ値を差分更新できる。
mapを使い、色が切り替わるマスの位置を覚えておけば、均しでmapの操作回数およびハッシュ値の差分更新回数はO(Q)であり、計算量はO(QlogQ)で済む。
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; } class ColorfulStrip { public: int recolor(int N, int C, int Q, int maxL, int seed) { ll state = seed; int i; vector<ll> F; ll cur=0; map<int,int> M; M[-1]=M[N]=0; M[0]=0; cur=N; while(Q--) { state = (state * 1103515245 + 12345)%(1LL<<31); int qlen = 1 + (state%maxL); state = (state * 1103515245 + 12345)%(1LL<<31); int L = state%(N+1-qlen); int R = L + qlen; state = (state * 1103515245 + 12345)%(1LL<<31); int NC = state%C; if(M.count(L)==0) { auto it=M.lower_bound(L); it--; M[L]=it->second; } if(M.count(R)==0) { auto it=M.lower_bound(R); it--; M[R]=it->second; } int CL=L; while(CL<R) { auto it=M.lower_bound(CL); int NCL=next(it)->first; (cur-=modpow(10,it->second)*(NCL-CL))%=mo; M.erase(CL); CL=NCL; } M[L]=NC; cur+=modpow(10,NC)*(R-L)%mo; cur=(cur%mo+mo)%mo; F.push_back(cur); } reverse(ALL(F)); ll ret=0; FORR(f,F) (ret=ret*10+f)%=mo; return ret; } }
まとめ
なんかSegTree使ってる人ちらほらいたけど、ない方がすっきり書ける気も。