#include #include #include #include #include using namespace std; // 나머지 계산을 위한 함수 int modCombine(const string& numStr, int K) { long long remainder = 0; for (char c : numStr) { remainder = (remainder * 10 + (c - '0')) % K; } return remainder; } int main() { int N, K; cin >> N; // 집합의 크기 vector nums(N); for (int i = 0; i < N; ++i) { cin >> nums[i]; // 각 수 입력 } cin >> K; // 정수 K 입력 // dp[mask]는 mask에 해당하는 숫자들로 이어붙였을 때 나머지 값 vector dp(1 << N, -1); // -1로 초기화하여 아직 계산되지 않은 상태를 나타냄 dp[0] = 0; // 아무것도 선택하지 않은 경우, 나머지는 0 // 비트마스크를 사용하여 부분 집합을 처리 for (int mask = 0; mask < (1 << N); ++mask) { if (dp[mask] == -1) continue; // 아직 계산되지 않은 경우 // 현재까지 사용된 숫자들을 이어붙여서 나머지를 계산 for (int i = 0; i < N; ++i) { if ((mask & (1 << i)) == 0) { // 아직 i번째 숫자가 포함되지 않았다면 int nextMask = mask | (1 << i); int nextRemainder = (dp[mask] * (int)pow(10, nums[i].size()) + modCombine(nums[i], K)) % K; dp[nextMask] = nextRemainder; } } } // 가능한 모든 부분집합을 다 고려한 후, 나머지가 0인 부분집합을 세기 int total_permutations = 0; int divisible_count = 0; // 마지막까지 다 쓴 경우들에 대해 나머지가 0인 것만 찾는다. for (int mask = 0; mask < (1 << N); ++mask) { if (dp[mask] == 0) { divisible_count++; } total_permutations++; } // 확률 계산 if (divisible_count == 0) { cout << "0/1" << endl; } else if (divisible_count == total_permutations) { cout << "1/1" << endl; } else { // 기약분수로 출력 int divisor = __gcd(divisible_count, total_permutations); cout << divisible_count / divisor << "/" << total_permutations / divisor << endl; } return 0; }

제출 #14678

제출 정보

제출 결과

제출 코드

찾은 반례