B 小 G 的城堡

文件名 输入文件 输出文件 时间限制 空间限制

castle.pas/c/cpp castle.in castle.out 1s 128MB

题目描述

小 G 家有一座城堡。城堡里面有 n 个房间，每个房间上都写着一个数字 p i 。小

G 拉着几个小伙伴在城堡里面玩耍，他们约定，如果某个人当前站在 i 房间里面，下

一步这个人就会去 p i 房间，再下一步这个人去 p p i 。

为了增加趣味性，小 G 想重新书写每个房间的 p i ，以满足：

• 如果从编号 1 到 k 中的某个房间开始，按照规则走，必须能够走到 1 号房间。

特别地，如果从 1 号房间开始走，也要能够走回 1 号房间（至少走一步，如果

p 1 = 1，从 1 走到 1 也算合法）。

• 如果从编号大于 k 的某个房间开始，按照规则走，一定不能走到 1 号房间。

小 G 想知道，有多少种书写 p i 的方案，可以满足要求。

输入格式

输入文件一行两个数字 n,k，含义如题。

输出格式

输出文件一个数字，表示合法的方案数。答案对 10 9 + 7 取模。

样例输入 1

5 2

样例输出 1

54

样例输入 2

7 4

4

样例输出 2

1728

数据范围

对于 40% 的数据，1 ≤ n ≤ 8

对于 70% 的数据，1 ≤ n ≤ 10 5

对于 100% 的数据，1 ≤ n ≤ 10 18 ,1 ≤ k ≤ min(8,n)。

思路：

　　先处理前K个有多少种情况，我打的表。

　　然后乘(n-k)^(n-k);

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int P=1e9+7;long long K[9]={ 0,1,2,9,64,625,7776,117649,2097152};long long fastlow(long long a,long long b){ long long ans=1;a=a%P; while(b) { if(b%2) ans=(ans*1LL*a)%P; b/=2; a=(1LL*a*a)%P; } return ans%P;}long long n,k;int main(){ freopen("castle.in","r",stdin); freopen("castle.ans","w",stdout); scanf("%lld%lld",&n,&k); long long ans=1; ans=fastlow(n-k,n-k); ans=(ans*1LL*K[k])%P; cout<