백준 1086 - 박성원

icpc.me/1086

푸는 방법을 고민하기 전에...

어떤 큰 정수를 100 이하의 수로 나눈 나머지를 구하는 것은 어렵지 않다. 나눗셈을 손으로 푸는 과정을 구현하면 된다.

 

큰 정수를 스트링으로 받은 다음 반복문을 통해 (이전 자릿수까지 나눗셈을 통해 나온 나머지 * 10 + 현재 자릿수) % K 하면 된다. C계열 코드로는 다음과 같이 쓸 수 있겠다.

 

int pre = 0;
 
for (int j = 0; j < seq[i].size(); ++j)
    pre = (pre * 10 + (seq[i][j] - '0')) % k;

 

pre는 나머지이고 초기 값은 0이다. (처음엔 이전 자릿수까지 계산한 결과가 없으니까) 스트링으로 저장된 i번째 수를 seq[i]라 하자.

 

이전 자릿수까지 구한 나머지는 현재 자릿수보다 한자리 더 크므로 지금까지 구한 나머지에 10을 곱한다. 그리고 지금 자릿수의 자릿값을 더하여 k로 나눈 나머지를 pre에 대입한다. 이를 반복하면 큰 정수를 K로 나눈 나머지를 구할 수 있다.

 

설명이 와닿지 않으면 직접 수를 하나 나눠보자. 이해가 쉽게 될 것이다.

 

그 다음 두 수를 이어 붙인 수의 나머지를 구하는 법을 생각해보자.

 

예를 들어 우리는 집합 {100, 100}이 있고 순열 100, 100에서 100100으로 결합한 후 33으로 나눈 나머지를 구할 것이다.

 

직접 계산하면 $100100 \; mod \; 33 = 11$ 이다.

 

나머지 연산의 분배 법칙을 통해 다음과 같이 식을 나타낼 수 있다.

 

100100 % 33 = 100000 % 33 + 100 % 33 = (100 % 33) * (1000 % 33) + (100 % 33) = 1 * 10 + 1 = 11

 

이렇게 식을 전개하고 나면 두 수를 결합하여 만들어진 수의 나머지를 어떻게 구해야 하는지 알 수 있다.

 

수 a, b가 있고 이 둘을 ab로 이어 붙인 수에 x로 나눈 나머지는 { (a % x) * (10 ^ b의 자릿수 % x) + (b % x) } % x 가 된다.

 

그냥 다 이어 붙인 다음 나머지를 구해도 될텐데 이런 방식을 쓰는 이유가 뭐냐고? 다음 아이디어에서 그 이유가 나온다.

아이디어

순열을 이어 붙인 수가 K로 나눠 떨어지는지 아닌지 구해야 한다. 일일이 나열하면 시간 복잡도가 $O(N!)$이므로 당연히 풀 수 없다.

 

조금 영리하게 생각해보자. 순열 앞부분을 어떤 수로 나눈 나머지를 알고 있는 상태에서 나머지 뒷부분에 순열에 사용되지 않은 수를 붙이는 것을 반복하면 지수 시간 복잡도로 풀 수 있다.

 

여기서 아까 말한 두 수를 이어 붙인 경우 나머지를 구하는 방법을 사용하면 된다.

 

순열 앞부분을 계산한 상태를 알고 있어야 하므로 동적 계획법을 사용해야 한다.

 

동적 계획법으로 풀기 위한 dp 테이블을 다음과 같이 정의할 수 있다.

 

dp[i][j] := 비트마스크 i에 속한 집합으로 구성한 순열에서 K로 나눈 나머지가 j가 되는 경우의 수

 

어떤 순열의 앞부분을 K로 나눈 나머지가 j로 중복되는 경우가 있을 것이고 거기에 아직 사용하지 않은 수를 붙여서 계산하는 것을 반복하여 순열을 완성하면 경우의 수를 효율적으로 구할 수 있다.

구현

바텀-업 dp로 풀자.

 

자릿수가 최대 50이므로 $\Sigma_{i = 1}^{50} (10^{i} \; mod \; K)$를 계산해 배열에 저장해주자.

 

집합에 속한 수도 역시 K로 나눈 나머지를 계산해 배열에 저장해주자.

 

dp 테이블의 초기 상태도 정해주자. 공집합으로 나타낸 순열은 0이고 이를 K로 나눈 나머지는 0이므로 dp[0][0] = 1이다.

 

이제 비트로 나타내지는 조합으로 만들어진 순열에서 구한 나머지 0부터 K - 1까지 나올 수 있는 경우의 수에 대해 사용되지 않은 원소를 붙였을 때 나머지가 될 수 있는 경우의 수로 합산해주어 dp 테이블을 채운다.

 

dp 테이블을 모두 채웠을 때 dp[(1 << n) - 1][0]이 박성원이 원하는 답이다.

 

우리는 박성원이 원하는 답이 나올 확률을 구해야 하므로 최대공약수로 나눠준 기약분수를 출력하면 원하는 결과를 얻을 수 있다.

 

시간 복잡도는 $O(2^{N}KN)$이다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int n, k;
 
ll fact[16];
string seq[16];
ll dp[1 << 15][100];
int tenmodk[51];
int seqmodk[16];
 
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
 
int powermodk(int a, int b)
{
    if (!b) return 1;
    
    if (b & 1) return powermodk(a, b - 1) * a % k;
    
    return powermodk(a * a % k, b / 2);
}
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    cin >> n;
 
    fact[0] = 1;
 
    for (int i = 1; i <= n; ++i)
    {
        fact[i] = fact[i - 1] * i;
        cin >> seq[i - 1];
    }
 
    cin >> k;
 
    for (int i = 0; i <= 50; ++i)
        tenmodk[i] = powermodk(10, i);
    
    for (int i = 0; i < n; ++i)
    {
        int pre = 0;
 
        for (int j = 0; j < seq[i].size(); ++j)
            pre = (pre * 10 + (seq[i][j] - '0')) % k;
        seqmodk[i] = pre;
    }
    
    dp[0][0] = 1;
    
    for (int i = 0; i < (1 << n); ++i)
    {
        for (int j = 0; j < k; ++j)
        {
            if (!dp[i][j])
                continue;
 
            for (int x = 0; x < n; ++x)
                if (!(i & (1 << x)))
                    dp[i | (1 << x)][(j * tenmodk[seq[x].size()] + seqmodk[x]) % k] += dp[i][j];
        }       
    }
 
    ll div = gcd(dp[(1 << n) - 1][0], fact[n]);
    cout << dp[(1 << n) - 1][0] / div << "/" << fact[n] / div;
}