Google Code Jam 2008 Round 1B : A. Crop Triangles

さて1Bも行きますか。
http://code.google.com/codejam/contest/32017/dashboard#s=p0

最大10万個の点の座標が与えられるので、３点選んで重心が格子点にくる組み合わせの数を求める。
重心がいっしょでも、３点の選び方が別なら別カウントする。
10万個の座標は直接与えられるわけではなく、漸化式で与えられる。

ただ、この問題は特に漸化式の特徴を活かす必要はない。
３つの点のX座標・Y座標の合計が3の倍数なら、重心が格子点になる。
まず、10万個の点をX座標を３で割った余りが0,1,2、Y座標を３で割った余りが0,1,2の掛けて9通りに分類する。

このうち、同じ分類から３点選ぶか、X・Y座標の和が３の倍数となる異なる３つの分類から１点ずつ計３点選べば重心が格子点にくる。
前者は分類の数nに対しだし、後者は３つの分類の積になる。

s64 n,A,B,C,D,X,Y,M;
s64 num[9];

void solve(int _loop) {
	int i,j,k,l;
	s64 res;
	
	scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&n,&A,&B,&C,&D,&X,&Y,&M);
	ZERO(num);
	FOR(i,n) {
		num[(X%3)*3+(Y%3)]++;
		X = (A*X+B)%M;
		Y = (C*Y+D)%M;
	}
	
	res=0;
	FOR(i,9) FOR(j,9) FOR(k,9) {
		if(i==j && i==k) {
			res+=num[i]*(num[i]-1)*(num[i]-2)/6;
			continue;
		}
		if(j<=i || k<=j) continue;
		if((i+j+k)%3!=0) continue;
		if((i/3+j/3+k/3)%3!=0) continue;
		res += num[i]*num[j]*num[k];
	}
	
	_PE("Case #%d: %lld\n",_loop,res);
}

まとめ

最初は漸化式の特徴を使うかと思ったけど、点が100000個までなのでO(N)なら十分解けるね。