kmjp's blog

競技プログラミング参加記です

Autumn Fest 2012 : I - Pyramid

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法も色々な適用方法があるのね。