#include #include #include #include #include using namespace std; int N; vector nums; int K; vector> left_lengths; int size_sum; vector> lefts; vector>> dp; pair divide(const string& number) { size_sum += number.size(); int left = 0; int ten_pow_n_left = 1; for (int i = number.size() - 1; i >= 0; i--) { left += (((number[i] - '0') % K) * ten_pow_n_left) % K; left %= K; ten_pow_n_left = (ten_pow_n_left * (10 % K)) % K; } return make_pair(left, number.size()); } pair select_num(int length, int left, int used) { if (used == (1 << N) - 1) { return left % K ? make_pair(0, 1) : make_pair(1, 0); } if (dp[left][used] != make_pair(-1ll, -1ll)) { return dp[left][used]; } pair counts = make_pair(0, 0); for (int next_i = 0; next_i < N; next_i++) { if (!(used & (1 << next_i))) { int next_left = (left + lefts[left_lengths[next_i].first][length]) % K; int next_length = length + left_lengths[next_i].second; auto [fst, snd] = select_num(next_length, next_left, used | (1 << next_i)); counts.first += fst; counts.second += snd; } } dp[left][used] = counts; return counts; } long long GCD(long long a, long long b) { if (b == 0) return a; return GCD(b, a % b); } int main() { // 입력 cin >> N; nums = vector(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } cin >> K; // 1로 나누기 예외처리 if (K == 1) { cout << "1/1"; return 0; } left_lengths = vector>(N); size_sum = 0; for (int i = 0; i < N; i++) { left_lengths[i] = divide(nums[i]); } // lefts 채우기 lefts = vector(K, vector(size_sum + 1, -1)); for (int left_i = 0; left_i < K; left_i++) { lefts[left_i][0] = left_i; for (int size_i = 1; size_i <= size_sum; size_i++) { lefts[left_i][size_i] = (lefts[left_i][size_i - 1] * (10 % K)) % K; } } dp = vector(K, vector(1 << N, make_pair(-1ll, -1ll))); auto [right_count, wrong_count] = select_num(0, 0, 0); if (right_count == 0) { cout << "0/1"; return 0; } long long gcd = GCD(max(right_count, wrong_count), min(right_count, wrong_count)); cout << right_count / gcd << '/' << (right_count + wrong_count) / gcd; }

제출 #21293

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: