백준[1086] 박상원

 

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

 

 

모든 탐색을 돌면 $15!$가지 경우의 수가 나온다.

하지만, 입력된 $N$개의 원소를 가지는 집합 $S$가 있을 때 부분집합 $s\subset S$이 있다고 하자.

부분집합 $s$로 합칠 수 있는 숫자들을 $num_i$라고 하면 $\text{cache}[\text{s}][\text{num}]$에 모듈러 연산을 했을 때 0이 되는 경우의 수를 저장할 수 있다.

 

어떤 부분집합 $s, (a\not\in s)$에 대해 조합한 $\text{num}$에서 $a$를 오른쪽에 추가했을 경우 다음과 같이 모듈러 연산을 할 수 있다.
$$\text{num} := (\text{num}*10^{len_a-1}\mod k+a)\mod k$$

$len_a$는 a의 길이이다.

 

메모제이션을 적용해 시간 복잡도를 계산하면 모든 조합의 수 $2^N$, 각 조합에서 for문 $N$번 도니까 결국 $O(2^N*N)$이다.

 

결론적으론 메모제이션을 이요해 최적화하는 문제이다.

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <math.h>
#include <map>
#include <climits>
#include <set>
#include <string>
#include <string.h>
#define INF 987654321
#define MAX_N 15
#define lld long long int
#define pii pair<int, int>
// #define DEBUG

using namespace std;

int N, k;
pii p[MAX_N];
int tens[51];
lld cache[(1 << MAX_N)][111];

lld solve(int s, int num) {
	if(s == (1 << N) - 1) return (num % k == 0);
	lld& ret = cache[s][num];
	if(ret != -1) return ret;
	ret = 0;
	for(int i = 0; i < N; i++) {
		if(s & (1<<i)) continue;
		lld next = num * tens[p[i].second] + p[i].first; // 현재에서 오른쪽에 끼운다.
		next %= k;
		ret += solve(s | (1 << i), next);
	}
	return ret;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	lld all = 1;
	cin >> N;
	vector<string> s(N);
	for(int i = 0; i < N; i++) {
		cin >> s[i];
		all *= (i+1);
	}
	cin >> k;
	tens[0] = 1;
	for(int i = 1; i < 51; i++) {
		tens[i] = (tens[i-1]*(10%k)) % k;
	}
	for(int i = 0; i < N; i++) {
		p[i].second = s[i].size();
		for(int j = 0; j < s[i].size(); j++) {
			p[i].first = (p[i].first * (10 % k)) + (s[i][j]-'0') % k;
			p[i].first %= k;
		}
	}
	memset(cache, -1, sizeof(cache));
	lld cnt = solve(0, 0);
	lld g = gcd(all, cnt);
	cout << cnt/g << '/' << all/g;
	return 0;
}

/*
x % k
(x*10^n) % k
(x%k * 10^n%k) % k


a % k
(a*10^n+b) % k
((a % k * 10^n % k) % k + b % k) % k


*/