1086번: 박성원 –

https://www.acmicpc.net/problem/1086

dp(i)(j) : i = 나머지 순열, j = 완료된 순열(비트 마스킹)

핵심은 나머지 순열로 dp를 설계하는 것이 었습니다.

큰 수 나눗셈, 최대공약수(gcd), 비트마스킹 dp를 조합하면 풀 수 있는 문제였다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, K;
string N_set(15);
ll dp(100)(32768); //dp(i)(j) : i = 순열의 나머지, j = 이룬 순열(비트마스킹)
int MOD(100)(15); //MOD(i)(j) : i = 현재 나머지, N_set(j)

ll gcd(ll a, ll b)
{
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int division(int res, string a)
{
    for (int i{ 0 }; i < a.length(); i++)
    {
        res = res * 10 + (a(i) - '0');
        res %= K;
    }
    return res;
}

ll solve(int mod, int idx) //mod : 순열의 나머지, idx : 이룬 순열
{
    if (dp(mod)(idx) != -1) return dp(mod)(idx);
    if (idx == (1 << N) - 1)
    {
        if (mod) return dp(mod)(idx) = 0;
        else return dp(mod)(idx) = 1;
    }

    ll sum{ 0 };
    for (int i{ 0 }; i < N; i++)
    {
        if (idx & (1 << i)) continue; //이미 봤던 정수라면 건너뛴다.

        sum += solve(MOD(mod)(i), idx | (1 << i));
    }

    return dp(mod)(idx) = sum;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N;
    for (int i{ 0 }; i < N; i++) cin >> N_set(i);
    cin >> K;
    //입력

    memset(dp, -1, sizeof(dp)); //초기화

    for (int i{ 0 }; i < 100; i++)
    {
        for (int j{ 0 }; j < N; j++)
        {
            MOD(i)(j) = division(i, N_set(j));
        }
    }

    ll num = solve(0, 0);
    ll den{ 1 };
    for (int i{ 1 }; i <= N; i++) den *= i;

    ll g = gcd(den, num);
    cout << num / g << "/" << den / g;
}