Codeforces #177 Div1. B. Polo the Penguin and Houses

さてB。これは順調に解けた。
http://codeforces.com/contest/288/problem/B

問題

N個の家があり、それぞれの銘板P[i]には1～Nのいずれかの数字が書かれている。
ペンギンが今家xにいるとき、次はP[x]に歩いていく、という処理を繰り返す。

以下の条件を満たすP[i]の組み合わせ数を答えよ。

• 最初1～K番の家からスタートしたとき、１手以上歩いたのちいずれ1番にたどり着く
• (K+1)～N番の家からスタートしたとき、いつまでたっても1番にたどり着かない

解法

まず、(K+1)～N番が1番にたどり着かないためには、P[K+1]～P[N]がいずれも(K+1)～Nなら良いので、これらの組み合わせは(N-K)**(N-K)通り。
また、P[1]は1～Kのどこかにしておけばいずれ1番にたどりつくのでK通り。
問題はP[2]～P[K]の組み合わせ。

ここはメモ再帰で処理する。
すでに1番に戻れることがわかっている家の数Aと、残された家の数Lについて組み合わせ数F(C,L)を求める。
P[2]～P[K]の組み合わせ数はF(1,K-1)通りである。
このFは以下の様に表せる。Lのうちi個を選び、すでに1番に戻れることが確定しているA個のいずれかを選ぶ、というもの。残されたL-i個の家は、新規に1番に戻れることが確定したi個から同様に選択する。

int N,K;
ll MO=1000000007;

int toto[10];
int num=0;
int memo[10][10];
int C[10][10];

int dodo(int cand,int num) {
	ll res=0;
	int i,j;
	
	if(num==0) return 1;
	if(memo[cand][num]>=0) return memo[cand][num];
	
	for(i=1;i<=num;i++) {
		ll r=C[num][i];
		FOR(j,i) r*=cand;
		
		r = (r*dodo(j,num-j))%MO;
		res = (res+r)%MO;
	}
	return memo[cand][num]=(int)res;
	
}

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t;
	
	ZERO(C);
	C[0][0]=1;
	for(i=1;i<10;i++) C[i][0]=C[i][1]=1;
	for(i=1;i<10;i++) for(j=1;j<10;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
	
	N=GETi();
	K=GETi();
	
	MINUS(memo);
	
	ll res=K;
	FOR(i,N-K) res = (res*(N-K)) % MO;
	res = (res * dodo(1,K-1)) % MO;
	cout << res << endl;
	
	return;
}

まとめ

一見数の大きさにびっくりするが、K<=8という点を考えると割と簡単。