codeforces C. Kuroni and Impossible Calculation

12686 단어 codeforces
C. Kuroni and Impossible Calculation
time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output 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
If you are not familiar with short notation, ∏1≤i
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 ∣ a i − a j ∣ m o d m\prod_{1≤i∏1≤iExamples
input
2 10 8 5
output
3
input
3 12 1 4 5
output
0
input
3 7 1 4 9
output
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.
제목:
∏ 1 ≤ i < j ≤ n\a i - a j\m\prod 계산{1≤i∏1≤i아이디어:
만약에 순수한 폭력을 사용한다면 2*105는 시간을 초과할 것이다. 그러나 여기에 비둘기 둥지의 정리와 모형 추출 연산이 있다. (a%mod-b%mod)+mod)%mod =(a-b+mod)%mod가 있기 때문에 모든 수를 남긴 후에 n을 넣어 m을 초과하면 반드시 하나가 반복된다. 중복되면 상감은 0이다. 그러면 모형을 추출하는 것은 반드시 0이다. 이것이 바로 비둘기 둥지의 원리이다. 만약 그렇게 하지 않는다면 여기,이렇게 최악의 상황은 O(100002)입니다. 그리고 폭력을 하면 됩니다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void out(int x) {
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
const int maxn = 2e+5 + 10;
int a[maxn];
int main() {
    int n, m;
    read(n), read(m);
    for (int i = 0; i < n; i++) read(a[i]);
    if (n > m) {
        printf("0");
        return 0;
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans = (ans * (abs(a[i] - a[j]) % m)) % m;
        }
    }
    printf("%d", ans);
    return 0;
}
이미지 처리 의 양자 필터 효과 (Gray and Color Image 용 Bilateral Filtering)
일대일 예제 시퀀싱 – Nodejs 연결

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage