글 읽기 - 반례 찾아 주실 수 있는 분 계시면 감사합니다 ㅜㅜ

banana970 2년 전 0

제가 넣어본 입력 예제는 다 정답으로 나오는데 제출하면 틀렸습니다가 나와서요 ㅜㅜ

그런데 틀리는 반례를 못찾겠습니다... 하나라도 혹시 보이면 부탁드려요!

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
int N;
int list[5001];
int list2[5001];
long long Data[5001] = { 0 };
int cnt[5001] = { 0 };
int j = 0;

long long DP(int n) {
	if (Data[n] != 0) {
		return Data[n];
	}


	if (n == list2[0]) {
		Data[n] = 1;
		
	}
	else {
		for (int i = 1; i < n; i++) {
			if (cnt[i] != 0) {
				int h = cnt[i];
				while (h) {
					Data[n] += Data[i];
					h--;
				}
			}
		}
		Data[n]++;
	}
	return Data[n];
}

int main() {
	
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> list[i];
		list2[i] = list[i];
		cnt[list[i]]++;
	}
	sort(list2, list2 + N);
	for (int i = 0; i < N; i++) {

		if (DP(list[i]) >= 998244353) {
			cout << DP(list[i]) % 998244353 << " ";
		}
		else {
			cout << DP(list[i]) << " ";
		}
	}

}

adfsfsf 2년 전 0

현재 코드 기준, Data에 들어가는 수 중 최댓값은 N이 5000이고 1부터 5000까지 차례대로 입력될 때의 2^4999로, 이건 C++의 어떤 자료형으로도 출력할 수 없습니다. 계산 과정에서 모든 중간 결과를 998244353의 나머지로 바꿔주셔야 오버플로우가 안 일어납니다.

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

문제

문제

출처

ICPC

반례 찾아 주실 수 있는 분 계시면 감사합니다 ㅜㅜ

banana970 2년 전 0

adfsfsf 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말