题意:给你一个长度为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;
}
}