Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) 比赛人数7420
[codeforces 1305C] Kuroni and Impossible Calculation 数据范围是突破
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址https://codeforces.ml/contest/1305/problem/C
2≤n≤210^5先突破n,找公式,没找到,努力了半天,只找到O(n^2)
突然发现1≤m≤1000,第一次遇到这么小的模
简单列了几个数据,感觉,差值可能遇到0,也可能遇到m,那么之后的数据,也无需再处理,答案是0
n>m 一定会遇到差值为0或m,或m倍数的情况,请看如下例子
n=6,m=5
1 1 2 3 4 5
能找到差值为0=1-1
n=6,m=5
1 2 3 4 5 6
能找到差值为5=6-1
n=6,m=5
1 2 3 4 5 7
能找到差值为5=7-2
n=6,m=5
1 2 3 4 5 111
1 2 3 4 5 111
能找到差值为 5的倍数=111-1=110
简单验证如下
n=6,m=5
x1 x2 x3 x4 x5 x6
x1<=x2<=x3<=x4<=x5<=x6
x2-x1=0,1,2,3,4 取值可能(已经模过5了)
x3-x2=0,1,2,3,4 取值可能(已经模过5了)
x4-x3=0,1,2,3,4 取值可能(已经模过5了)
x5-x4=0,1,2,3,4 取值可能(已经模过5了)
x6-x5=0,1,2,3,4 取值可能(已经模过5了)
请读者随便取值,总能找到,差值%5=0
任意找的某组数据如下
x2-x1=0
x3-x2=1
x4-x3=2
x5-x4=3
x6-x5=4
用如上数据,找到差值x5-x3=x5-x4+x4-x3=3+2=5
故答案为0
AC代码如下
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
int a[200010];
int main(){
int n,m,i,j;
LL ans=1;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
if(n>m){
printf("0\n");
return 0;
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
ans=ans*abs(a[i]-a[j])%m;
printf("%lld\n",ans);
return 0;
}
|