SRM531 Div1 Easy(300), Div2 Medium(600) NoRepeatPlaylist

TopCoder

NoRepeatPlaylist

動的計画法。i曲目を聴き終わった時点でj種類の曲を聴いている場合の数を覚えておく。それをT[i][j]とすると、

T[i][j] = T[i-1][j-1]*(N-j+1) + T[i-1][j]*max(j-M,0)

が成り立つ。なぜなら、1曲前まででj-1種類の曲を聴いているならば、今までに聴いていない曲はN-j+1曲。1曲前まででj種類の曲を聴いているならば、今までに聴いた曲はj曲。ただし、直前M曲は聴くことができないので、j-M。

#include <vector>
using namespace std;

class NoRepeatPlaylist{public:
int numPlaylists( int N, int M, int P )
{
    vector<vector<long long> > T( P+1, vector<long long>(N+1) );
    T[0][0] = 1;
    for ( int i=1; i<=P; i++ )
    for ( int j=1; j<=N; j++ )
        T[i][j] = ( T[i-1][j-1]*(N-j+1) + T[i-1][j]*max(j-M,0) ) % 1000000007;
    return (int)T[P][N];
}};