백준 1086 / C++

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

1086번: 박성원

 

[ 풀이 ] 

N이 작고 순열의 각 원소의 순서가 중요하므로 비트DP로 순회하자. 

p1 p2 .... pn 순으로 간다고 하자. p1에서 p2로 갈 때 수는 p1*10^(p2의 길이)+p2 가 된다.

p2의 길이는 최대 50이므로 단순 계산으론 안되고 미리 10^m (modk)를 전처리해놓으면 된다.

p_i들 또한 k로 나눈 나머지만 중요하므로 순회하면서 모두 k로 나눈 나머지로 전처리해놓자.

이제 dp식을 세우자. dp[bit][v]는 현재 상태와 값을 알 때, k로 나눠지는 수의 개수라고 하자. 

다음 인덱스 i를 볼 때, 식에서 v가 다음턴엔 v*10^(p[i]길이)+p[i] (mod k)가 됨을 알 수 있다.

모든 경우를 더해주고, 기저상태는 인덱스를 모두 채웠을 때 v값이 0이면 1을 뱉어주면 된다.

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string num[55];
ll n, k, a[55], len[55], mul[55], dp[1 << 15][101];

// 10^m (mod k) 전처리 
void make_table(int k) {
	mul[0] = 1;
	for (int i = 1; i <= 50; i++) {
		mul[i] = mul[i - 1] * 10 % k;
	}
}

// dp[bit][v]=sum(dp[bit'][v'%k])
ll go(int bit, ll v) {
	if (bit + 1 == (1 << n)) return (v == 0); // base case
	ll& ret = dp[bit][v];
	if (~ret) return ret;
	ret = 0;
	for (int i = 0; i < n; i++) {
		if (bit & (1 << i)) continue;
		ret += go(bit | (1 << i), (v * mul[len[i]] + a[i]) % k);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	ll fac = 1;
	for (ll i = 0; i < n; i++) {
		cin >> num[i];
		fac *= (i + 1);
	}
	cin >> k;
	for (int i = 0; i < n; i++) {
		len[i] = (int)num[i].size(); 
		int t = 0;
		// num[i]%k = a[i]
		for (auto s : num[i]) {
			t *= 10; t %= k;
			t += (s - '0'); t %= k;
		}
		a[i] = t;
	}
	make_table(k);
	memset(dp, -1, sizeof(dp));
	// 답은 go(0,0)/n! 이 된다. 
	ll p = go(0, 0), q = fac;
	ll g = gcd(p, q);
	if (p == 0) {
		cout << 0 << "/" << 1 << '\n';
	}
	else {
		cout << p / g << "/" << q / g << '\n';
	}
}