首页 > 代码库 > 【哈希】CDOJ1717 京电的神秘矩阵

【哈希】CDOJ1717 京电的神秘矩阵

技术分享

对每个矩阵里的元素用两个大素数做双关键字哈希,丢进set即可。

#include<cstdio>
#include<iostream>
#include<set>
using namespace std;
#define MOD1 1000000007ll
#define MOD2 1000000009ll
typedef long long ll;
ll m,n,a,b;
ll Quick_Pow(ll a,ll p,ll MOD){
	if(!p){
		return 1ll;
	}
	ll res=Quick_Pow(a,p>>1,MOD);
	res=res*res%MOD;
	if(p&1ll){
		res=(a%MOD*res)%MOD;
	}
	return res;
}
set<pair<ll,ll> >S;
int main(){
	cin>>m>>n>>a>>b;
	for(ll i=1ll;i<=m;++i){
		for(ll j=1ll;j<=n;++j){
			ll x1=Quick_Pow(a+j-1ll,b+i-1ll,MOD1);
			ll x2=Quick_Pow(a+j-1ll,b+i-1ll,MOD2);
			S.insert(make_pair(x1,x2));
		}
	}
	printf("%d\n",S.size());
	return 0;
}

【哈希】CDOJ1717 京电的神秘矩阵