TopCoder SRM609: VocaloidsAndSongs

典型的なDP。

dp[gumiNum, iaNum, mayuNum] = それぞれの歌手が歌うパターン数

で状態を持てば良い。ただし７通りの遷移の部分は手で書きたくなかったのでビットを使ったループ処理に置き換えている。

public class VocaloidsAndSongs {
    public int count(int S, int gumi, int ia, int mayu) {
        int mod = 1000000007;
        var dp = new int[S + 1, S + 1, S + 1];
        dp[0, 0, 0] = 1;
        for (int i = 0; i < S; i++) {
            var next = new int[S + 2, S + 2, S + 2];
            for (int bit = 1; bit < 8; bit++) {
                int p1 = (bit >> 0) % 2;
                int p2 = (bit >> 1) % 2;
                int p3 = (bit >> 2) % 2;
                for (int a = 0; a < S + 1; a++) {
                    for (int b = 0; b < S + 1; b++) {
                        for (int c = 0; c < S + 1; c++) {
                            next[a + p1, b + p2, c + p3] += dp[a, b, c];
                            next[a + p1, b + p2, c + p3] %= mod;
                        }
                    }
                }
            }
            dp = next;
        }
        return dp[gumi, ia, mayu];
    }
}