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)で解いている人がいますが…よくわかりません…これが現実的な解法だと思います。