2013-01-06

■ TopCoder SRM531 Div2 600 NoRepeatPlaylist 13:31

要約:1~Nの数字からなる、長さPの数列を考える。このとき、次の条件を満たすものはいくつあるか。

・同じ数字はM以上離れている必要がある。

・すべての数字が一回以上使われている必要がある。

考察:dp(N,M,P)を求めたいものとする。

まず、数列の第P項目に注目する。これがそこまでのP-1個の数字のすべてと異なる場合と、そうでない場合がある。

するとP-1項目までの場合の数は、前者はdp(N-1,M,P-1),後者はdp(N,M,P-1)である。

また、前者は第P項目として1~NのN通りあり、後者はP-1~P-M項目のM個と異なる(N-M)通りがある。

つまりdp(N,M,P)=dp(N-1,M,P-1)*N+dp(N,M,P-1)*(N-M)が成り立つ。

これはO(NMP)ででき、ACできる。

以下ソース。小さいケースの処理が面倒だった

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long dp[101][101][101]={};
class NoRepeatPlaylist{
public:
	int numPlaylists(int N, int M, int P){
		dp[0][0][0]=1;
		for(int i=1;i<=N;i++){
			for(int j=0;j<=i;j++){
				for(int k=1;k<=P;k++){
				if(i==k){
					dp[i][j][k]=1;
					dp[i][j][k]=dp[i-1][0][k-1]*i;
					dp[i][j][k]%=1000000007;
					 continue;
				}
					dp[i][j][k]+=(dp[i-1][j][k-1]*i);
					dp[i][j][k]%=1000000007;
					dp[i][j][k]+=(dp[i][j][k-1]*(i-j));
					dp[i][j][k]%=1000000007;
				}
			}
		}
		return (int)dp[N][M][P];				
	}
};

ツイートする