TopCoder SRM 700 Div2 Hard XYZCoder

そういえば１月ぶりぐらいにSRMの事を書いている。
https://community.topcoder.com/stat?c=problem_statement&pm=14401

問題

R*S人の参加者でSRMを行い、1～(R*S)番まで順位を付けた。その際タイはいなかった。
R個の部屋でS人ずつ参加者がいたとする。
各部屋のLeaderの順位を並べたとき、できる数列の組み合わせは何通りか。

解法

以下のDPを行えばよい。
dp(r,l) := r個の部屋のroom leaderの順位が未確定で、room leaderの順位は決まったが自分自身の順位が決まらない人の人数がl人の場合の問題文に示す組み合わせ

1番から順に順位を付ける際、room leaderから選ぶ場合とそうでない人から選ぶ場合を足していけば良い。
Leaderの順位は気にするが、それ以外の人の順位は気にしないので以下のようになる。(1人room leaderの順位が決まると、(s-1)人後者の人数が増える。)
dp(r,l) = r*dp(r-1,l+s-1) + dp(r,l-1)

ll mo=1000000007;
ll memo[101][10101];
class XYZCoder {
	public:
	
	ll dpdp(int r,int s,int l) {
		if(r==0) return 1;
		if(memo[r][l]>=0) return memo[r][l];
		
		memo[r][l]=r*dpdp(r-1,s,l+s-1)%mo;
		if(l) (memo[r][l]+=dpdp(r,s,l-1))%=mo;
		return memo[r][l];
	}
	
	int countWays(int room, int size) {
		MINUS(memo);
		return dpdp(room,size,0);
	}
}

まとめ

割とシンプル。