考虑排列 \(P_i\) 已经固定了的情况，那么连边 \(i\to P_i\) 形成有向图 \(G\)，最小连边数就是 \(N\) 减去弱连通块数。善良的出题人已经告诉你连边方案就是 \((N-1)^K\)，所以答案就是 \(N(N-1)^K\) 减去所有连边方案中弱连通块数量总和。于是只需要考虑所有连边方案中弱连通块数量总和即可。
注意到最后这张图一定是个内向基环树森林，所以某些 \(P_i\) 未确定时就应该是个内向基环树加若干内向树构成的森林（孤立点也算内向树）。考虑一个弱连通块 \(G'\subseteq G\)，按照其形态分类：
- \(G'\) 为内向基环树，则 \(G'\) 内的点的 \(P_i\) 均固定，且只有一个环，所以对一个连边方案的贡献为 \(1\)，算上外部连边方案，总贡献为 \((N-1)^K\)。
- \(G'\) 为内向树，则 \(G'\) 内存在唯一 \(P_i\) 不固定的点 \(i\)，就是内向树的根。这个连通块有两种选择：
- \(P_i\) 选择 \(G'\) 内的点，那么 \(P_i\) 有 \(|V_{G'}|-1\) 种选择方案（不能选自己），外部还剩 \((N-1)^{K-1}\) 种方案，那么贡献为 \((|V_{G'}|-1)(N-1)^{K-1}\)。
- \(P_i\) 选择 \(G'\) 外的点，那么 \(G'\) 就变成了某个大内向基环树的子图，而这个基环树除去环边是由若干个内向树组成的。这类贡献有关其它连通块大小，单独拉出来在下面讨论。
刚才的问题可以转化为单独考虑每个大环的贡献，大环是由从 \(G\) 中选出若干个形态为内向树的连通块，选出它们的根之后连接组成的。假设选择了 \(G_1,G_2,\cdots,G_m\) \(m\) 个连通块形成一个环，环上的树的排列方式有圆排列 \((m-1)!\) 种，每个根 \(i\) 的 \(P_i\) 可以在下一棵内向树的点中任意选择，选择方案有 \(\prod |V_{G_i}|\) 种（\(V_G\) 为构成子图 \(G\) 的点集），其余 \(P_i\) 未匹配的 \(i\) 有 \(K-m\) 个，选出这些 \(P_i\) 有 \((N-1)^{K-m}\) 种方案。
那么设组成基环树的内向树数量为 \(m(m\ge 2)\)，方案数就是：
\[(m-1)!(N-1)^{K-m}\sum\limits_{G_1,G_2,\cdots,G_m}\prod\limits_{i=1}^m|V_{G_i}| \]后面这个东西就是个背包，设 \(f(m)=[x^m]\prod\limits(|V_{G_i}|x+1)\)，可以 \(O(N^2)\) 背包 dp 求出来，那么 \(m\) 的总贡献就是：
\[(m-1)!(N-1)^{K-m}f(m) \]然后算上之前的贡献就做完了，复杂度 \(O(N^2)\)。瓶颈在于计算 \(f(m)\)，可以多项式优化。
标签：Urban,连通,NOMURA,连边,方案,Programming,贡献,基环树,内向 From： https://www.cnblogs.com/Ender32k/p/17803570.html