東京工業大学プログラミングコンテスト2015 J - 指さし

コンテスト中最後まで満点取れなかった問題。

問題

ttpc2015.contest.atcoder.jp

解法

dp[rest][ok] = (残り人数が rest 人で, すでに K 人での巡換を作ったかのフラグが ok であるような, 場合の数)とします。

dp[rest][ok] から, rest 人中選ぶ人数 k のループを回して, 次の状態を考えます。
重複を避けるために, 一番先頭の人は必ず選ぶと考えます。残りの rest-1 人中 k-1 人を選ぶ場合の数は, 通りで, これは巡換なので, その並び方は 通りです。
k = K だった場合は, K 人の巡換を作ったというノルマを達成したので ok = 1 になります。ということで,
dp[rest-k][nextOK] += dp[rest][ok] * nPk(rest-1, k-1)
となります。

得た知見

• 以外に 2 変数あっても 1 次元 DP でできるのってあるんだよな
  • なんとなく技術室奥コンテストの大きな数をつくったを思い出した
• 重複しないように数えるのに苦労していたが, 「先頭の人だけ選ぶ」「残りの人の配置を考える」で考えればよかったんだね

const ll MOD = 1e9+7;
ll fact[1024], nCr[1024][1024];

ll dp[1024][2];
int N, K;

ll nPk(int n, int k) {
    return (nCr[n][k] * fact[k]) % MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 1024; i++) {
        nCr[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            nCr[i][j] = (nCr[i-1][j-1] + nCr[i-1][j]) % MOD;
        }
    }
    fact[0] = 1;
    for (int i = 1; i < 1024; i++) fact[i] = (fact[i-1] * i) % MOD;
    cin >> N >> K;
    dp[N][0] = 1;
    for (int rest = N; rest >= 0; rest--) {
        for (int ok = 0; ok < 2; ok++) {
            for (int k = 2; k <= min(K, rest); k++) {
                int nok = ok;
                if (k == K) nok = 1;
                dp[rest-k][nok] += (dp[rest][ok]*nPk(rest-1, k-1)) % MOD;
                dp[rest-k][nok] %= MOD;
            }
        }
    }
    cout << dp[0][1] << endl;
    return 0;
}