题解 P2817 【宋荣子的城堡】

· · 题解

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

n<={10^{18} }

那么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太大所以要用快速幂

以此敬上