Link
Solution
一共只有 (n) 辆车,如果两两之间不攻击又要使所有空格子被攻击到,那么就是一个排列 (n!)。现在我们想使其中一对能互相攻击到,就需要将其中一辆车移到另一行或另一列,那么这辆车原来所在的行或列就会空出来,又要使每个空格子被攻击到,那么就要保证每一列或每一行都至少要有一辆车,所以计数的时候让每辆车对应一列或一行。
而且考虑一个很显然的性质,如果恰有 (k) 对车能相互攻击,当且仅当有 (k) 行没有车或者 (k) 列没有车。那么问题就转换为了有恰好 (k) 行或 (k) 列没有车的方案数。很显然,这两个问题是等价的,所以只考虑行的情况,答案就是其的两倍。注意:若 (k=0),则只能计算一次。而 (n) 辆车最多有 (n-1) 对能相互攻击,所以对于 (kgeq n) 的,方案为 (0).
剩下的就比较套路了,计数将 (n) 个元素划分到 (k) 个非空集合的方案数,容易发现这就是斯特林数。
#include<stdio.h>
#define N 200007
#define ll long long
const int Mod = 998244353 ;
ll fac[N],inv[N];
ll qpow(ll x,ll y){
ll ret=1,cnt=0;
while(y>=(1LL<<cnt)){
if(y&(1LL<<cnt)) ret=(ret*x)%Mod;
x=(x*x)%Mod,cnt++;
}
return ret;
}
ll C(ll x,ll y){return x<y? 0:fac[x]*inv[y]%Mod*inv[x-y]%Mod;}
ll n,K;
int main(){
//freopen("Data.in","r",stdin);
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%Mod;
inv[N-1]=qpow(fac[N-1],Mod-2);
for(int i=N-2;~i;i--) inv[i]=inv[i+1]*(i+1)%Mod;
scanf("%lld%lld",&n,&K);
if(K>=n) printf("0");
else{
ll ans=0;
for(int i=K,op=1;i<=n;i++,op=-op)
ans=(ans+op*C(i,K)*C(n,i)%Mod*qpow(n-i,n)%Mod+Mod)%Mod;
printf("%lld",!K? ans:ans*2%Mod);
}
}