DP 문제인데, 생각보다 발상이 까다롭다. 당연히 모든 순열을 완전 탐색했다간 15!가지의 경우를 탐색해야 하므로 시간 초과가 발생한다. 그리고 집합에 포함된 수도 길이가 50까지인 자연수 범위로 상당히 크기 때문에, 수를 만든 후에 모듈러 연산을 적용하는 부분도 쉽지 않다.
따라서, 먼저 매우 큰 수에 대한 모듈러 연산을 어떻게 처리할지 생각해 봐야 한다. 물론 문자열 형태로 만들어 한 글자씩 처리하는 방법도 있겠지만, 그렇게 하겠다면 적어도 나는 위 문제를 제 시간 안에 풀어낼 로직이 떠오르지 않는다.
모듈러 연산은(합동식) 덧셈, 뺄셈, 곱셈에 대해 분배법칙이 성립하는 연산이고 나눗셈에 대해서는 성립하지 않는다(그래서 페르마의 소정리를 이용해 곱셈 꼴로 바꿔서 해결한다). 따라서 문제에서 예시로 주어지는 {5221,40, 1, 58, 9}로 만든 5,221,401,589 % K의 경우 다음과 같이 생각할 수 있다.
(5,221,000,000 + 400,000 + 1,000 + 580 + 9) % K
(5,221,000,000%K + 400,000%K + 1,000%K + 580%K + 9%K) % K
((5,221*10^6)%K + (40*10^4)%K + (1*10^3)%K + (58*10^1)%K + (9*10^0)%K) % K
(((5,221%K)*(10^6%K))%K + ((40%K)*(10^4%K))%K + ((1%K)*(10^3%K))%K + ((58%K)*(10^1%K))%K + ((9%K)*(10^0%K))%K) % K
가독성이 조금 떨어지긴 하겠으나, 위 식은 모두 합동이다. 눈치챌 수 있듯, 집합 내의 수들에 대해 미리 나머지를 구해두고, 순열에 배치되는 순서에 따라 적절하게 10^n을 곱하는 꼴로 만들 수 있고 각각에 대해 모듈러 연산을 적용할 수 있다.
위와 같은 식으로 변형하게 된다면 이런 생각도 가능하다. 어차피 모듈러 연산을 이용한다면 모든 순열을 다 찾을 필요가 없고 일정 범위의 나머지 값들만 활용하면 된다. K의 범위가 100보다 작거나 같은 자연수이므로 모듈러 연산의 결과 또한 0~99의 범위일 것이다. 집합 내의 특정 원소들을 사용해 만든 나머지가 k인 경우의 수를 바탕으로 dp[선택 상태][k]를 구성한다고 생각해 보면, O(2^N * N * K)의 복잡도로 모든 경우를 탐색할 수 있다.
dp[선택 상태][k]에서 아직 선택되지 않은 원소를 사용해, 다음 상태를 만들고 다음 상태를 만들었을 때의 나머지도 위의 모듈러 연산 성질로 빠르게 구해내 현재의 값을 더해주는 식으로 진행한다.
빠른 연산을 위해 미리 10^N 꼴에 대한 나머지 값들과 각 원소들에 대한 나머지 값들을 전처리해 두고 사용했다.
선택 상태의 경우 비트 마스킹을 이용해 쉽게 나타낼 수 있고, 실제 구현에서도 그렇게 구현했다. 마지막으로 정답을 기약 분수 꼴로 출력해야 하는데, 이는 GCD를 구해 분자와 분모를 각각 나눠주도록 했다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long dp[1<<15][100] = {0, };
int getRemainder(const string& num, int divisor) {
int prevNum = 0;
for(auto c: num) {
prevNum = (prevNum*10+(c-'0')) % divisor;
}
return prevNum;
}
long long gcd(long long l, long long r) {
long long big, small;
big = max(l, r);
small = min(l, r);
while(small != 0) {
long long remain = big % small;
big = small;
small = remain;
}
return big;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n;
vector<string> numSet(n);
vector<int> remainderArr(n);
vector<int> decimalRemainderArr(51);
for(int i=0; i<n; i++) {
cin >> numSet[i];
}
cin >> k;
for(int i=0; i<n; i++) {
remainderArr[i] = getRemainder(numSet[i], k);
}
decimalRemainderArr[0] = 1%k;
for(int i=1; i<51; i++) {
decimalRemainderArr[i] = (decimalRemainderArr[i-1]*10) % k;
}
int bitRange = 1 << n;
dp[0][0] = 1;
for(int i=0; i<bitRange; i++) {
for(int j=0; j<n; j++) {
if((i&(1<<j)) == 0) {
for(int l=0; l<k; l++) { // cur == dp[i][l]
int target = ((l*decimalRemainderArr[numSet[j].length()])%k + remainderArr[j]) % k;
dp[i|1<<j][target] += dp[i][l];
}
}
}
}
long long p, q=1;
p = dp[(1<<n)-1][0];
for(int i=1; i<=n; i++) {
q *= (long long)i;
}
long long gcdResult = gcd(p, q);
cout << p/gcdResult << "/" << q/gcdResult;
}