글 읽기 - 어디가 틀렸는지 모르겠습니다.

kth990303 3년 전 0

코드에 주석을 달아놓았습니다.

누적합을 구한 후, 누적합의 나머지에 따른 개수를 담는 배열에서

아래와 같이 부분수열의 개수를 구해주었습니다.

반례가 있을까요?

#include <iostream>
using namespace std;
typedef long long ll;
const int MAX = 50001;
const int MAX_D = 1000001;
ll D, N, a[MAX], c[MAX_D], s[MAX];
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	while (t--) {
        // 초기화
		ll ans = 0;
		fill(a, a + MAX, 0);
		fill(c, c + MAX, 0);
		fill(s, s + MAX, 0);
		cin >> D >> N;
		for (int i = 1; i <= N; i++) {
			cin >> a[i];
            // 누적합을 저장시키고
			s[i] = s[i - 1] + a[i];
            // 누적합을 D로 나눠준 후
			s[i] %= D;
            // 누적합의 나머지에 따른 개수를 저장시킴.
			c[s[i]]++;
		}
		ans += c[0];    // 나머지가 0인 구간합은 자체가 답임
		for (int i = 0; i < D; i++) {
            // 나머지가 같은 구간합끼리 선택해서 빼는 경우 nC2
			ans += c[i] * (c[i] - 1) / 2;
		}
		cout << ans << "\n";
	}
}

2sms22rjt 3년 전 1

안녕하세요! 늘 고맙습니다.

18번째 줄에 MAX_D까지 0으로 채워주면 될 것같습니다

kth990303 3년 전 1

@2sms22rjt

해결되었습니다. 감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다.

kth990303 3년 전 0

2sms22rjt 3년 전 1

kth990303 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말