kmjp's blog

競技プログラミング参加記です

TopCoder SRM 700 Div1 Medium CrazyFunctions

SRM

これは無理だわ…。
https://community.topcoder.com/stat?c=problem_statement&pm=14266

問題

関数f(x)を、整数1～Nから整数1～Nに変換する関数とする。このようなf(x)はN^N通り考えられる。

G(f,w)はf^r(x)をw以上のr及びx=1～Nに適用して得られる値の集合とする。
Z(f)はすべてのwを取ったときのG(f,w)の要素数の最小値とする。
A(y)はZ(f)=yであるfの個数とする。
N,Kが与えられたとき、A(K)の値を求めよ。

解法

問題文が分かりにくいので、グラフで考える。
i→f(i)に有向グラフを張ったとする。
各頂点からある回数以上辺にそって移動した場合到達する頂点群の数がKとなるfの数を求めよ、となる。

こうなるのは、当然K個の頂点が閉路を成す(複数の閉路でも良い)場合である。
よって解は \displaystyle {}_N C_K * S(K) * T(N,K)となる。

最初のCombinationは閉路を成すK個の頂点の選びかたである。
S(K)は、各頂点かの出次数が1である有効グラフにおいて、K個の頂点が閉路を成すような辺の構成法である。
T(N,K)は、N個中K個の頂点が根付き木を無し、残り(N-K)頂点をそれらにつなぐつなぎかたである。これは既に閉路を成すK頂点に、残り(N-K)頂点を閉路が増えないようにつなぐつなぎ方と考えて良い。

S(K)は簡単でS(K)=K!である。
これは(K-1)頂点が閉路を成しているときにもう１点を加える場合、既存の(K-1)辺の間に挿入するか、自己辺を追加するかでS(K)=(K-1)*S(K-1)+S(K-1)=K*S(K-1)から計算できる。
また数学的にはfが全単射であればそのような閉路を成すので、そこからS(K)=K!と導いても良い。

問題はT(N,K)である。
O(N^3)位のDPなら簡単で、根付き木につながっている頂点に対し、子の頂点数が未確定な葉に対し頂点をつないで行くやり方を求めればよい。
すなわち \displaystyle T(N,K) = \sum_{i=0}^{N-K} T(N-i,K-1+i)*{}_{N-K} C_iで求められる。
ただ今回のN,Kの値域だとTLEする。

O(NK)位のDPでも解けるようだが、コードがよくわからなかったので別解を紹介。
以下のコメントが参考になった。
Topcoder Single Round Match 700 - Codeforces

閉路を構成するK個の頂点が1つの根頂点に縮約したとし、全頂点数がN-K+1であるグラフの全域木を考える。
根以外の(N-K)頂点のうち、i個が縮約した頂点につながっていたとする。
(実際は根がK個あるので、後でK^iを掛ける)

根頂点の次数がiで、全頂点数がN-K+1である全域木の数は、Prufer Sequenceを考えるとPrüfer Sequenceで根頂点を指す数値が(i-1)箇所あり、残りは根頂点以外を指すとと考えると {}_{N-K-1} C_{i-1} * (N-K)^{N-K-i}通りである。
よってまとめると \displaystyle T(N,K) = \sum_{i=1}^{N-K} {}_{N-K-1} C_{i-1} * (N-K)^{N-K-i}であり、この計算はO(N-K)で解ける。

また、実はこのT(N,K)はOEISにもあったらしい…。
A066324 - OEIS

ll mo=1000000007;
const int NUM_=5005;
ll fact[NUM_+1];
int C[NUM_+1][NUM_+1];
int P[NUM_+1][NUM_+1];

class CrazyFunctions {
	public:
	int count(int n, int k) {
		
		int i,j;
		fact[0]=1;
		FOR(i,NUM_) fact[i+1]=fact[i]*(i+1)%mo;
		FOR(i,NUM_) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
		FOR(i,NUM_) {
			P[i][0]=1;
			FOR(j,NUM_) P[i][j+1]=1LL*P[i][j]*i%mo;
		}
		
		ll ret = 0;
		if(n==k) ret = 1;
		else {
			for(i=1;i<=n-k;i++) ret += 1LL * P[k][i] * P[n-k][n-k-i] % mo * C[n-k-1][i-1] % mo;
		}
		return ret%mo * fact[k] %mo * C[n][k] %mo;
		
	}
}

まとめ

Prüfer Sequenceなんてこれまで１回しか見たことないし、こんなん思い浮かばないよ…。