[ABC339F] Product Equality 题解

· · 题解

第一次 AK ABC，写个题解纪念一下。

大数运算判断相等，果断考虑哈希。

具体地，把每个数对质数 p 取模，使用 __gnu_pbds::gp_hash_table 存储每个数的出现次数；然后枚举两个乘数，在哈希表中查找它们的积的数量，加入答案即可。

但是单模哈希容易被卡，于是本人使用 3 个质数 p_1=10^9+9,p_2=1610612741,p_3=10^8+81 进行三模哈希，卡卡常可以通过。

令 a_i 在十进制下的位数为 l_i，时间复杂度 O(n^2+\sum l_i)，带个 3 的常数。

放代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
const int p[3]={1000000009,1610612741,100000081};
int H(string s,int x){
  int c=0;
  for(char i:s)
    ((c*=10)+=i-48)%=p[x];
  return c;
}
main(){
  ios::sync_with_stdio(false);
  int n,c=0; cin>>n;
  vector<string> a(n);
  for(auto &i:a)cin>>i;
  vector<array<int,3> > h(n);
  __gnu_pbds::gp_hash_table<int,int> m[3];
  for(int i=0;i<n;i++)
    for(int j=0;j<3;j++)
      m[j][h[i][j]=H(a[i],j)]++;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
      int s=1000;
      for(int k=0;k<3;k++)
        s=min(s,m[k][h[i][k]*h[j][k]%p[k]]);
      c+=s;
    }
  cout<<c<<endl;
  return 0;
}