BOJ. SeongYeon Park (1086)

On this page

Problem: BOJ 1086 — SeongYeon Park · 한국어 · 日本語

Subset dynamic programming

The input contains N strings. A permutation chooses an ordering of their positions; even when two strings have identical contents, their positions are distinct choices and contribute separate permutations. There are N! equally likely orderings.

Let dp[mask][r] be the number of ways to concatenate exactly the strings selected by mask so that the resulting number has remainder r modulo K. The empty concatenation has remainder zero, so dp[0][0] = 1. For each string i, precompute its remainder value[i] modulo K, and precompute power[len] = 10^len mod K for lengths up to the total input length.

Appending string i to a concatenation with remainder r and current length len gives remainder

nextRemainder = (r * power[length[i]] + value[i]) mod K.

Thus, for every unused index i, add dp[mask][r] to dp[mask | (1 << i)][nextRemainder]. The transition iterates over indices, not distinct string values, which correctly counts repeated input strings as distinguishable positions. Once all positions are used, dp[(1 << N) - 1][0] is the number of divisible permutations.

The probability is that count divided by N!. Reduce the fraction by their greatest common divisor; when the count is zero, print 0/1 directly. N <= 15, so every state count and 15! fit in a signed long. With 2^N masks, K remainders, and at most N transitions per state, the time complexity is O(N K 2^N) and the space complexity is O(K 2^N).

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        String[] numbers = new String[n];
        int totalLength = 0;
        for (int i = 0; i < n; i++) {
            numbers[i] = input.next();
            totalLength += numbers[i].length();
        }
        int k = input.nextInt();

        int[] value = new int[n];
        int[] length = new int[n];
        for (int i = 0; i < n; i++) {
            length[i] = numbers[i].length();
            int remainder = 0;
            for (int j = 0; j < length[i]; j++) {
                remainder = (remainder * 10 + numbers[i].charAt(j) - '0') % k;
            }
            value[i] = remainder;
        }

        int[] power = new int[totalLength + 1];
        power[0] = 1 % k;
        for (int len = 1; len <= totalLength; len++) {
            power[len] = (int) ((long) power[len - 1] * 10 % k);
        }

        int states = 1 << n;
        long[][] dp = new long[states][k];
        dp[0][0] = 1;
        for (int mask = 0; mask < states; mask++) {
            for (int remainder = 0; remainder < k; remainder++) {
                long ways = dp[mask][remainder];
                if (ways == 0) {
                    continue;
                }
                for (int i = 0; i < n; i++) {
                    if ((mask & (1 << i)) == 0) {
                        int nextRemainder = (int) (
                            ((long) remainder * power[length[i]] + value[i]) % k
                        );
                        dp[mask | (1 << i)][nextRemainder] += ways;
                    }
                }
            }
        }

        long numerator = dp[states - 1][0];
        if (numerator == 0) {
            System.out.println("0/1");
            return;
        }

        long denominator = 1;
        for (int i = 2; i <= n; i++) {
            denominator *= i;
        }
        long divisor = gcd(numerator, denominator);
        System.out.println((numerator / divisor) + "/" + (denominator / divisor));
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    private static class FastScanner {
        private final BufferedReader reader =
            new BufferedReader(new InputStreamReader(System.in));

        String next() throws IOException {
            StringBuilder token = new StringBuilder();
            int c;
            do {
                c = reader.read();
            } while (c <= ' ' && c != -1);
            while (c > ' ') {
                token.append((char) c);
                c = reader.read();
            }
            return token.toString();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}