[10986] 나머지 합

https://www.acmicpc.net/problem/10986

분류가... https://www.acmicpc.net/problem/tag/Prefix%20Sum

prefix sum??이라고 되어있네요..뭔지 잘모르겠습니당.....

이 문제는 

(a + b) % MOD = (a % MOD + b % MOD) % MOD
라는 것을 이용해야합니다.

a1 + a2 + a3 + ... + an = Sn

이라고 했을 때

aj + a(j+1) + a(j + 2) + ... ai = Si - S(j-1)

입니다.

예제의

5 3
1 2 3 1 2

라고 인풋이 들어오면

2 3 1을 더해도 3으로 나눴을때 나머지가 0이되겠죠??

이것을 어떻게 찾냐???

하면

1 2 3 1 을 다더하면 7이 나오겟죠??

근데 인덱스 0까지의 합은 1입니다.

그렇다면 

인덱스 1~3은 S3 - S0입니다.

S0의 나머지는 1

S3의 나머지 또한 1이죠

그렇다하면 나머지 두개가 같은 이 S3 와 S0을 뺀다면

나머지가 0이됩니다.

즉 이 둘을 뻇을 때 나머지가 0이라는 말입니다.

데이터를 받을 때마다 연속적으로 합을 구해서 mod값으로 나누고 나눈 나머지값들을 각각

카운트합니다.

그리고 m미만의 각 개수에 대해서 n(해당 모드의 개수)C2를 해주면됩니다.(n개 중에 2개를 고르는 방법)

주의할 점은 나머지가 0인경우 nC2 + 자기자신도 이미 나누어지기 때문에 자기자신의 개수까지 더해야한다는 점입니다.

코드입니다.

#include <iostream>
#include <vector>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
 
    ll sum = 0;
    ll c[1000] = { 0, };
 
    //인풋받으면서 sum에다가 인풋받은값을 계속더해줌
    //그리고 그 합에 대해서 mod를 나눠서 c라는 배열에 카운팅해줌.
    while (n--) {
        int a;
        cin >> a;
        sum += a;
        c[sum % m]++;
    }
 
    ll ret = c[0];//0은 그자체로 이미 나머지가 0이기때문에
    for (int i = 0; i < m; i++) ret += (c[i] * (c[i] - 1)) / 2;//nC2
 
    cout << ret;
 
    return 0;
}