POJ 3690: Constellations - omochan's diary

蟻本に書いてあるように二次元hashをすればいいです。

hashといえばこの記事
http://hos.ac/blog/#blog0003
が有名ですが、ここに書いてあるように3つのmodでhashをとるようにしてみました。

注意：TLE解法です。

struct ll3 {
	ll v[3];
	ll3(ll a,ll b,ll c){v[0]=a;v[1]=b;v[2]=c;}
	ll3(ll a){v[0]=a;v[1]=a;v[2]=a;}
	ll3(){v[0]=0;v[1]=0;v[2]=0;}
	inline void operator=(const ll3& vs){rep(i,0,3)v[i]=vs.v[i];}
	inline void operator=(ll a){rep(i,0,3)v[i]=a;}
	inline ll3 operator+(const ll3& vs){ll3 res;rep(i,0,3)res.v[i]=v[i]+vs.v[i];return res;}
	inline ll3 operator-(const ll3& vs){ll3 res;rep(i,0,3)res.v[i]=v[i]-vs.v[i];return res;}
	inline ll3 operator*(const ll3& vs){ll3 res;rep(i,0,3)res.v[i]=v[i]*vs.v[i];return res;}
	inline ll3 operator%(const ll3& vs){ll3 res;rep(i,0,3)res.v[i]=v[i]%vs.v[i];return res;}
	inline void operator+=(const ll3& vs){rep(i,0,3)v[i]+=vs.v[i];}
	inline void operator-=(const ll3& vs){rep(i,0,3)v[i]-=vs.v[i];}
	inline void operator*=(const ll3& vs){rep(i,0,3)v[i]*=vs.v[i];}
	inline void operator%=(const ll3& vs){rep(i,0,3)v[i]%=vs.v[i];}
	inline ll3 operator+(ll a){ll3 res;rep(i,0,3)res.v[i]=v[i]+a;return res;}
	inline ll3 operator-(ll a){ll3 res;rep(i,0,3)res.v[i]=v[i]-a;return res;}
	inline ll3 operator*(ll a){ll3 res;rep(i,0,3)res.v[i]=v[i]*a;return res;}
	inline ll3 operator%(ll a){ll3 res;rep(i,0,3)res.v[i]=v[i]%a;return res;}
	inline void operator+=(ll a){rep(i,0,3)v[i]+=a;}
	inline void operator-=(ll a){rep(i,0,3)v[i]-=a;}
	inline void operator*=(ll a){rep(i,0,3)v[i]*=a;}
	inline void operator%=(ll a){rep(i,0,3)v[i]%=a;}
	inline bool operator==(const ll3& vs){int cnt=0;rep(i,0,3)cnt+=v[i]==vs.v[i];return cnt==3;}
	inline bool operator!=(const ll3& vs){int cnt=0;rep(i,0,3)cnt+=v[i]==vs.v[i];return cnt<=2;}
	friend ostream& operator<<(ostream& out,const ll3& vs){out<<"("<<vs.v[0]<<" "<<vs.v[1]<<" "<<vs.v[2]<<")";return out;}
};
bool operator<=(const ll3& vs1,const ll3& vs2){rep(i,0,3)if(vs1.v[i]!=vs2.v[i])return vs1.v[i]<=vs2.v[i];return true;}
bool operator<(const ll3& vs1,const ll3& vs2){rep(i,0,3)if(vs1.v[i]!=vs2.v[i])return vs1.v[i]<vs2.v[i];return false;}
const ll3 mod = ll3{1000000007, 1000000009, 1000000021};

int N, M, T, P, Q;
char s[1010];
int patterns[1110][1110];
int field[1110][1110];
ll3 has[1110][1110], tmp[1110][1110];

void compute_hash(int field[1110][1110], int N, int M) {
	rep(i, 0, N + 1) {
		fill(has[i], has[i] + M + 1, 0);
		fill(tmp[i], tmp[i] + M + 1, 0);
	}
	rep(i, 0, N) {
		ll3 h = 0, mul = 1;
		rep(j, 0, Q) {
			h = h * 2 + field[i][j]; h %= mod;
			mul *= 2; mul %= mod;
			//debug(i, j, field[i][j], h, mul);
		}
		for(int j = 0; j + Q <= M; j++) {
			tmp[i][j] = h;
			h = (h * 2 % mod - mul * field[i][j] % mod + field[i][j + Q] + mod) % mod;
		}
	}
	ll3 bmul = 1;
	rep(i, 0, Q) {
		bmul *= 2;
		bmul %= mod;
	}
	for(int j = 0; j + Q <= M; j++) {
		ll3 h = 0, mul = 1;
		rep(i, 0, P) {
			h = h * bmul % mod + tmp[i][j];
			mul *= bmul; mul %= mod;
		}
		for(int i = 0; i + P <= N; i++) {
			has[i][j] = h;
			h = (h * bmul % mod - mul * tmp[i][j] % mod + tmp[i + P][j] + mod) % mod;
		}
	}
}

int main() {
	for(int q = 1; ;q++) {
	scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);
	if(N == 0) break;
	rep(i, 0, N) {
		scanf("%s", s);
		rep(j, 0, M) {
			if(s[j] == '*') field[i][j] = 1;
			else field[i][j] = 0;
		}
	}
	multiset<ll3> unseen;
	rep(t, 0, T) {
		rep(i, 0, P) {
			scanf("%s", s);
			rep(j, 0, Q) {
				if(s[j] == '*') patterns[i][j] = 1;
				else patterns[i][j] = 0;
			}
		}
		compute_hash(patterns, P, Q);
		unseen.insert(has[0][0]);
	}

	compute_hash(field, N, M);
	for(int i = 0; i + P <= N; i++) {
		for(int j = 0; j + Q <= M; j++) {
			unseen.erase(has[i][j]);
		}
	}
	int ans = T - unseen.size();
	printf("Case %d: %d\n", q, ans);
	}
	return 0;
}

このll3っていうクラスは3つのlong longの値を保持するだけのクラスです。modは自動で取ってくれないのでオーバーフローには注意しないといけません。3つの値に対してそれぞれ異なるmodを取ることによってハッシュの衝突をなるべく避けようとしています。
2つのハッシュ値が等しいかどうかは、3つの値がすべて等しいかで判断します。
つまり2つのハッシュ値が異なると判断された場合は3つの値のうち1つ以上異なることになります。
ハッシュの衝突は異なるものを等しいと判断してしまう現象なので、異なるものをちゃんと異なるといえることが重要になります。
1つのmodに対して本来異なるのに等しいと判断してしまう確率はたいていの場合大体1/modで、さらにそれが3回起こる確率は
modが10^-9であれば10^-27乗のオーダーになるので、衝突することはほとんどないとみていいことがわかります。

ですが、3つのlong longの値に対してmodをとるので遅いしメモリも食います。制限時間の厳しい問題では使用すべきではないでしょう。実際上の解法もTLEしましたし。だからってhashを1つのmodでやるのは怖いしハッシュは加減が難しいですね…

まあ悪意の満ちたテストケース(基底を何個持ってきても衝突する)がない限り大丈夫なのでPOJではmod2^64を使います…