백준 1086 - 박성원 (Python)

개인적으로 너무 어려웠던 문제입니다.
다른 분들의 풀이를 많이 참고했습니다.

핵심 코드

tmp = 0
    for i in range(n):
        if not bit & (1 << i):
            new_mod = ((mod * mod_10[a_len[i]]) % k + a[i]) % k
            tmp += dfs(new_mod, bit | (1 << i))

    dp[mod][bit] = tmp

4번째 줄의 의미는 나머지 연산의 특성을 생각하면 알 수 있습니다.
dp[나머지][비트]에는 비트 % k == 나머지 일 때 가능한 비트들의 수를 저장한다.

나머지 연산 특성

(a + b) % c == (a % c + b % c) % c
(a - b) % c == (a % c - b % c) % c
(a * b) % c == (a % c * b % c) % c

나눗셈일 때는 성립하지 않아서 곱셈의 역원으로 계산해야 합니다.

나머지 부분은 주석으로 설명하겠습니다.

import sys
from math import factorial, gcd

input = sys.stdin.readline

def solution(mod, bit):
    if bit == (1 << n) - 1: # 끝까지 다 돌았을 때
        if mod == 0: # 나누어 떨어질 때
            return 1
        return 0

    if dp[mod][bit] != -1: # 이미 저장된 값이 있을 때
        return dp[mod][bit]

    tmp = 0
    for i in range(n):
        if not bit & (1 << i):
            # 나머지가 i 인 모든 비트들을 찾아서 더해줌
            new_mod = ((mod * mod_10[a_len[i]]) % k + a[i]) % k
            tmp += dfs(new_mod, bit | (1 << i))

    dp[mod][bit] = tmp
    
    return dp[mod][bit]

n = int(input())
a = [int(input()) for _ in range(n)]
k = int(input())

dp = [[-1] * (1 << n) for _ in range(k)]
a_len = [len(str(i)) for i in a] # 나머지 계산을 하기 위해 미리 계산
a = [i % k for i in a]

mod_10 = [1]
for i in range(50): # 나머지 계산을 하기 위해 미리 계산
    mod_10.append((mod_10[-1] * 10) % k)
    
answer = solution(0, 0)

if answer == 0:
    print('0/1')
else:
    f = factorial(n)
    if answer == f or k == 1:
        print('1/1')
    else:
        m = gcd(answer, f)
        print('{}/{}'.format(answer // m, f // m))