Codeforces #198 Div1. C. Iahub and Permutations

またPermutationか。
http://codeforces.com/contest/341/problem/C

問題

1～Nのpermutationからなる数列Aがある。
ただし、一部の要素は未確定である(A[i]=-1で表現される)。

ここで、Aとしてあり得る数列のうち、不動点(A[i]=i)を持たないような組み合わせ数を答えよ。

解法

どっかで近い問題見たと思ったら、AtCoderだ。
C: 高橋君、24歳 - AtCoder Regular Contest #009 | AtCoder

以下の２通りのパラメータX,YでDPを行えばよい。

• A[i]は未確定で、数iはまだ他の要素で利用されていない、というような要素数Y
• A[i]は未確定で、数iは別の要素で利用済み、というような要素数X

DP[X][Y]をX,Yに対応する組み合わせ数とする。

• X==0なら、残りのY要素で不動点は作れないので組み合わせはD[0][Y]=Y!通り。
• X==1なら、数iが未使用であるようなA[i]には残りのY個の数字のいずれかを割り当てればよいのでD[1][Y]=Y*D[0][Y]=Y*Y!通り。
• X>=2なら、Xに含まれる要素A[i]には、残り(X-1)個から選ぶ場合とY個から選ぶ場合が考えられるので、それぞれX,Yの遷移を考えて足せばよい。

int N;
vector<int> A;
int used[2001];
ll mo=1000000007;
ll dpdp[4002][4002];

ll dodo(ll X,ll Y) {
	ll a;
	if(dpdp[X][Y]==-1) {
		if(X==0) {
			dpdp[X][Y] = 1;
			ll Y2=Y;
			while(Y2>0) {
				dpdp[X][Y] = (dpdp[X][Y]*Y2)%mo;
				Y2--;
			}
		}
		else if(X==1) {
			dpdp[X][Y] = Y;
			ll Y2=Y;
			while(Y2>0) {
				dpdp[X][Y] = (dpdp[X][Y]*Y2)%mo;
				Y2--;
			}
		}
		else {
			dpdp[X][Y] = ((X-1)*dodo(X-2,Y+1)) % mo;
			if(Y>0) dpdp[X][Y] = (dpdp[X][Y] + Y*dodo(X-1,Y)) % mo;
		}
	}
	return dpdp[X][Y];
}

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) {
		x=GETi();
		A.push_back(x);
		if(x>0) used[x]=1;
	}
	FOR(x,2*N+1) FOR(y,2*N+1) dpdp[x][y]=-1;
	x=y=0;
	FOR(i,N) {
		if(A[i]==-1) {
			if(used[i+1]) y++;
			else x++;
		}
	}
	
	_P("%lld\n",dodo(x,y));
	return;
}

まとめ

Div1 Cの割に簡単。