博客

Tokitsukaze 有一个长度为 n 的序列 a 和一个正整数 p 。

对于所有 x=0…p−1，Tokitsukaze 想知道三元组 [i,j,k]的数量，满足：

• i≠j and i≠k and j≠k

• (ai⋅aj+ak)≡x (mod p)

输入描述：


第一行包含两个整数 n, p (3≤n≤5000; 1≤p≤5000)。

第二行包含 n 个整数 a1,a2,…,an (0≤ai≤10^9)。

输出描述：


输出一行 p 个整数，第 d 个整数表示 x=d 时的答案 (0≤d≤p−1)。

输入：

3 3
1 2 3

输出：

0 2 4

样例解释：

当 x=0 时，没有满足条件的三元组；

当 x=1 时，满足条件的三元组为；[2,3,1],[3,2,1]；

当 x=2 时，满足条件的三元组为；[1,2,3],[2,1,3],[1,3,2],[3,1,2]

解析：因为 i,j k,x都是变的，暴力枚举4个变量肯定不合理，但是等式可以变为ai⋅aj=x-ak，然后就可以O(n^2)处理出a[ i ]*a[ j ]的值的个数，然后再O(n^2)枚举x和k，就可以得到方案个数，但是此时还没有满足i,j,k互不相等，我们得减去其中不合法的情况，可以利用c[ i ][ j ]表示k=i的时候，满足ai⋅aj=x-ak的方案数，然后累加时候减去即可。

标程解法

#include <cstdio>
typedef long long ll;
const int N=5005;
int a[N],b[N],c[N][N];
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]%=p;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            int w=a[i]*a[j]%p;
            b[w]++,c[i][w]+=2;//c[][]+2因为i=k和j=k的时候的不合法方案,记录在一起
        }
    }
    for(int x=0;x<p;x++)
    {
        ll ans=0;//需要开long long，不然累加会爆int
        for(int k=1;k<=n;k++)
        {
            int tar=(x-a[k]+p)%p;//+p之后%p是为了避免出现负值
            ans+=b[tar]-c[k][tar];
        }
        printf("%lld ",ans);
    }
    printf("\n");
    return 0;
}