可重集三元组计数问题：求解满足条件的三元组数量

{'title':'题意','content':'给一可重集 (S) 及质数 (p)，问能从集合中选出多少种本质不同的三元组 ((x,y,z)) ((x\leq y\leq z)) 使得 (xyz\equiv 1\pmod p)？(|S|\leq 2333,p\leq 2^{30})

70% 解 保证 (x<p|x\in S)。首先排序所有数并预处理出其逆元。接着枚举 (x,y(x\leq y))，算出 (z=x^{-1}y^{-1})，检查是否 (y\leq z) 以及是否 (z\in S)（二分）。注意处理有数字相等的情况。

100% 解 排序时优先根据 (\mod p) 结果排序，并将所有数字去重后的结果另外存储一份。仍然枚举 (x,y(x\leq y))，算出 (z)，统计与 (z) 在同一剩余系下的数字个数。同样注意处理有数字相等的情况。

代码：

#include<bits/stdc++.h> using namespace std; int getint(){ int ans=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-1; c=getchar(); } while(c>='0'&&c<='9'){ ans=ans10+c-'0'; c=getchar(); } return ansf; } int p;

bool cmp(int a,int b){ if(a%p!=b%p)return a%p<b%p; return a<b; } bool cmp2(int a,int b){ return a%p<b%p; }

inline int qpow(int x,int y,int z){ int ans=1; while(y){ if(y&1)ans=ans1llx%z; x=x1llx%z; y>>=1; } return ans; } int a[3000]; int inv[3000]; int uniq[3000];

int main(){ int n=getint(); p=getint(); int sqrtn=sqrt(n); for(int i=0;i<n;i++){ a[i]=getint(); } sort(a,a+n,cmp); memcpy(uniq,a,sizeof(uniq)); int r_=unique(uniq,uniq+n)-uniq; for(int i=0;i<n;i++){ inv[i]=qpow(a[i],p-2,p); } int ans=0; //a[i]<a[j]<=a[k] for(int i=0;i<n;i++){ if(a[i]==0)continue; if(i&&a[i-1]==a[i])continue; for(int j=i+1;j<n;j++){ if(j&&a[j-1]==a[j])continue; if(a[i]==a[j])continue; int ak=inv[i]1llinv[j]%p; //cout<<'>> ? '<<a[i]<<' '<<a[j]<<' '<<ak<<endl; if(ak%p<a[j]%p)continue; if(ak%p==a[j]%p){ ans+=(a[j+1]==a[j]); //cout<<'> '<<ans<<endl; ans+=upper_bound(uniq,uniq+r_,ak,cmp2) -upper_bound(uniq,uniq+r_,a[j],cmp); //cout<<'> '<<ans<<endl; }else{ ans+=upper_bound(uniq,uniq+r_,ak,cmp2) -lower_bound(uniq,uniq+r_,ak,cmp2); } } } //a[i]=a[j]<=a[k] for(int i=0;i<n-1;i++){ if(a[i]!=a[i+1])continue; if(i&&a[i-1]==a[i])continue; if(a[i]==0)continue; int ak=inv[i]1llinv[i]%p; if(ak%p<a[i]%p)continue; if(ak%p==a[i]%p){ ans+=(a[i+2]==a[i]); //cout<<'> '<<ans<<endl; ans+=upper_bound(uniq,uniq+r_,ak,cmp2) -upper_bound(uniq,uniq+r_,a[i],cmp); //cout<<'> '<<ans<<endl; }else{ ans+=upper_bound(uniq,uniq+r_,ak,cmp2) -lower_bound(uniq,uniq+r_,ak,cmp2); } } printf('%d\n',ans); return 0; }

为什么这份代码中if(j&&a[j-1]==a[j])continue;，而不是if(j>i+1&&a[j-1]==a[j])continue;内容：这份代码中的if(j&&a[j-1]==a[j])continue;是为了避免重复计算相同的三元组。在内层循环中，对于任意的i，我们只需要枚举不等于i的j来计算三元组。因此，当j等于i时，我们需要跳过，而当j等于i+1时，我们可以继续计算。因此，if(j&&a[j-1]==a[j])continue;是正确的。而if(j>i+1&&a[j-1]==a[j])continue;则是不必要的，因为对于任意的i，j的初始值都是i+1，即j>i+1。