TopCoder SRM 531 Div1 Easy NoRepeatPlaylist

問題

N曲の曲からP曲を重複を許して、以下の条件を満たすよう選ぶ。
選び方は何通りあるか、mod 10^9 + 7で求めよ。

条件：
全ての曲が少なくとも一度以上選ばれる。
同じ曲は間に少なくともM曲のほかの曲を挟む。

制約条件

N,M,P≦100

方針

dp[i]を、i曲ちょうどを使って、同じ曲の間には少なくともM曲他の曲が挟まっているような曲の選び方の場合の数とする。

dp[M+1]は(M+1)!通りの選び方がある。
i曲「以下」で条件を満たすのは、N*(N-1)*…*(N-M)*(N-M)*…*(N-M)通り。
ここからj曲（j＜i)で条件を満たすものを引けば、i曲ちょうどで条件を満たす曲の選び方の場合の数がわかる。

包除原理を使っても解けるらしい。

ソースコード

const int mod=1000000007;
ll dp[101], C[101][101];

class NoRepeatPlaylist {
	public:
	int numPlaylists(int N, int M, int P) 
	{
		if(M+1>P){
			ll res=1;
			rep(i,N)(res*=i+1)%=mod;
			return res;
		}
		memset(dp,0,sizeof(dp));
		rep(i,101)rep(j,i+1)C[i][j]=i==0||i==j?1:(C[i-1][j-1]+C[i-1][j])%mod;
		
		dp[M+1]=1;
		rep(i,M+1)(dp[M+1]*=i+1)%=mod;
		for(int i=M+2;i<=N;i++){
			ll tmp=1;
			rep(j,P)(tmp*=max(i-j,i-M))%=mod;
			rep(j,i)(dp[i]+=dp[j]*C[i][j]%mod)%=mod;
			dp[i]=(mod-dp[i]+tmp)%mod;
		}
		return dp[N];
	}
};