hash这么难过后面的点吗?
查看原帖
hash这么难过后面的点吗?
826228
SSHHXD楼主2024/8/27 15:22

hash这么难过后面的点吗?还是说我哪里写的不对,或者做法太劣?写了个六哈希才过。。

#include <bits/stdc++.h>
#define int long long
using namespace std;
bitset<1100100> has_as;
bitset<1100100> has_bs;
bitset<1100100> has_cs;
bitset<150010> has_ds;
bitset<1234567> has_es;
bitset<19260822> has_fs;

typedef long long ll;
const int mod1s = 1099933;
const int base1s = -999961;
const int base2s = 1000000007;
const int mod2s = 1045157;
const int mod3s = 146521;
const int base3s = -31;
const int base4s = 1134503;
const int mod4s = 1234547;
const int mod5s = 19260817;
const int base5s = 114514;

bool zhi(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return false;
	}
	return true;//这个只是找base和mod用的
}

ll readasd(){
	int s=0,f=1;char t=getchar();
	while('0'>t || t>'9'){
		if(t=='-')f=-1;
		t=getchar();
	}
	while('0'<=t&&t<='9'){
		s=(s<<1)+(s<<3)+t-'0';
		t=getchar();
	}
	return s*f;
}
ll outputsd(int s){
	if(s>9)outputsd(s/10);
	putchar(s%10+'0');
}

bool has_checksd(int a){
	ll has1d=(base1s*a)%mod1s;
	ll has2d=(base2s*a)%mod2s;
	ll has3d=(base1s*a)%mod2s;
	ll has4d=(base3s*a)%mod3s;
	ll has5d=(base4s*a)%mod4s;
	ll has6d=(base5s*a)%mod5s;
	has1d=(has1d+mod1s)%mod1s;
	has2d=(has2d+mod2s)%mod2s;
	has3d=(has3d+mod2s)%mod2s;
	has4d=(has4d+mod3s)%mod3s;
	has5d=(has5d+mod4s)%mod4s;
	has6d=(has6d+mod5s)%mod5s;
	if(has_as[has1d]&&has_bs[has2d]&&has_cs[has3d]&&has_ds[has4d]&&has_es[has5d]&&has_fs[has6d])return false;
	has_as[has1d]=1;
	has_bs[has2d]=1;
	has_cs[has3d]=1;
	has_ds[has4d]=1;
	has_es[has5d]=1;
	has_fs[has6d]=1;
	
	return true;
}
int T,n,aa;
signed main(){
	T=readasd();
	while(T--){
		has_as.reset();
		has_bs.reset();
		has_cs.reset();
		has_ds.reset();
		has_es.reset();
		has_fs.reset();
		
		n=readasd();
		for(int i=1;i<=n;i++){
			aa=readasd();
			if(has_checksd(aa)){
				printf("%lld",aa);
				putchar(' ');
			}
		}
		putchar('\n');
	}
	//for(int i=1134500;i<=1134567;i++)if(zhi(i))cout<<i<<' ';
	return 0;
}
2024/8/27 15:22
加载中...