Autumn Festも解いてない問題があるので練習。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_09
先日のWUPC2の問題と似ている。
もちろんimos法の問題。
smallは何も考えず指示通り足せばいいだけ。
本番もsmallはそれで取れた。Largeが問題だね。
WUPC2は指示がN=10^5、サイズがS=500までだったけど、今回は指示がQ=10^6、サイズがN,M,D=1000程度とデータが1ケタ大きい。
WUPC2の問題はO(NS)でも間に合ったけど、今回はO(QN)だと間に合わない。
よって今回はもっと計算量を落とさないといけない。
そこで解説にある通り、2次元のimos法。
これだと2次元範囲への加算がO(1)で処理できる。
ただ今回は2次元の加算がD段ピラミッド状に積み重なっているので、積み重ね分を処理するとO(D)になってしまう。
そこで、解説にある+1が並ぶ左下方向と、-1が並ぶ右下方向のimos法を先に行い、その結果を2次元でimos法を取ると、O(Q+NM)程度で処理できる。
int N,M,Q; int MU[3]; int AD[3]; int PA,PB,PD; int PI[3005][3005]; int MI[3005][3005]; ll IMO[3005][3005]; ll X[3005][3005]; void solve() { int x,y,i,j,p,rr,TM,TTC,dep,res; ll ret; GET3(&N,&M,&Q); GET3(&PA,&MU[0],&AD[0]); GET3(&PB,&MU[1],&AD[1]); GET3(&PD,&MU[2],&AD[2]); FOR(i,Q) { //加算分 PI[999+PA-PD+1][999+PB]++; PI[999+PA+PD+1][999+PB]--; PI[999+PA+1][999+PB+PD]++; PI[999+PA+1][999+PB-PD]--; //減算分 MI[999+PA-PD+1][999+PB+1]--; MI[999+PA+PD+1][999+PB+1]++; MI[999+PA+1][999+PB+PD+1]++; MI[999+PA+1][999+PB-PD+1]--; PA=(PA*MU[0]+AD[0])%N+1; PB=(PB*MU[1]+AD[1])%M+1; PD=(PD*MU[2]+AD[2])%max(N,M)+1; } ZERO(X); //左下に加算 FOR(i,6000) { y=(i<=3000)?i:3000; x=(i<=3000)?0:(i-3000); p=0; while(y>=0 && x<=3000) { p+=PI[x][y]; IMO[x][y]+=p; x++;y--; } } //右下に加算 FOR(i,6000) { y=(i<=3000)?i:0; x=(i<=3000)?0:(i-3000); p=0; while(y<=3000 && x<=3000) { p+=MI[x][y]; IMO[x][y]+=p; x++;y++; } } ll PP=1000000007; ll MO=1000000009; FOR(x,3000) { p=0; if(x==0) FOR(y,3000) X[x][y]=(p=(p+IMO[x][y])%MO); else FOR(y,3000) X[x][y]=(X[x-1][y]+(p=(p+IMO[x][y])%MO))%MO; } ll hash=0; FOR(x,N) FOR(y,M) hash = (hash*PP+X[1000+x][1000+y])%MO; _P("%lld\n",hash); }
まとめ
2次元のimos法か、勉強になった。
WUPC2の時といい、imos法も色々な適用方法があるのね。