東京工業大学プログラミングコンテスト2015 : J - 指さし

これは点数の割に簡単かも。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_j

問題

N人の人が互いに(自分以外の)誰かを１人指している。
誰からも刺されてない人はいない。
各人が指してる指をたどったとき、最長でK人たどって自分に戻る人がいた。

N,Kに対し、そのような指の指し方の組み合わせが何通りあるか求めよ。

解法

N人を2～K人のいくつかの組に分ける問題とみなすことができる。
さらにK人の組は最低1個なければならない。
またi人組ができたとき、その内部の指さし順は(i-1)!通りである。

このことから、dp[全体の人数][K人組の有無] := 状態を満たす組み合わせ総数　を状態としてDPしていけばよい。
全部でx人の組み合わせを作る場合、うち先頭の人が(i-1)人を選んでi人の組み合わせを作ると考えると、
dp[x][0] += dp[x-i][0] * C(x-1,i-1) * (i-1)! = dp[x-i][0]*P(x-1,i-1)
となる。あとはK人組の有無に応じてdpの2つ目の数字の0/1の添え字を考えればよい。
Pは事前に前処理していればO(1)で求まるので、このDPは全体でO(N^2)。

const int NUM_=4001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

int N,K;
ll dp[1010][2];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;
	
	cin>>N>>K;
	
	dp[0][0]=1;
	for(i=2;i<=N;i++) {
		for(x=2;x<=min(i,K);x++) {
			(dp[i][(x==K)] += dp[i-x][0] * fact[i-1] % mo * factr[i-x]) %= mo ;
			(dp[i][1]      += dp[i-x][1] * fact[i-1] % mo * factr[i-x]) %= mo ;
		}
	}
	cout<<dp[N][1]%mo<<endl;
	
}

まとめ

150ptなのでぼちぼち厳しいかと思ったけど、まだいけるね。
サクサク解けるのもたまには良い。