不参加だった回。
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にしてはちょっと難しめ?