**Problem:**

There are two rules for a valid playlist

1 - At least

**M**songs have to be played between any two occurrences of the same song.
2 - Every songs at least played once.

Firstly, let us just consider the first rule.

1. If we list out all invalid and valid arrangements, they can be show in a big searching tree:

2. If the parent break the 1st rule, so as its children.

3. If a i-th layer node has more than M-1 ancestors, a valid node just can have N-M choices in next branch, so it will have N-M children.

__Algorithm__
Let us define DP[i] as following

DP[i]=numbers of leaves(playlists) in i-th layer.

DP[0]=1;

==>DP[i+1]= DP[i]*(N-i) where i < M

DP[i]*(N-M) where i>=M

==>DP[i+1]= DP[i]*(max(N-i,N-M))

==>DP[i]= DP[i-1]*(max(N-i+1,N-M))

where 1<M<N<P<=100

====================================================

Now, let us consider the problem with both first and second rules.

1. Define rule2(N) = it is true when all songs 1....N have been played once.

2. If the parent meets rule2(N), so as its children.

i.e. If a playlist uses N songs, it will be the same as it is longer.

3. If a playlist meets rule2(N-1), it must not meet rule2(N)

i.e. If a playlist just uses N-1 songs, this playlist cannot use other songs.

4. If the parent meets rule2(j), only (N-j) choice of its children meet rule2(j+1).i.e. If a playlist just uses N-1 songs, this playlist cannot use other songs.

i.e. If a playlist is using j songs, the only way to make this playlist using j+1 songs is:

Add a new song which is not belong to 1...j.

And you can have N-j choices in this case.

Add a new song which is not belong to 1...j.

And you can have N-j choices in this case.

Let us define DP[i][j] as following

DP[i][j] = # of playlist in ith layer (play list length=i), if we just consider j songs (1....j)

**and**the playlist meet the rules 1(non-repeat in last m song)

and rule2(j)=(Just j songs are picked).

DP[i][j] in i-th layer is contributed by the values of two types of playlist in its upper layer, (i-1)th layer.

- This playlist meet Rule2(N-1), but must not meet Rule2(N).

so, no playlist exist in both DP[i-1][N] and DP[i-1][N-1]

- If we want next level playlist meet Rule2(N), there are only (1) choice on the song.

That mean only one child for this node in layer (i-1)th.

- In general, there will be N-(j-1) choices for a new song in order to make this playlist meet rule2(j) .

==> DP[i][j] += DP[i-1][j-1]*(N-j+1)

Type 2 : Playlists were counted in DP[i-1][N]

All playlists have been counted in DP[i-1][N] meet rule 1 and 2.

5. If the parent meet the 2nd rule, so as its children.

6. If the parent break the 1st rule, so as its children.

==> If the parent keep the 1st rule, there should be N-M choices for a child to pick a new song in order to keep rule1.

In general, there should be j-M choices for a playlist in D[i-1][j]

5. If the parent meet the 2nd rule, so as its children.

6. If the parent break the 1st rule, so as its children.

==> If the parent keep the 1st rule, there should be N-M choices for a child to pick a new song in order to keep rule1.

In general, there should be j-M choices for a playlist in D[i-1][j]

But please also notice that if(j<M), this playlist will fail to meet rule 2(M). (j songs are not enough.)

==> DP[i][j] += DP[i-1][j]*(max(j-M,0))

N=50,M=5,P=100

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,2450,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,117600,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,(i<j zero area)0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,5527200,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,254251200,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,417372479,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,252117430,947016478,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,921607339,682098833,774691803,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,260587143,675411789,746917981,762363706,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,938546765,231482425,354966845,435455513,494548030,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

(j<M zero area)

0,0,0,0,0,0,441303923,294465995,51957883,142129153,730918098,385508560,287373037,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,6304462,817911350,750747684,481885700,549775063,46444980,920175336,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,429981403,724825902,355267177,190083313,574078224,766342170,126311865,46487194,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,441303923,277335278,663677895,863756375,516370717,47801787,753445737,131497170,91923716,673538977,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

... <truncated>

Hence, the C++ code will be:

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define MOD 1000000007

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#include <iostream>

using namespace std;

class NoRepeatPlaylist

{

public:

int numPlaylists(int n,int m,int p)

{

ll dp[102][102];

rep(i,0,101)rep(j,0,101)dp[i][j]=0;

dp[0][0]=1;

rep(i,1,p)

{

rep(j,1,n)

{

dp[i][j]=(dp[i-1][j]*max(j-m,0)+dp[i-1][j-1]*(n-j+1))%MOD;

}

}

return (int)dp[p][n];

};

};

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define MOD 1000000007

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#include <iostream>

using namespace std;

class NoRepeatPlaylist

{

public:

int numPlaylists(int n,int m,int p)

{

ll dp[102][102];

rep(i,0,101)rep(j,0,101)dp[i][j]=0;

dp[0][0]=1;

rep(i,1,p)

{

rep(j,1,n)

{

dp[i][j]=(dp[i-1][j]*max(j-m,0)+dp[i-1][j-1]*(n-j+1))%MOD;

}

}

return (int)dp[p][n];

};

};

## No comments:

## Post a Comment