SRM700Med

https://community.topcoder.com/stat?c=problem_statement&pm=14266

完全に知っているかどうかの問題ですが…

問題文がややこしいが、{1,2,...,n}から{1,2,...,n}への関数fを無限回適用したものをgとして、g(1),g(2),...,g(n)がk個の値を取る時のfの個数を求めよという問題になる。グラフに言い換えるとn頂点n辺のグラフになり、連結成分をみると、dfs+単純ループとなっている。なので単純ループに含まれる頂点数がkになるものを数え上げれば良い。
k頂点で単純ループを作る方法をdp[k]とすると、答えはdp[k]*C(n,k)*T(n,k)となる。ここでCはコンビネーション、T(n,k)=k*n^(n-k-1)。
C(n,k)はn頂点のうちどれを単純ループに含めるか、T(n,k)はn頂点k連結成分の森の数である。詳しくは
https://en.wikipedia.org/wiki/Cayley%27s_formula
を参照。
dp[i]の遷移はdp[i+j]にdp[i]*C(k-i-1,j-1)*(j-1)!を足し合わせれば良い。係数は取られていない頂点のうち番号最小のものでj頂点のループを作る方法の数である。よってO(K^2)で解けた。

ll dp[5010];

struct CrazyFunctions {
	int n;
	int k;
	int count(int _n, int _k) {
		n = _n, k = _k;
		C_init(n);
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		rep(i, 0, k) {
			rep(j, 1, k + 1) {
				if(i + j > k) continue;
				ADD(dp[i + j], dp[i] * C(k - i - 1, j - 1) % mod * fac[j - 1] % mod);
			}
		}
		ll res = dp[k];
		if(n != k) {
			MUL(res, C(n, k) * k % mod * mod_pow(n, n - k - 1) % mod);
		}
		return res;
	}
};

なんかO(N+K)で解いている人がいますが…よくわかりません…これが現実的な解法だと思います。