题目描述
saruka有一座大大的城堡！城堡里面有n个房间，每个房间上面都写着一个数字p[i]。有一天，saruka邀请他的小伙伴LYL和MagHSK来城堡里玩耍（为什么没有妹子），他们约定，如果某一个人当前站在i号房间里，那么下一步他就要去p[i]号房间，在下一步就要去p[p[i]]号房间。
为了增加趣味性，saruka决定重新书写一下每个房间的p[i]，以满足：
<1>如果从编号为1-k的某个房间走，按照规则走，必须能走回1号房间。特别的，如果从1号房间开始走，也要走回1号房间。（至少走一步，如果p[1] = 1，从1走到1也算合法）
<2>如果从编号大于k的房间开始，按照规则走，一定不能走到1号房间。
saruka想知道，一共有多少书写p[i]的方案可以满足要求？
输入输出格式
输入格式：
共一行两个数字n，k，含义如题。
输出格式：
一个数字，表示合法的方案数。答案对10 ^ 9 + 7取模。
输入输出样例
输入样例#1：
5 2
输出样例#1：
54
输入样例#2：
7 4
输出样例#2：
1728
说明
1 <= n <= 10 ^ 18
1 <= k <= min(8，n)
题解：
首先这道题我们可以发现，对于这道题来说k号房间时一个分界点，它前面的一定是走不到后面且一定能走回一号点，所以就会一定有点指向一号点，并且就会有k个点可以满足，然后这个点还会有(k-1)个点去指向它，所以对于1~k个点来说就会有k^(k-1)种方案，而对于(k+1~n)这些点来说，他们只能指向(k+1~n)中的这些点，所以就会有(n-k)^(n-k)种方案，然后根据乘法原理，那么总方案数为k^(k-1)*(n-k)^(n-k)
于是乎，我们就可以用快速幂去解决这个问题。
第一种：
LL ksm(LL a, LL b)
{
int ans = 1;
a = a % mod;
while (b > 0)
{
if (b % 2 == 1)
ans = (ans * a) % mod;
b /= 2;
a = (a * a) % mod;
cout << a << " a " << ans <<endl;
}
return ans;
}
第二种：
LL ksm(LL a, LL b)
{
LL ans = 1;
a %= mod;
while (b)
{
if (b & 0x1)
ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
其实第一种和第二种几乎一样，只不过第二种是依靠二进制来实现的，所以运算速度会快一点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
LL ksm(LL a, LL b)
{
LL ans = 1;
a %= mod;
while (b)
{
if (b & 0x1)
ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int main()
{
LL n, k;
cin >> n >> k;
LL ans = ((ksm(k, k-1)%mod) * (ksm(n-k, n-k)%mod))%mod;
cout << ans;
return 0;
}