Codeforces #717 Div2 : E. Baby Ehab Plays with Permutations

遅れて参加したこともあり全完できず。
https://codeforces.com/contest/1516/problem/E

問題

N個の区別できる箱が順に並んでいる。
2個の箱を選んでswapすることをちょうどj回繰り返して達成できる箱の並びは何通りか、j=1～Kそれぞれについて求めよ。

解法

f(n) := その箱の並びの状態にするのに最低n回かかるような並び方
とすると、求める解はf(j)+f(j-2)+f(j-4)+…となる。
このf(n)を求めよう。

i番の箱が最終的にP(i)番の位置に移動すると考え、i→P[i]に辺を張る。
もし長さLの連結成分があると、そのような入れ替えは(L-1)回のswapがいる。
これを用いて、
dp(a,b) := 初期位置と異なる箱がちょうどa個で、swap回数が最小b回であるような箱の並び
を求めよう。f(n) = sum(dp(*,n))となる。
dp(a,b)には、長さLの連結成分を1個追加するとdp(a+L,b+L-1)に遷移するので、あとはその組み合わせを数えていこう。

int N,K;
const ll mo=1000000007;

ll dp[404][404];
ll fact[404];
ll ret[404];

ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=400;i++) fact[i]=fact[i-1]*i%mo;
	
	
	
	cin>>N>>K;
	dp[0][0]=1;
	for(int step=0;step<=K;step++) for(int num=0;num<=2*K;num++) if(dp[step][num]) {
		(ret[step]+=dp[step][num]*modpow(fact[num-step]))%=mo;
		for(x=2;num+x<=N&&step+(x-1)<=K;x++) {
			(dp[step+x-1][num+x]+=comb(N-num,x)*dp[step][num]%mo*fact[x-1])%=mo;
		}
	}
	
	for(i=1;i<=K;i++) {
		ll sum=0;
		for(j=i;j>=0;j-=2) sum+=ret[j];
		cout<<sum%mo<<" ";
	}
	
}

まとめ

Div2最終問にしてはシンプル。