BOJ 1086 박성원

개요

BOJ 1086 박성원

• 백준 온라인 저지 1086번 문제
• BOJ 40단계

C++

#include <bits/stdc++.h>
using namespace std;

int N, K;
string nums[16];
pair<int,int> p[16];
int A[51];
long dp[1 << 15][100];
 
long getDP(int s, int num) {
    if (s == (1 << N) - 1) return (num % K == 0);
    long &ret = dp[s][num];
    if (ret != -1) return ret;
    ret = 0;
    for (int i=0; i<N; i++) {
        if (s & (1 << i)) continue;
        long nextNum = (num * A[p[i].second] + p[i].first) % K;
        ret += getDP(s | (1 << i), nextNum);
    }
    return ret;
}

void solve() {
    long all = 1;
    for (int i=0; i<N; i++) {
        all *= i + 1;
    }
    A[0] = 1 % K;
    for (int i=1; i<55; i++) {
        A[i] = (A[i-1] * 10) % K;
    }
    for (int i=0; i<N; i++) {
        reverse(nums[i].begin(), nums[i].end());
        p[i].second = nums[i].size();
        for (int j=0; j<nums[i].size(); j++) {
            p[i].first += (nums[i][j]-'0') * A[j] % K;
        }
        p[i].first %= K;
    }
    memset(dp, -1, sizeof(dp));
    long cnt = getDP(0, 0);
    long g = gcd(all, cnt);
    long p = cnt / g;
    long q = all / g;
    cout << p << '/' << q;
}
 
int main() {
    cin >> N;
    for (int i=0; i<N; i++) {
        cin >> nums[i];
    }
    cin >> K;
    solve();
}