Codeforces #745 Div1 : B. Mathematics Curriculum

不参加だった回。
https://codeforces.com/contest/1580/problem/B

問題

1～NのPermutation Cがあったとき、整数Xが良いとは、CにおいてXを含む部分列のうち、最大値はちょうどM通り取れることをいう。
N,M,Kが与えられる。
1～NのPermutationのうち整数Xが良いものであるようなXがちょうどK個になるものは何通りか。

解法

F(L,S,D) := 長さLのPermutationのうち、最大値がS通り取れるものがちょうどD通りである組み合わせ
とする。F(N,M,K)が求めたい値である。
F(L,S,D)を求める際、最大値がどこにあるかと、その左右の数列を総当たりしていくと良い。
O(N^2*M^2*K)かかるが、定数倍が小さめなので間に合う。

int N,M,K,P;
ll mo;
static const int N_=1020;
static ll C_[N_][N_];
static ll fact[N_+1];

ll dp[101][101][101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K>>mo;
	FOR(i,N_) C_[i][0]=C_[i][i]=1;
	for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	fact[0]=1;
	for (int i=1;i<=N_;++i) fact[i]=fact[i-1]*i%mo;
	
	FOR(i,M+1) dp[0][i][0]=1;
	for(i=1;i<=N;i++) dp[i][1][1]=fact[i];
	for(i=1;i<M;i++) {
		for(int lef=0;lef<N;lef++) for(int ml=0;ml<=lef;ml++) if(dp[lef][i][ml]) {
			for(int ri=0;lef+ri<N;ri++) for(int mr=0;mr<=ri;mr++) if(dp[ri][i][mr]) {
				(dp[lef+ri+1][i+1][ml+mr]+=C_[lef+ri][lef]*dp[lef][i][ml]%mo*dp[ri][i][mr])%=mo;
			}
		}
	}
	
	cout<<dp[N][M][K]<<endl;
}

まとめ

1000ptにしてはちょっと難しめ？