Codeforces #175 Div2. E. Positions in Permutations

ようやく最後。ここだけ極端に回答者が少ないね。
自分も自力では解けずEditorialを見て回答。
http://codeforces.com/contest/285/problem/E

問題

整数配列の長さNと、数Kが与えられる。
i番目の配列の要素p[i]に対し、|p[i]-i|=1の時、その要素はGoodである。
Goodな要素がK個となる配列の組み合わせ数を答える。

解法

まず、Goodな要素がK以上となる数をDPで求める。
各要素iに対し、i+1およびi-1を使用したかしてないかを2bit値で覚えつつ、あとはGoodな要素数毎にDPする。

Goodになる場所をKを選ぶ組み合わせ数をG(K)とすると、それ以外の(N-K)個の要素の割り当ては(N-K)!になるので全体の組み合わせ数がG(K)*(N-K)!となる。
ただ、実際には(N-K)個の要素を適当に割り振ると、結果的に|p[i]-i|=1となる要素が増えてK個よりGood数が増える可能性がある。

ここで、Goodがi個な配列数をF(i)とすると、F(N)=G(N)である。
F(N-1)はG(N-1)*1!からGoodがN-1より大きいケースを引かなければならないが、考えてみるとこれはF(N)を引けばよいことがわかる。
同様にF(N-2)はG(N-2)*2!からF(N)とF(N-1)を引けばよい。
さらに繰り返してF(K)はF(K+1),...,F(N)の分を引くことで計算できる。
F(K)を求める際、F(i)を引く回数は回になる点に注意。

int N,K;
ll mo=1000000007;
ll F[1010][1010][4];
ll FL[1010];
ll addmod(ll& l,ll r){ return l=(((l+r)%mo)+mo)%mo;}

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		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;
	}
	return C_[P_][Q_];
}



void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	
	N=GETi();
	K=GETi();
	F[0][0][0]=1;
	
	FOR(i,N) {
		FOR(j,N) {
			// use i-1
			if(i>0) {
				addmod(F[i+1][j+1][0],F[i][j][0]);
				addmod(F[i+1][j+1][1],F[i][j][2]);
			}
			// use i+1
			if(i<N-1) {
				addmod(F[i+1][j+1][2],F[i][j][0]+F[i][j][1]);
				addmod(F[i+1][j+1][3],F[i][j][2]+F[i][j][3]);
			}
			// neither
			addmod(F[i+1][j][0],F[i][j][0]+F[i][j][1]);
			addmod(F[i+1][j][1],F[i][j][2]+F[i][j][3]);
		}
	}
	
	for(i=N;i>=0;i--) {
		FL[i]=(F[N][i][0]+F[N][i][1]+F[N][i][2]+F[N][i][3])%mo;
		FOR(j,N-i) FL[i]=(FL[i]*(j+1))%mo;
		for(j=i+1;j<=N;j++) addmod(FL[i],-FL[j]*comb(j,i));
	}
	
	_P("%d\n",FL[K]);
	
	return;
}

まとめ

前後の値の利用状況を2bit持ってDPする、まではできたけど、F(K)を求めるのにF(K+1)以降の値を利用する、ってのがすんなり思い浮かばなかった…。