AtCoder ARC #138 (大和証券プログラミングコンテスト2022 Spring) : E - Decreasing Subsequence

うーん、考察が難しい。
https://atcoder.jp/contests/arc138/tasks/arc138_e

問題

整数Nに対し、整数列Aを以下のように定める。

• 0≦A[i]≦i (1-origin)
• 1以上の値は、A中でそれぞれ高々1回しか登場しない。

あり得る上記整数列A全通りにおける、下記の選び方の総数を求めよ。

• AのK要素の部分列のうち、正整数のみで構成され、かつ降順になっているもの

解法

Aの条件を以下のように言い換える。
ラベル0～Nの(N+1)頂点からなる有向グラフを考える。
A[i]が正の場合、i→(A[i]-1)と辺を張る。
Aの条件より、これらの辺は複数のパスを成すし、入次数・出次数は高々1である。

部分列の選び方は、これらのパスがK重にネストしている箇所を選ぶことに相当する。
R[i]→L[i]に辺が張られているとき、L[1]＜L[2]＜…＜L[K]＜R[K]＜R[K-1]＜…＜R[1]となるようなK要素の整数列L,Rを選べばよい。

この考察をもとに元の問題を解く。
L[K]の値を固定し、総当たりしよう、L[1]～L[K-1]と、R[1]～R[K]の選びかたは、この時点で二項係数で容易に求められる。
あとはこれら2K個の頂点に含まれない、残りN-2K頂点の組み合わせを考えよう。

これはL,Rの選び方によらないので、事前にN-2K頂点を何個のパスに分割するケースが何通りあるか、前処理としてDPで求めておけばよい。

int N,K;
const ll mo=1000000007;

ll dp[5050][5050];
ll sum[5050];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	dp[0][0]=sum[0]=1;
	for(x=1;x<=5000;x++) {
		FOR(y,5010) {
			(dp[x][y]+=dp[x-1][y]*y)%=mo;
			(dp[x][y+1]+=dp[x-1][y])%=mo;
		}
		FOR(y,5010) (sum[x]+=dp[x][y])%=mo;
	}
	
	ll ret=0;
	for(int A=K;A<=N;A++) for(int B=K;A+B<=N+1;B++) {
		(ret+=dp[A][K]*dp[B][K]%mo*sum[N+1-A-B]%mo*comb(N+1,A+B))%=mo;
	}
	cout<<ret<<endl;
	
}

まとめ

まずネストした辺で考えるところに考えが至らない…。