Codeforce-Ozon Tech Challenge 2020-C. Kuroni and Impossible Calculation(鸽笼原理）

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<=1000

#include <bits/stdc++.h>

using namespace std;

template <typename t>

void read(t &x)

{

    char ch = getchar();

    x = 0;

    t f = 1;

    while (ch < '0' || ch > '9')

        f = (ch == '-' ? -1 : f), ch = getchar();

    while (ch >= '0' && ch <= '9')

        x = x * 10 + ch - '0', ch = getchar();

    x *= f;

}

#define wi(n) printf("%d ", n)

#define wl(n) printf("%lld ", n)

#define rep(m, n, i) for (int i = m; i < n; ++i)

#define rrep(m, n, i) for (int i = m; i > n; --i)

#define P puts(" ")

typedef long long ll;

#define MOD 1000000007

#define mp(a, b) make_pair(a, b)

#define N 200005

#define fil(a, n) rep(0, n, i) read(a[i])

//---------------https://lunatic.blog.csdn.net/-------------------//

int a;

int b[1005], flag;

vector<pair<int, int>> c;

int main()

{

    int n, m;

    read(n), read(m);

    for (int i = 0; i < n; i++)

    {

        read(a);

        int mo = a % m;

        b[mo]++;

        c.push_back(make_pair(mo, a));

        if (b[mo] >= 2)

            flag = 1;

       // cout << mo << endl;

    }

    if (flag)

    {

        puts("0");

        return 0;

    }

    int ans = 1;

    for (int i = 0; i < c.size(); i++)

    {

        for (int j = i + 1; j < c.size(); j++)

        {

            if (c[i].second > c[j].second)

            {

                ans *= (c[i].first - c[j].first + m);

            }

            else

            {

                ans *= (-c[i].first + c[j].first + m);

            }

            ans %= m;

        }

    }

    cout << ans << endl;

}

巴特西

Codeforce-Ozon Tech Challenge 2020-C. Kuroni and Impossible Calculation(鸽笼原理）

最新文章

热门文章