#C241118B. 宠物狗

哈希 集合哈希
题目
发布日期:   2024-11-18
更新日期:   2024-11-22
文章字数:   2.7k
阅读时长:   15 分

#C241118B. 宠物狗

标签（Label）

  • 哈希
  • 集合哈希

网址（Website）

题目详情 - 宠物狗 - Super

题解 - 宠物狗 - Super

题目（Problem）

样例

输入数据 1

2
aab
ababccd

输出数据 1

6
661

【样例 1 解释】

对于第一组询问：

  • $d=1$ 时分割方式为 ${[1,1],[2,2],[3,3]}$，有 $3$ 种不同的方案；
  • $d=2$ 时分割方式为 ${[1,2],[3,3]},{[1,1],[2,3]}$，其中 $[1,1],[3,3]$ 长度不为 $d$，不用于排列，有 $2$ 种不同的方案；
  • $d=3$ 时分割方式为 ${[1,3]}$，有 $1$ 种不同的方案。共 $6$ 种方案。

对于第二组询问，共有 $661$ 种不同的方案。

【样例 2】

见选手目录下的 dog/dog2.in 和 dog/dog2.ans。

该样例满足子任务 $1$ 的限制。

【样例 3】

见选手目录下的 dog/dog3.in 和 dog/dog3.ans。

该样例满足子任务 $2$ 的限制。

【样例 4】

见选手目录下的 dog/dog4.in 和 dog/dog4.ans。

该样例满足子任务 $3$ 的限制。

【样例 5】

见选手目录下的 dog/dog5.in 和 dog/dog5.ans。

该样例满足子任务 $4$ 的限制。

【样例 6】

见选手目录下的 dog/dog6.in 和 dog/dog6.ans。

该样例满足子任务 $5$ 的限制。

【样例 7】

见选手目录下的 dog/dog7.in 和 dog/dog7.ans。

该样例满足子任务 $6$ 的限制。

题解（Solution）

出题者题解

代码（Code）

75分（使用map）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'), write(-x);
	else if(x<10) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}bool ST;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 212345;
const int mod = 998244353;

mt19937_64 rr(time(0));
inline int rnd(int l,int r){return rr()%(r-l+1)+l;}

int fac[N],inv[N];
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
inline int ksm(int x,int k=mod-2){
	int res=1;while(k){
		if(k&1) mul(res,x);
		mul(x,x), k>>=1;
	}return res;
}inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}

char s[N];
int n,ans;

namespace H{
	const int p1 = 1e9+9, b1 = 1331;
	const int p2 = 1e9+7, b2 = 997;
	int fac1[N], pw1[N];
	int fac2[N], pw2[N];
	void init(){
		pw1[0]=1;For(i,1,N-5) pw1[i]=pw1[i-1]*b1%p1;
		pw2[0]=1;For(i,1,N-5) pw2[i]=pw2[i-1]*b2%p2;
	}
	void pre(){
		For(i,1,n) fac1[i] = (fac1[i-1]*b1 + s[i]-'a'+1)%p1;
		For(i,1,n) fac2[i] = (fac2[i-1]*b2 + s[i]-'a'+1)%p2;
	}
	inline int calc(int l,int r){
		int t1 = (fac1[r]-pw1[r-l+1]*fac1[l-1]%p1+p1)%p1;
		int t2 = (fac2[r]-pw2[r-l+1]*fac2[l-1]%p2+p2)%p2;
		return (t1*131ll+t2);
	}
}

map<int,int> mp,hsh;
map<P,int> exi;
int Val, S1, S2;
inline void ins(int x){
	mul(Val, fac[mp[x]]);
	mp[x]++, 
	mul(Val, inv[mp[x]]);
	
	if(!hsh.count(x)) hsh[x] = rnd(1,1e9);
	S1 += hsh[x], S2 ^= hsh[x];
}
inline void del(int x){
	mul(Val, fac[mp[x]]),
	mp[x]--;
	mul(Val, inv[mp[x]]);
	
	assert(hsh.count(x));
	S1 -= hsh[x], S2 ^= hsh[x];
}

void Solve(){
	ans = 0;
	
	scanf("%s", s+1), n = strlen(s+1);
	H::pre();
	
	For(d,1,n){
		mp.clear(), exi.clear(), hsh.clear();
		Val = fac[n/d], S1 = 0, S2 = 0;
		
		int yu = n%d;
		for(int i=yu+1;i<=n;i+=d){//假定n%d起始点在1，存入 hash 
			ins(H::calc(i,i+d-1));
		}
		
		add(ans, Val);
		if(n%d==0) continue;
		exi[{S1,S2}] = true;
		for(int i=1,j=yu+1;j<=n;i+=d,j+=d){//枚举n%d的起始点 
			ins(H::calc(i,i+d-1)), 
			del(H::calc(j,j+d-1));
			
			if(!exi.count({S1,S2})){
				exi[{S1,S2}] = true;
				add(ans, Val);
			}
		}
	}write(ans),puts("");
}

bool ED;
//多测清空 
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("dog.in","r",stdin);
	freopen("dog.out","w",stdout);
	int Tt=rd();double Tim=clock();
	fac[0]=1;For(i,1,N-5) fac[i]=fac[i-1]*i%mod;
	inv[N-5] = ksm(fac[N-5]);
	Rof(i,N-6,0) inv[i] = inv[i+1]*(i+1)%mod;
	H::init();while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
100分（使用邻接表）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'), write(-x);
	else if(x<10) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}bool ST;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
const int mod = 998244353;

mt19937_64 rr(time(0));
inline int rnd(int l,int r){return rr()%(r-l+1)+l;}

int fac[N],inv[N];
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
inline int ksm(int x,int k=mod-2){
	int res=1;while(k){
		if(k&1) mul(res,x);
		mul(x,x), k>>=1;
	}return res;
}

char s[N];
int n,ans;

namespace H{
	const int p1 = 1e9+9, b1 = 131;
	const int p2 = 1e9+7, b2 = 233;
	int fac1[N], pw1[N];
	int fac2[N], pw2[N];
	void init(){
		pw1[0]=1;For(i,1,N-5) pw1[i]=pw1[i-1]*b1%p1;
		pw2[0]=1;For(i,1,N-5) pw2[i]=pw2[i-1]*b2%p2;
	}
	void pre(){
		For(i,1,n) fac1[i] = (fac1[i-1]*b1 + s[i]-'a'+1)%p1;
		For(i,1,n) fac2[i] = (fac2[i-1]*b2 + s[i]-'a'+1)%p2;
	}
	inline int calc(int l,int r){
		int t1 = (fac1[r]-pw1[r-l+1]*fac1[l-1]%p1+p1)%p1;
		int t2 = (fac2[r]-pw2[r-l+1]*fac2[l-1]%p2+p2)%p2;
		return (t1<<31)+t2;
	}
}

const int M = 800;
struct HL{
	int hd[805], nxt[N<<3|7], tot;
	int num[N<<3|7], sum[N<<3|7];
	inline int add(int x,int v=1){
		int tmp = x%M;
		for(int i=hd[tmp];i;i=nxt[i]) if(num[i]==x) return sum[i]+=v;
		nxt[++tot]=hd[tmp], hd[tmp] = tot;
		num[tot] = x, sum[tot] = v;return v;
	}
	inline int chkins(int x,int v){
		int tmp = x%M;
		for(int i=hd[tmp];i;i=nxt[i]) if(num[i]==x) return sum[i];
		nxt[++tot]=hd[tmp], hd[tmp] = tot;
		num[tot] = x, sum[tot] = v;return v;
	}
	inline int operator[](int x){
		int tmp = x%M;
		for(int i=hd[tmp];i;i=nxt[i]) if(num[i]==x) return sum[i];
		return 0;
	}
	inline void clear(){memset(hd,0,sizeof hd), tot=0;}
}mp,hsh,exi;

int Val, S1, S2;
inline void ins(int x){
	int tmp = mp.add(x,1);
	mul(Val, fac[tmp-1]);
	mul(Val, inv[tmp]);
	
	tmp = hsh.chkins(x,rnd(1,1e12)), S1 += tmp, S2 ^= tmp;
}
inline void del(int x){
	int tmp = mp.add(x,-1);
	mul(Val, fac[tmp+1]);
	mul(Val, inv[tmp]);
	
	tmp = hsh.chkins(x,rnd(1,1e12)), S1 -= tmp, S2 ^= tmp;
}

inline int zhuan(int x,int y){return x*37+y;}

void Solve(){
	ans = 0;
	
	scanf("%s", s+1), n = strlen(s+1);
	H::pre();
	
	For(d,1,n){
		mp.clear(), exi.clear(), hsh.clear();
		Val = fac[n/d], S1 = 0, S2 = 0;
		
		int yu = n%d;
		for(int i=yu+1;i<=n;i+=d){
			ins(H::calc(i,i+d-1));
		}
		
		add(ans, Val);
		if(n%d==0) continue;
		exi.add(zhuan(S1,S2));
		
		for(int i=1,j=yu+1;j<=n;i+=d,j+=d){
			ins(H::calc(i,i+d-1)), 
			del(H::calc(j,j+d-1));
			
			if(exi.add(zhuan(S1,S2)) == 1){
				add(ans, Val);
			}
		}
	}write(ans),puts("");
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("dog.in","r",stdin);
	freopen("dog.out","w",stdout);
	int Tt=rd();double Tim=clock();
	fac[0]=1;For(i,1,N-5) fac[i]=fac[i-1]*i%mod;
	inv[N-5] = ksm(fac[N-5]);
	Rof(i,N-6,0) inv[i] = inv[i+1]*(i+1)%mod;
	H::init();while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
100分（使用vector）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'), write(-x);
	else if(x<10) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}bool ST;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
const int mod = 998244353;

mt19937_64 rr(time(0));
inline int rnd(int l,int r){return rr()%(r-l+1)+l;}

int fac[N],inv[N];
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void mul(int &x,int y){x=x*y%mod;}
inline int ksm(int x,int k=mod-2){
	int res=1;while(k){
		if(k&1) mul(res,x);
		mul(x,x), k>>=1;
	}return res;
}

char s[N];
int n,ans;

namespace H{
	const int p1 = 1e9-63, b1 = 131;
	const int p2 = 1e9+7, b2 = 997;
	int fac1[N], pw1[N];
	int fac2[N], pw2[N];
	void init(){
		pw1[0]=1;For(i,1,N-5) pw1[i]=pw1[i-1]*b1%p1;
		pw2[0]=1;For(i,1,N-5) pw2[i]=pw2[i-1]*b2%p2;
	}
	void pre(){
		For(i,1,n) fac1[i] = (fac1[i-1]*b1 + s[i]-'a'+1)%p1;
		For(i,1,n) fac2[i] = (fac2[i-1]*b2 + s[i]-'a'+1)%p2;
	}
	inline int calc(int l,int r){
		int t1 = (fac1[r]-pw1[r-l+1]*fac1[l-1]%p1+p1)%p1;
		int t2 = (fac2[r]-pw2[r-l+1]*fac2[l-1]%p2+p2)%p2;
		return (t1*37+t2);
	}
}

const int M = 200;
struct Hash_List{
	vector<P> link[1024];
	inline int add(int x,int v=1){
		for(auto &p:link[x%M]) if(p.x==x) return p.y+=v;
		link[x%M].emplace_back(x,v);return v;
	}
	inline int chkins(int x,int v){
		for(auto &p:link[x%M]) if(p.x==x) return p.y;
		link[x%M].emplace_back(x,v);return v;
	}
	inline int operator[](int x){
		for(auto &p:link[x%M]) if(x==p.x) return p.y;
		return 0;
	}
	void clear(){For(i,0,M-1) link[i].clear();}
}mp,hsh,exi; 

int Val, S1, S2;
inline void ins(int x){
	int tmp = mp.add(x,1);
	mul(Val, fac[tmp-1]);
	mul(Val, inv[tmp]);
	
	tmp = hsh.chkins(x,rnd(1,1e12)), S1 += tmp, S2 ^= tmp;
}
inline void del(int x){
	int tmp = mp.add(x,-1);
	mul(Val, fac[tmp+1]);
	mul(Val, inv[tmp]);
	
	tmp = hsh.chkins(x,rnd(1,1e12)), S1 -= tmp, S2 ^= tmp;
}

inline int zhuan(int x,int y){return x*37+y;}

void Solve(){
	ans = 0;
	
	scanf("%s", s+1), n = strlen(s+1);
	H::pre();
	
	For(d,1,n){
		mp.clear(), exi.clear(), hsh.clear();
		Val = fac[n/d], S1 = 0, S2 = 0;
		
		int yu = n%d;
		for(int i=yu+1;i<=n;i+=d){//假定n%d起始点在1，存入 hash 
			ins(H::calc(i,i+d-1));
		}
		
		add(ans, Val);
		if(n%d==0) continue;
		exi.add(zhuan(S1,S2));
		
		for(int i=1,j=yu+1;j<=n;i+=d,j+=d){//枚举n%d的起始点 
			ins(H::calc(i,i+d-1)), 
			del(H::calc(j,j+d-1));
			
			if(exi.add(zhuan(S1,S2)) == 1){
				add(ans, Val);
			}
		}
	}write(ans),puts("");
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("dog.in","r",stdin);
	freopen("dog.out","w",stdout);
	int Tt=rd();double Tim=clock();
	fac[0]=1;For(i,1,N-5) fac[i]=fac[i-1]*i%mod;
	inv[N-5] = ksm(fac[N-5]);
	Rof(i,N-6,0) inv[i] = inv[i+1]*(i+1)%mod;
	H::init();while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.iohttps://wolfdeer62456.github.io/2024/11/18/C241118B-%E5%AE%A0%E7%89%A9%E7%8B%97/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
哈希 集合哈希
赏
  目录