SRM531 NoRepeatPlaylist

この問題、全然わからんかった。
答えみても暫くわからんかったし、答えみたあとに自分で書いても
間違ってたし。
でも、この問題のお陰で、DPとかメモ化とかいろんん技法を勉強できたの
はよかったな。
あと、以外に難しい問題でも問題を簡単にして、あとで変形していく
方法は使えるとわかった。

あーでも、自信が粉砕したことは確か。
こんな俺でも一流になって
いつか振り返って、いろんな人に勇気を与える日記になるようがんばる。

以下、ソースコード

#include <iostream>

#define MAX_P 100

#define MAX_N 100

#define MIN(X,Y) (((X) < (Y)) ? (X) : (Y))

#define MAX(X,Y) (((X) > (Y)) ? (X) : (Y))

#define IFZEROONE(X) (((X) == 0) ? 1: (X)) 
#define MODULO 1000000007

class NoRepeat{

private:

  long long dp[MAX_P+1][MAX_N+1];

public:

  int foo(int, int, int);

  void showDP(int, int, int);

};
int NoRepeat::foo(int N, int M, int P){
  memset(dp, 0, sizeof(dp));

  //this->showDP(N, M, P);
  int a, b;

  dp[0][0] = 1;

  for(int i=1; i<=P; i++){

    for(int j=1; j<=N && j<=i; j++){

      // j is number of songs which has been played already.

      

      if( i > M && i > 1){ // choose same song

        dp[i][j] = ( dp[i-1][j] * MAX(( (N-M) - (N-j) ), 0) ) % MODULO;

      }

      // choose a new song

      //dp[i][j] += dp[i-1][j-1] * MIN( (N-j+1), (N-M) ); // this is wrong,,,

      dp[i][j] = (dp[i][j] + (dp[i-1][j-1] * (N-j+1)) % MODULO) % MODULO;
      //printf("i=%d, jj=%d\n", i, j);

      //this->showDP(N, M, P);

    }

  }
  return (int)dp[P][N];

}