NC228153. 延误列车
描述
如果不知道那些遗失的话语就在口袋里握紧双手吧停止挣扎的呼吸延误的今天就睡个觉应付过去吧如果不知道那些遗失的话语就搭上各停列车启程吧
有一张 个点的完全图，现在删去其中一条包含
个点的简单链（没有交点）求它的生成树数量。
因为删除哪条链的答案都是相同的，所以你可以视为删除 ，
或者
。
求答案对 取模后的值。
输入描述
第一行输入两个正整数
。
输出描述
输出一行表示答案对取模后的值。
示例1
输入:
5 3
输出:
40
示例2
输入:
4 2
输出:
8
示例3
输入:
5 4
输出:
21
说明:
两棵生成树不同当且仅当存在至少一对点对C++ 解法, 执行用时: 4ms, 内存消耗: 412K, 提交时间: 2021-11-09 15:53:38
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,k;
int qpow(int a,int b)
{
if(b<0) return 0;
int res=1;
while(b)
{
if(b&1) res=1ll*res*a%mod;
b>>=1;
a=1ll*a*a%mod;
}
return res;
}
int main()
{
scanf("%d%d",&n,&k);
if(k==2) printf("%lld\n",1ll*(n-2)*qpow(n,n-3)%mod);
else if(k==3) printf("%lld\n",1ll*(n-1)*(n-3)%mod*qpow(n,n-4)%mod);
else printf("%lld\n",(1ll*(qpow(n-2,3)-2*n+4)%mod*qpow(n,n-5)%mod+mod)%mod);
return 0;
}