import sys import math input = sys.stdin.readline # get input len_arr = int(input()) # max : 15 arr = [int(input()) for _ in range(len_arr)] # max : x.yz * 10**49 target = int(input()) # 최초 나머지로 변환 init_remain_arr = [num % target for num in arr] num_exps = [0] * (1 << len_arr) custom_range = [] # 최초 자리수 확인 for i in range(len_arr): num = arr[i] num_exp = 0 while num: num //= 10 num_exp += 1 num_exps[1 << i] = num_exp # 자리수 및 순서 확인 for i in range(1 << len_arr): num_zeros = 0 num_exp = 0 for j in range(len_arr): if (1 << j) & i: num_zeros += 1 num_exp += num_exps[1< 10: new_val = (prev_val * 10) % target else: new_val = (prev_val * (10)*target) % target modula_table.append(new_val) # print(modula_table) # 탐색 for idx in custom_range: for num_moves in range(len_arr): if idx & (1 << num_moves): # 현재 숫자가 걸친다면 cur_remain = init_remain_arr[num_moves] prev_idx = idx - (1 << num_moves) prev_num_exp = num_exps[prev_idx] for prev_remain, prev_remain_cnt in dp[prev_idx].items(): # new_remain = ((cur_remain* (10**prev_num_exp)) + prev_remain) % target new_remain = (((cur_remain * modula_table[prev_num_exp]) % target) + prev_remain ) % target dp[idx][new_remain] = dp[idx].get(new_remain, 0) + prev_remain_cnt # for idx in range(len(dp)): # print(idx, bin(idx)[2:].zfill(5), dp[idx]) bunja = (dp[-1].get(0, 0)) bunmo = (sum(dp[-1].values())) if bunja == 0: answer = "0/1" else: gcd = math.gcd(bunja, bunmo) answer = str(bunja // gcd) + "/" + str(bunmo // gcd) print(answer) # for idx in range(len(num_exps)): # print(bin(idx)[2:].zfill(9), num_exps[idx])

제출 #155348

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: