C. Kuroni and Impossible Calculation
题意:
给出一个数量级在2e5的整型数组,要求求出(∏1≤i<j≤n|ai−aj|) % m 的值。注意:n ≤ 2e5,m ≤ 1000,ai ≤ 1e9。
思路
在思考这道题的时候就想到了不能直接暴力,显而易见,复杂度不能大于O(nlogn),而且也注意到了m最大只有1000,与其他两个指标格格不入,想到应该可以简化程序过程,但是最终还是没有想到方向。其实很容易想到,答案一定在0~999之间,而且数组a有很大的数据量,只要出现一个因子是m的倍数,答案一定是0。然后可以发现如果任意两个数对m取模结果相同,那么这两个数之间一定隔着m的倍数,答案即为0。将所有元素%m的值记录,如果任何一个值出现了两次及以上,答案直接为0,否则再重新遍历。
基于这个思想,还有更简单的做法,假设最坏的情况是a[i] % m 各不相同,最多也只有1000种情况,当n > 1000时至少会出现两个相同的余数,否则才需要遍历,此时O(n^2)的复杂度已经能接受了
代码
1 | int n, m, a[N]; |
大哭Q.Q 错失上分良机啊……