小w的a=b问题（高性能优化+减少误差)

66 阅读 0 评论 44 点赞

我是靠谱客的博主忧虑烧鹅，最近开发中收集的这篇文章主要介绍小w的a=b问题（高性能优化+减少误差)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/contest/923/B
来源：牛客网

题目描述

给你两个数组，一个a[]a[]数组，长度为n，另一个是b[]b[]数组，长度为m。
现在问你∏ni=1a[i]!∏i=1na[i]!是否等于∏mi=1b[i]!∏i=1mb[i]!
其中∏∏是连乘符，它表示n个元素的乘积。"!“为阶乘运算，表示小于等于该数所有正整数的积，并且规定0!=1。
我们认为阶乘运算”!“的优先级大于连乘运算"∏∏”。
输入描述:
第一行是一个正整数T，(1⩽T⩽2∗102)(1⩽T⩽2∗102)表示案例的数目
对于每组案例，第一行是两个正整数n,m，(1⩽n,m⩽105)(1⩽n,m⩽105)。
接下来一行输入n个整数a[i]，(0⩽a[i]⩽105)(0⩽a[i]⩽105)。
接下来一行输入m个整数b[i]，(0⩽b[i]⩽105)(0⩽b[i]⩽105)。保证n,m的总和不多于2∗1062∗106
输出描述:
对于每组案例，输出一行一个字符串，如果∏ni=1a[i]!∏i=1na[i]!等于∏mi=1b[i]!∏i=1mb[i]!，请输出"equal"。
反之请输出"unequal"。

示例1

输入

3
2 1
5 3
6
4 6
4 2 3 0
2 3 2 2 1 3
3 4
5 6 7
3 4 5 6

输出

equal
equal
unequal

说明

对于第一组案例：
5! * 3!=1 * 2 * 3 * 4 * 5 * 1 * 2 * 3=720
6!=1 * 2 * 3 * 4 * 5 * 6=720
完全相等。
对于第二组案例：
4! * 2! * 3! * 0!=1 * 2 * 3 * 4 * 1 * 2 * 1 * 2 * 3 * 1=288
2! * 3! * 2! * 2! * 1! * 3!=1 * 2 * 1 * 2 * 3 * 1 * 2 * 1 * 2 * 1 * 1 * 2 * 3=288
完全相等。
对于第三组案例：
5!*6!*7!=435456000
3!*4!*5!*6!=12441600
两者不等。

不得不说这道题目的要求还真是高啊！
~~说到底还是自己太弱gei了，有的大佬十几分钟就AC了QAQ~~

话不多说了，这道题注意几个问题：
1.暴力不可取！绝对TLE！
2.尽量采用read()快速读入，因为数据要求比较高
3.阶乘运算中数字过大，采用高精度计算麻烦费时间，并且容易TLE，最好的方法是取模运算
4.取模尽量取大且为质数，同时要多次取不同的模计算避免误差！！（个人测试出至少要取四组不同的摸才能AC，5555555qaq一直WA）

剩下就上代码了，算是比较好理解的，类似于双哈希减少误差的思想，如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+5;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct node
{
    int jc[N],v1,v2;
    long long mod;
    void init(){
        jc[0]=1;
        for(int i=1;i<N;i++)
            jc[i]=1ll*jc[i-1]*i%mod;
    }
    void add1(int x){v1=1ll*v1*jc[x]%mod;}
    void add2(int x){v2=1ll*v2*jc[x]%mod;}
}c[4];
int main(){
    int t,n,m,k;
    t=read();
    c[0].mod=998244353;
    c[1].mod=998244853;
    c[2].mod=1000000007;
    c[3].mod=1000000009;
    for(int i=0;i<4;i++)
        c[i].init();
    while(t--){
        n=read();m=read();
        for(int i=0;i<4;i++)
            c[i].v1=c[i].v2=1;
        for(int i=1;i<=n;i++){
            k=read();
            for(int j=0;j<4;j++)
                c[j].add1(k);
        }
        for(int i=1;i<=m;i++){
            k=read();
            for(int j=0;j<4;j++)
                c[j].add2(k);
        }
        bool flag=true;
        for(int i=0;i<4;i++)
            if(c[i].v1!=c[i].v2)
                flag=false;
        if(flag)
            cout<<"equal"<<endl;
        else
            cout<<"unequal"<<endl;
    }
    return 0;
}