概述
首先发出题目链接:
链接:https://ac.nowcoder.com/acm/contest/923/B
来源:牛客网
涉及:哈希
题目如下:
很明显,这个题不能硬算,可以先预处理阶乘,把每个数的阶乘先算出来,放在一个数组里,后面每次输入样例中间,可以直接拿出来用
阶乘的性质:
n
!
=
n
∗
(
n
−
1
)
!
n!=n*(n-1)!
n!=n∗(n−1)!
但是阶乘也很大,这个时候就要运用到基本的哈希算法了,在这里可以先取两个模值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问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复