AtCoder ARC #112 : E - Cigar Box

苦手なタイプの問題だけど、解き切れてよかった。
https://atcoder.jp/contests/arc112/tasks/arc112_e

問題

数列(1...N)に対し、以下の処理をM回行う。

• 任意の1要素を選び、先頭か末尾に移動する

ここで数列Aが与えられる。
M回の処理後の数列がAとなるような処理順は何通りあるか。

解法

Aのうち、

• 処理によって先頭から埋まった部分P要素
• 最初から最後まで動かさなかった部分Q要素
• 処理によって末尾から埋まった部分R要素

がそれぞれ何個であるか総当たりしよう。
ただし真ん中の部分は、昇順でなければならない。
この手順はO(N^2)かかるので、個々のパターンの数え上げをO(1)で終えることを考える。

動かさない部分を除いたf(P,R)を、「P+R個の要素をM回の処理で詰める手順」とする。
要素を1つ減らすため、g(X)を「前か後ろかはともかく、X個の要素をM回の要素で詰める手順」とすると、
f(P+R) := g(P+R) * Comb(P+R,P)
となる。

あとはg(X)を求めよう。
処理前は、どの要素も「まだ動かす必要があり最終的な場所に固定されていない」という状態である。
各処理で行うのは、

• 固定されていない要素を固定するために先頭か末尾に動かす
• 固定されていない要素を先頭か末尾に動かす(まだ固定されないまま)

h(X,M) := 未固定の要素がX個あり、あとM手処理がある
とおくと、

• M=1のときは、最後の1個を固定するしかないので、h(1,1) = 1
• M＞1の時、h(X,M) = h(X-1,M-1) + 2*X*h(X,M-1)

としてg(X)=h(X,M)とすればよい。

int N,M;
int A[3030];
const ll mo=998244353;
int up[3030];
ll dp[3030][3030];
ll p2[3030],fact[3030];

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;
	
	
	p2[0]=1;
	fact[0]=1;
	FOR(i,3010) {
		p2[i+1]=p2[i]*2%mo;
		fact[i+1]=fact[i]*(i+1)%mo;
	}
	
	cin>>N>>M;
	
	dp[1][1]=1;
	for(i=1;i<M;i++) {
		for(j=1;j<=3000;j++) {
			// add
			(dp[i+1][j+1]+=dp[i][j])%=mo;
			// same
			(dp[i+1][j]+=dp[i][j]*(2*j))%=mo;
		}
	}
	
	FOR(i,N) cin>>A[i];
	ll ret=0;
	for(i=N-1;i>=0;i--) {
		if(A[i]<A[i+1]) up[i]=1+up[i+1];
		else up[i]=1;
		for(j=1;j<=up[i];j++) if(j<N) {
			(ret+=comb(N-j,i)*dp[M][N-j])%=mo;
		}
	}
	// all
	FOR(i,N+1) (ret+=comb(N,i)*dp[M][N])%=mo;
	
	cout<<ret<<endl;
}

まとめ

なんで問題名がシガーボックス？と思ったけど、ジャグリングのやつか。