更好的阅读体验

题目传送门

• 给定 $a_1\sim a_{n}a\_1\backslash sim\; a\_n$，求当 $x\in [1,p)x\backslash in[1,p)$ 时满足以下条件的有序三元组 $(i,j,k)(i,j,k)$ 的数量：

  • $i\mathrm{\ne }j,j\mathrm{\ne }k,k\mathrm{\ne }ii\backslash ne\; j,j\backslash ne\; k,k\backslash ne\; i$.

  • $(a_i\cdot a_j+a_k)\mathrm{m}\mathrm{o}\mathrm{d}p=x(a\_i\backslash cdot\; a\_j+a\_k)\; \backslash bmod\; p=x$.

• $1\le n,p\le 50001\backslash le\; n,p\backslash le\; 5000$，$0\le n\le 10^{9}0\backslash le\; n\backslash le\; 10^9$.

$\mathtt{\text{Solution}}\backslash texttt\{Solution\}$

分别求 $x=1\sim p-1x=1\backslash sim\; p-1$ 时的答案 ${\mathrm{ans}}_{}\backslash operatorname\{ans\}\_x$.对于枚举的每一个 $xx$，枚举 $k=1\sim nk=1\backslash sim\; n$，这样可以得到 $a_i\cdot a_j\mathrm{m}\mathrm{o}\mathrm{d}p=(x-a_k)\mathrm{m}\mathrm{o}\mathrm{d}pa\_i\backslash cdot\; a\_j\; \backslash bmod\; p=(x-a\_k)\backslash bmod\; p$.

考虑预处理 $v_w(w\in [1,p))v\_w(w\backslash in[1,p))$ 表示满足 $a_i\cdot a_j\mathrm{m}\mathrm{o}\mathrm{d}p=wa\_i\backslash cdot\; a\_j\backslash bmod\; p=w$ 的有序对 $(i,j)(i\mathrm{\ne }j)(i,j)(i\backslash ne\; j)$ 的个数. 这个可以枚举两个数，然后将它们乘积的余数对应的 $vv$ 值 $+1+1$. 这样对于枚举的 $kk$，直接将 ${\mathrm{ans}}_{}\backslash operatorname\{ans\}\_x$ 加上 $v_{(x-a_k)\mathrm{m}\mathrm{o}\mathrm{d}p}v\_\{(x-a\_k)\backslash bmod\; p\}$ 即可.

不过 $v_{(x-a_k)\mathrm{m}\mathrm{o}\mathrm{d}p}v\_\{(x-a\_k)\backslash bmod\; p\}$ 可能计算了 $a_{k}a\_k$ 去乘上某个数，因此还要预处理 $u_{i,j}(i\in [1,n],j\in [1,p))u\_\{i,j\}(i\backslash in[1,n],j\backslash in[1,p))$，表示满足 $a_i\cdot a_t\mathrm{m}\mathrm{o}\mathrm{d}p=j(t\mathrm{\ne }i,t\in [1,n])a\_i\backslash cdot\; a\_t\backslash bmod\; p=j(t\backslash ne\; i,t\backslash in[1,n])$ 的 $tt$ 的个数. 这个可以枚举 $i,ti,t$ 两个数，然后然后将它们乘积的余数对应的 $u_{i}u\_i$ 值 $+1+1$.

最后再把 ${\mathrm{ans}}_{}\backslash operatorname\{ans\}\_x$ 减去 $2\cdot u_{k,x}2\backslash cdot\; u\_\{k,x\}$ 即可. 注意是 $22$ 倍，因为 $vv$ 的值是有序对个数，当 $i=k,j=ki=k,j=k$ 时都要减去 $u_{k,x}u\_\{k,x\}$.

时间复杂度为 $\mathcal{O}(n^2+np)\backslash mathcal\{O\}(n^2+np)$，空间复杂度为 $\mathcal{O}(np+n+p)\backslash mathcal\{O\}(np+n+p)$，可以接受.

$\mathtt{\text{Code}}\backslash texttt\{Code\}$

#include<bits/stdc++.h>
#define int long long//相乘会见祖宗.
#define N 5001
using namespace std;
int u[N][N],v[N],p,n,a[N];
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>p;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i^j){
                ++v[a[i]*a[j]%p];
                ++u[i][a[i]*a[j]%p];
            }
        }
    }
    for(int i=0,k;i<p;++i){
        k=0;
        for(int j=1,q;j<=n;++j){
            q=(i-a[j]+p*1145141919810)%p;//注意负数取模.
            k+=v[q]-u[j][q]*2;
        }
        cout<<k<<' ';
    }
}

测评链接