AtCoder ABC #267 (NECプログラミングコンテスト2022) : G - Increasing K Times

全完はしたけど、割と手間取ったな。
https://atcoder.jp/contests/abc267/tasks/abc267_g

問題

N要素の整数列Aが与えられる。
このAの並べ替え方N!通りのうち、A[i]＜A[i+1]となるiがちょうどK個となるものは何通りか。

解法

挿入DPで解く。
Aのうち値の小さい順に、最終的な数列に挿入していくことを考える。
ただし、同じ値は同時に挿入する。

f(n,k) := Aのうちnまでの値の並び順を決めたとき、A[i]＜A[i+1]となる箇所がk個であるような組み合わせ

とする。
今、A中にn以下の値がB個、n+1がC個あったとして、それらの挿入位置を考えよう。
f(n,k)の状態を考えると、Aは(B-k)個の単調増加列を連結したものであることがわかる。
ここにn+1をC個追加する場合、単調増加列の先頭の直前に値を1個挿入すると、A[i]＜A[i+1]となる箇所が1個増える。それ以外の箇所に挿入した場合は増えない。
これをもとに、何か所でA[i]＜A[i+1]となる箇所を増やすかを総当たりしよう。

増やす数をa個とすると、a個挿入する位置を決め、またC個中どのa個をどの順番でその位置に入れるかを掛けて、最後に残り(C-a)個の(n+1)をどこに挿入するかを重複組み合わせの要領で考えると以下のように遷移できる。
f(n+1,k+a) += f(n,k) * Binom(B-k,a) * Perm(C,a) * H(k+a+1, C-a) * (C-a)!

int N,K;
int A[5555];

ll from[5555],to[5555];
const ll mo=998244353;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;
	cin>>N>>K;
	map<int,int> M;
	FOR(i,N) {
		cin>>x;
		M[x]++;
	}
	int sum=0;
	from[0]=1;
	FORR2(a,v,M) {
		ZERO(to);
		FOR(i,sum+1) if(from[i]) {
			for(int add=0;add<=min(sum-i,v);add++) {
				ll pat=comb(sum-i,add)*comb(v,add)%mo*fact[add]%mo*hcomb(i+add+1,v-add)%mo*fact[v-add]%mo;
				(to[i+add]+=from[i]*pat)%=mo;
			}
		}
		
		swap(from,to);
		sum+=v;
	}
	cout<<from[K]<<endl;
	
}

まとめ

ちょっと手間取ったけど解けてよかったね。