我是靠谱客的博主 沉静战斗机,最近开发中收集的这篇文章主要介绍牛客练习赛48----B-小w的a=b问题,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

首先发出题目链接:
链接:https://ac.nowcoder.com/acm/contest/923/B
来源:牛客网
涉及:哈希


题目如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
很明显,这个题不能硬算,可以先预处理阶乘,把每个数的阶乘先算出来,放在一个数组里,后面每次输入样例中间,可以直接拿出来用


阶乘的性质
n ! = n ∗ ( n − 1 ) ! n!=n*(n-1)! n!=n(n1)!
但是阶乘也很大,这个时候就要运用到基本的哈希算法了,在这里可以先取两个模值mod1和mod2,然后把每一个数的阶乘分别模上这两个数,得到的结果分别存在两个数组里,得到两个数组表

#define mod1 (ll)101211711
#define mod2 (ll)157865417
typedef long long ll;
int i;
ll pmod[100005][3];
ll suma=1,sumb=1;
for(i=1;i<=1e5;i++){
	pmod[i][1]=suma=suma*i%mod1;//第一个哈希表
	pmod[i][2]=sumb=sumb*i%mod2;//第二个哈希表
}

这里哈希只用取模的方式,是因为取模可以不影响循环阶乘的运算

如果只用一个模值,很可能发生两个不同的数模上一个数的结果相同的情况。

不知道哈希算法的,可以看看这个博客。


得到了阶乘哈希表,在后面的输入样例中直接采用阶乘哈希表的值就OK了。

由于有两个模值,所以有两个哈希表,同时考虑两个哈希表,基本可以保证没有特殊情况

		for(i=1;i<=n;i++){//a数组
			scanf("%d",&p);
			if(p==0)	p=1;//这里要特判一下
			sum1_1=sum1_1*pmod[p][1]%mod1;//sum1_1存以第一个哈希表为判断依据阶乘相乘值
			sum1_2=sum1_2*pmod[p][2]%mod2;//sum1_2存以第二个哈希表为判断依据阶乘相乘值
		}
		for(i=1;i<=m;i++){//b数组
			scanf("%d",&p);
			if(p==0)	p=1;
			sum2_1=sum2_1*pmod[p][1]%mod1;//sum2_1存以第一个哈希表为判断依据阶乘相乘值
			sum2_2=sum2_2*pmod[p][2]%mod2;//sum2_2存以第二个哈希表为判断依据阶乘相乘值
		}
		//判断阶乘相乘值是否相同
		sum1_1==sum2_1 && sum1_2==sum2_2?printf("equaln"):printf("unequaln");	

举个例子

过于简单,不用举例子了。。
小一点的数取模也是本身,大一点数的例子也不好举,主要是弄懂哈希算法就好了


代码如下:

#include <iostream>
#define mod1 (ll)101211711
#define mod2 (ll)157865417
using namespace std;
typedef long long ll;
int n,m,t,p;
ll pmod[100005][3];
int main(){
	int i;
	ll suma=1,sumb=1;
	for(i=1;i<=1e5;i++){
		pmod[i][1]=suma=suma*i%mod1;
		pmod[i][2]=sumb=sumb*i%mod2;
	}
	cin>>t;
	while(t--){
		ll sum1_1=1,sum1_2=1;
		ll sum2_1=1,sum2_2=1;
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++){
			scanf("%d",&p);
			if(p==0)	p=1;
			sum1_1=sum1_1*pmod[p][1]%mod1;
			sum1_2=sum1_2*pmod[p][2]%mod2;
		}
		for(i=1;i<=m;i++){
			scanf("%d",&p);
			if(p==0)	p=1;
			sum2_1=sum2_1*pmod[p][1]%mod1;
			sum2_2=sum2_2*pmod[p][2]%mod2;
		}
		sum1_1==sum2_1 && sum1_2==sum2_2?printf("equaln"):printf("unequaln");	
	}
	return 0;
}

最后

以上就是沉静战斗机为你收集整理的牛客练习赛48----B-小w的a=b问题的全部内容,希望文章能够帮你解决牛客练习赛48----B-小w的a=b问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部