boj 10986 나머지 합

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

10986번: 나머지 합

[boj 3673 나눌 수 있는 부분 수열] 문제와 같은 풀이 방법입니다.

 

모든 수열의 누적합을 구해 각각의 누적 합의 %M 값을 사용합니다.

5 3
1 2 3 1 2

위의 입력을 예시로 들면

sum   = 1 3 6 7 9
MOD M = 1 0 0 1 0

이렇게 됩니다. 저는 이번 문제는 dp에 MOD M한 값을 미리 저장해두었고, cnt[dp[i]]으로 카운팅 하였습니다.

 

M = 3이므로

나머지가 0인 갯수는 3

나머지가 1인 갯수는 2이므로

 

나머지가 같은 부분 수열에서 2개를 뽑는 조합을 더하는 식으로 구할 수 있습니다.

 

 

#include <iostream>
#define MAX_N 1000001
#define MAX_M 1001
using namespace std;
typedef long long ll;
 
ll cnt[MAX_M], ans;
int dp[MAX_N];
int N, M;
 
void func() {
    ans = cnt[0];
    for (int i = 0; i < M; i++) {
        ans += (cnt[i] * (cnt[i] - 1) / 2LL);
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
 
        dp[i] = (dp[i] + dp[i - 1]) % M;
        cnt[dp[i]]++;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}