题面

题解

答案就是\(S(n-k,k)\times {n-1\choose k-1}\)

其中\(S(n,m)\)表示左边\(n\)个点，右边\(m\)个点的完全二分图的生成树个数，它的值为\(n^{m-1}m^{n-1}\)，证明可以看

居然没想出来……

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;int n,m,k,P,res,inv[500005];inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int C(int n,int m){    inv[0]=inv[1]=1;fp(i,2,n-m)inv[i]=mul(P-P/i,inv[P%i]);    int res=1;    fp(i,1,n-m)res=mul(res,inv[i]);    fp(i,m+1,n)res=mul(res,i);    return res;}int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%d%d",&n,&k,&P),m=n-k;    res=mul(ksm(k,m-1),ksm(m,k-1));    res=mul(res,C(n-1,k-1));    printf("%d\n",res);    return 0;}