题意:给你一个长度为n的序列,要你求他们的连乘,最后mod m。
思路:
如果O(n^2)暴力的话很好求,但是因为n = 2e5 所以肯定会超时。
先给出结论,如果 n > m ,连乘直接为0。(等下给出证明)
如果n <= m ,直接O(n^2)暴力即可,因为m最大取值 = 1e3。
证明:
假设存在 j ,使得 an - aj = 0 mod m,那么整个式子就直接等于0了,结论成立。
假设存在j1,使得 an - aj != 0 mod m,那么一定存在 0<j1<j2<n,因为mod m的取值只有[0,m-1],如果取值为0 ,结论显然成立,如果不为0,那么有[1,m-1]种取值,但是 n > m ,那么mod m后至少存在m种取值(不含0),由鸽巢原理可知,必定存在 an - aj = c mod m = an - ai ,即存在同余。
那么移项后就有 ai - aj = 0 mod m。
综上结论成立。
有了这个结论代码就很好写了。
代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn];
int main(){
    ll n,m;cin>>n>>m;
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    ll ans = 1;
    if(n>m)cout<<"0"<<endl;
    else{
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        ans = (ans*abs(a[i] - a[j]))%m;
        cout<<ans<<endl;
    }
}