自动搬运

查看原文

来自洛谷，原作者为

	zzw4257 于浩歌狂热之际中寒；于天上看见深渊。于一切眼中看见无所有；于无所希望中得救。

搬运于2025-08-24 21:41:56，当前版本为作者最后更新于2018-03-31 18:19:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果没有思路，首先来看一下这道题的数据范围

那么O(n),甚至$$O(sqrt(n))$$都是不行的 那么我们就要来思考接近O(1)的算法

我们来审一审题
每个房子i都有对应的pi，是这个房间的后续
也就很类似于链表的结构，每个房间都有指向的下一个房间
求有多少种pi的排列顺序使得从前k个房子出发后都能到达1号
而除去这k个房子之外的房子都不能到达1号
但其实我们举一个小例子就会发现：

如果有两个相通的房间，能么第三者最终只有能同时到达两者或不能到达两个房间一种取pi的结果

其实pi作为着i和pi的联系，1号房间能被到达也即px=1，又因为前k个房间（由题包含1号）都作为前续取了px或能到达px的后缀

又因为px包含1，也即px={1,2,3,4...k}每个元素都作为另外的k-1个元素的后缀

那么对这k个元素，每个元素都要作为另一个元素的前续，那么他们必定是相连的而且都最终指向1

因此不妨称前k各元素出现的现象为一个循环，它们都在这个循环里；

但又应除去这k个房子之外的房子都不能到达1号这个条件所以这个循环内又不能有除去这k个房子之外的房子

所以总体来看整个城堡就被分成两块

而两边各自的方案都是可以算出来的

一边是k个房间都能到达一

所以最后一步只有一个选择

前面的k-1个选择都随便

所以是$k^{k-1}$

另一边是n-k个随便走都不影响

所以是${(n-k)}^{n-k}$

答案就出来了是$k^{k-1}*{(n-k)}^{n-k}$

但是呢由于n太大所以要用快速幂

以此敬上