XSY3593 极好的问题

极好的问题

题意

Solution

首先看到这个数据范围，\(O(n^2 log_n)\)跑不了了

我们先按照模P分类，枚举两个数，然后算出他们乘积的逆元，在原序列中二分找到这个逆元即可

然后是一波暴力组合数统计，细节有一点点多

不过貌似人家的复杂度都是比我优很多的QAQ 我这个代码还要卡常

#include<bits/stdc++.h>
using namespace std;
int a[3010];
int rea[3010];
int n,p;
int cnt;
inline bool cmp(const int &a,const int &b){
    return (a%p)==(b%p)?a<b:(a%p)<(b%p);
}
void exgcd(int a,int b,int &x,int &y){
    if(!b)x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
inline int sb(int a){
    int x,y;
    exgcd(a,p,x,y);
    x=(x%p+p)%p;
    return x;
}
int ans1,ans2,ans3;
int num1[3010],num2[3010],num3[3010];
inline int find(int val){
    int l=1,r=cnt;
    while(l<r){
        int mid=(l+r)/2;
        if(rea[mid]<val)l=mid+1;
        else if(rea[mid]>val)r=mid-1;
        else return mid;
    }
    return rea[l]==val?l:-1;
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i){
        if(a[i]%p!=a[i-1]%p){
            ++cnt;
            rea[cnt]=a[i]%p;
        }
        if(a[i]!=a[i-1])num1[cnt]++;
        if(a[i]==a[i-1]&&a[i]!=a[i+1])num2[cnt]++;
        if(a[i]==a[i-1]&&a[i-1]==a[i-2]&&a[i]!=a[i+1])num3[cnt]++;
    }
    int ans=0;
    for(register int i=1;i<=cnt;++i){
        for(register int j=1;j<=cnt;++j){
            int inv=sb(1ll*rea[i]*rea[j]%p);
            int k=find(inv);
            if(k==-1)continue;
            if(i!=j&&j!=k&&i!=k){
                ans1+=num1[i]*num1[j]*num1[k];
            }
            else if(i!=j&&j==k){
                ans1+=num1[j]*(num1[j]-1)*num1[i];
                ans2+=num2[j]*num1[i];
            }
            else if(i!=j&&i==k){
                ans1+=num1[k]*(num1[k]-1)*num1[j];
                ans2+=num2[k]*num1[j];
            }
            else if(i==j&&j!=k){
                ans1+=num1[i]*(num1[i]-1)*num1[k];
                ans2+=num2[i]*num1[k];
            }
            else{
                ans1+=num1[i]*(num1[i]-1)*(num1[i]-2);
                ans2+=num2[i]*(num1[i]-1)*3;
                ans3+=num3[i];
            }
        }
    }
    printf("%d\n",ans1/6+ans2/3+ans3);
}

XSY3593 极好的问题

原文：https://www.cnblogs.com/youddjxd/p/11782237.html