SRM 531 div1 easy: NoRepeatPlaylist

問題

TopCoder Statistics - Problem Statement

解法

包除原理で解きました。

i 個以下の曲を使って P 曲を並べる場合, 最初の曲は i 通り, 次の曲は i-1 通り, ..., M 曲目は i-M 通り, となり, それ以後は i-M 通りだけ使える曲があります。

i 個の曲の選び方は C[N][i] で求められるので, 上の計算でこれを掛け算したものを これを f(i) とすると, N 曲ぴったり使う P 曲の並べ方は, f(N) - f(N-1) + f(N-2) - ... と求められます。

const ll MOD = 1e9+7;
ll C[111][111];

class NoRepeatPlaylist {
public:
    int numPlaylists(int N, int M, int P) {
        if (M > N) return 0;
        if (P < N) return 0;
        for (int i = 0; i < 111; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = C[i-1][j-1] + C[i-1][j];
                C[i][j] %= MOD;
            }
        }
        ll ans = 0;
        for (int i = M; i <= N; i++) {
            ll tmp = 1;
            for (int j = 0; j < P; j++) {
                (tmp *= i-min(j, M)) %= MOD;
            }
            (tmp *= C[N][i]) %= MOD;
            if ((N-i)%2 == 0) ans += tmp;
            else ans -= tmp;
            ans %= MOD;
        }
        (ans += MOD) %= MOD;
        return ans;
    }
};