글 읽기 - 문제 힌트는 만족하는데 제출하면 틀렸다고 합니다

seokjeongeum 2년 전 0

주석처리한 코드를 통해서 N=1일때부터, N=40일 때 까지 답을 모두 더해 출력하면 126461847755가 나오는데

코드를 제출하면 틀렸다고 합니다

출력이 잘못된걸까요?

#include <iostream>
#include <queue>
#include <tuple>
#include <limits>
#include <unordered_map>
#include <stack>
#include <set>
#include <deque>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;
vector<vector<vector<long long>>>d;
long long f(int digit, int current, int state) {
	long long& r = d[digit][current][state];
	if (r != -1) {
		return r;
	}
	if (digit == 0) {
		if (state == (1 << 10) - 1) {
			return r = 1;
		}
		else {
			return r = 0;
		}
	}
	r = 0;
	if (current + 1 < 10) {
		r += f(digit - 1, current + 1, state | (1 << (current + 1)));
	}
	if (current - 1 >= 0) {
		r += f(digit - 1, current - 1, state | (1 << (current - 1)));
	}
	return r;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(numeric_limits<double>::max_digits10);
	int N;
	cin >> N;
	d.resize(N, vector<vector<long long>>(10, vector<long long>(1 << 10, -1)));
	long long sum = 0;
	for (int i = 1; i <= 9; ++i) {
		sum += f(N - 1, i, 1 << i);
	}
	cout << sum % 1000000000LL << '\n';
	//d.resize(40, vector<vector<long long>>(10, vector<long long>(1 << 10, -1)));
	//long long l = 0;
	//for (int i = 1; i <= 40; ++i) {
	//	for (int j = 1; j <= 9; ++j) {
	//		l += f(i - 1, j, 1 << j);
	//	}
	//}
	//cout << l;
	return 0;
}

bamgoesn 2년 전 2

반례입니다.

68

정답: 646028283 (14778633959646028283)
출력: -63523333

69

정답: 396360486 (29050565590396360486)
출력: -22742746

70

정답: 169463574 (57094374404169463574)
출력: 40808726

seokjeongeum 2년 전 0

감사합니다

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

문제

문제

출처

ICPC

문제 힌트는 만족하는데 제출하면 틀렸다고 합니다

seokjeongeum 2년 전 0

bamgoesn 2년 전 2

seokjeongeum 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말