SRM531 Div1 Easy

300
DPする。
DP[どこまで使ったたか][どこまで作ったか]
今まで使った曲をまた使う or 新たな曲を使う


本番中、[どこまで使ったたか]と[どこまで作ったか]はすぐに考えついたけど、そこから先が分からなかった。
Mコ前が必ず全て異なると何故考えつかなかったのか。悲しい。
覚えるのに[100]が100コ要るから無理だとスルーしてたし。

class NoRepeatPlaylist {
public:
  int numPlaylists(int N, int M, int P)
  {
    const lli mod = 1000000007;

    lli t[N + 1][P + 1];
    fill(&t[0][0], &t[N][P + 1], 0);

    t[1][1] = 1;

    for (int n = 0; n <= N; ++n) {
      for (int p = 0; p < P; ++p) {

        t[n][p + 1] += t[n][p] * max(n - M, 0);
        t[n][p + 1] %= mod;
        
        if (n != N) {
          t[n + 1][p + 1] += t[n][p] * (N - n + 1);
          t[n + 1][p + 1] %= mod;
        }
      }
    }

    return t[N][P];
  }

};