BOJ. Hue Circle (2482)

[Link] https://www.acmicpc.net/problem/2482 · 한국어 · 日本語

We must choose K of the N positions on a circle so that no two selected positions are adjacent, including the first and last positions. Let line(L, k) count ways to choose k nonadjacent positions from a line of length L. The chosen positions need at least one unchosen position between consecutive choices, so

line(L, k) = C(L - k + 1, k)

when 0 <= k <= L - k + 1; otherwise it is zero. In particular, choosing zero positions has one way, and negative or impossible arguments contribute zero.

Split the circular choices into two disjoint cases:

1. If the first position is selected, its two neighbors cannot be selected. The remaining N - 3 positions form a line, from which we choose K - 1: line(N - 3, K - 1).
2. If the first position is not selected, the other N - 1 positions form a line, from which we choose K: line(N - 1, K).

Add these counts and take the result modulo 1,000,000,003. The cases cover every selection exactly once. The implementation builds Pascal’s triangle only through the required K columns, obtaining each needed binomial coefficient in O(NK) time and O(NK) space. This is small for N <= 1000 and also avoids factorial division modulo a non-prime modulus.

Handle boundaries before building the table: selecting zero positions has one way; N = 1 has one way for K = 1 and zero for other positive K; N = 2 has two ways for K = 1 and zero for larger K. Invalid N or K and any K > floor(N / 2) for N > 1 yield zero. The first two cycle sizes are explicit because the usual split assumes three distinct positions.

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

public class Main {
    private static final int MOD = 1_000_000_003;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine().trim());
        int k = Integer.parseInt(input.readLine().trim());

        if (n < 1 || k < 0 || k > n) {
            System.out.println(0);
            return;
        }
        if (k == 0) {
            System.out.println(1);
            return;
        }
        if (n == 1) {
            System.out.println(k == 1 ? 1 : 0);
            return;
        }
        if (n == 2) {
            System.out.println(k == 1 ? 2 : 0);
            return;
        }
        if (k > n / 2) {
            System.out.println(0);
            return;
        }

        int[][] binomial = new int[n + 1][k + 1];
        for (int row = 0; row <= n; row++) {
            binomial[row][0] = 1;
            for (int column = 1; column <= Math.min(row, k); column++) {
                int value = binomial[row - 1][column]
                        + binomial[row - 1][column - 1];
                binomial[row][column] = value >= MOD ? value - MOD : value;
            }
        }

        int answer = binomial[n - k - 1][k - 1]
                + binomial[n - k][k];
        if (answer >= MOD) {
            answer -= MOD;
        }
        System.out.println(answer);
    }
}