CodeForces-Kuroni and Impossible Calculation（思维+鸽巢原理）

熬过最苦的日子 做最酷的自己

又是一场深夜掉分场（默默擦泪。jpg）

原题链接

Kuroni and Impossible Calculation

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

To become the king of Codeforces, Kuroni has to solve the following problem.

He is given n numbers a1,a2,…,an. Help Kuroni to calculate ∏1≤i<j≤n|ai−aj|. As result can be very big, output it modulo m.

If you are not familiar with short notation, ∏1≤i<j≤n|ai−aj| is equal to |a1−a2|⋅|a1−a3|⋅ … ⋅|a1−an|⋅|a2−a3|⋅|a2−a4|⋅ … ⋅|a2−an|⋅ … ⋅|an−1−an|. In other words, this is the product of |ai−aj| for all 1≤i<j≤n.

Input

The first line contains two integers n, m (2≤n≤2⋅105, 1≤m≤1000) — number of numbers and modulo.

The second line contains n integers a1,a2,…,an (0≤ai≤109).

Output

Output the single number — ∏1≤i<j≤n|ai−aj|modm.

Examples

inputCopy

2 10

8 5

outputCopy

3

inputCopy

3 12

1 4 5

outputCopy

0

inputCopy

3 7

1 4 9

outputCopy

1

Note

In the first sample, |8−5|=3≡3mod10.

In the second sample, |1−4|⋅|1−5|⋅|4−5|=3⋅4⋅1=12≡0mod12.

In the third sample, |1−4|⋅|1−9|⋅|4−9|=3⋅8⋅5=120≡1mod7.

思路： 一开始想的只有暴力暴力再暴力，看了一眼数据范围甚至还想用树状数组来写一波。后来听群里大佬说的思路。

假设有m+1个数，一定有两个数%m相等，相减后一定为0.

当n>m时，一定有两个数%m相等，那么相减后一定为0.所以n>m时答案为0.

当n<=m时，m最大是1000，暴力枚举一波就可以了

跟鸽巢原理差不多吧~ 传送门

代码：

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=1e6+7;
ll a[maxn];
int main(){
       ll n,m;
    n=read();m=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    if(n>m){
        puts("0");
        return 0;
    }
    ll res=1;
    for(ll i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            res=res*abs(a[j]-a[i])%m;
    printf("%lld\n",res);
    return 0;
}

越来越喜欢cf了~