Codeforces 1342 E Placing Rooks —— 第二类斯特林数

This way

题意：

现在有一个n*n的棋盘，n个棋子，你要放置这些棋子使得他们满足以下条件： 每个格子都能被某个棋子打到 共有k对棋子能够打到对方 如果一个格子所处的这一行或这一列有一个棋子，那么这个格子就能被打到。两个棋子处在同一行或同一列并且它们之间没有别的棋子，这两个棋子被视为可以能够打到对方。

题解：

这个就是第二类斯特林数的模板题，

第一类斯特林数：

你有n个不同棋子，要让他构成m个环，有多少种组成方法 环是有序的，你每次要么让一个棋子自成一格环，要么让它加入某个棋子的左边，于是 可以写出这样的方程：

dp[i][j]=dp[i-1][j-1]+dp[i-1][j-1]*i

第二类斯特林数：

你有n个不同的棋子，要将他们分成m个非空集合，有多少种组成方法 集合是无序的，它的方程式是这样的： $S(n,m)=\frac{1}{m!}{\sum }_{i=0}^m(-1{)}^i\ast C_m^i\ast (m-i{)}^n$ 那么这道题，首先要么每行都有一个棋子，要么每列都有一个棋子，行和列的考虑是相同的，所以最后*2即可。 由于有k对棋子可以打到对方，所以有n-k列含有1个或多个棋子，剩下的列一个棋子都没有。所以这里的情况数是$C_n^{n-k}$ 然后就是$S(n,n-k)$ 由于所有棋子的行是不一样的，所以n-k列是一个排列数：$(n-k)!$ 最后的答案就是$C_n^{n-k}\ast S(n,n-k)\ast (n-k)!$ $=>C_n^{n-k}\ast {\sum }_{i=0}^{n-k}(-1{)}^i\ast C_{n-k}^i\ast (n-k-i{)}^n$

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e5+5; const ll mod=998244353; ll fac[N],inv[N],p[N]; ll qpow(ll a,ll b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;} ll c(ll n,ll m){ if(m==0||m==n)return 1; if(m>n||m<0)return 0; return fac[n]*inv[m]%mod*inv[n-m]%mod; } int main() { int n,k; scanf("%d%d",&n,&k); fac[0]=p[0]=1; if(k>n-1) return 0*printf("0\n"); for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; inv[n]=qpow(fac[n],mod-2); for(ll i=n-1;i;i--) inv[i]=inv[i+1]*(i+1)%mod; ll ans=0,f=1; for(int i=0;i<=n-k;i++) ans=(ans+f*c(n-k,i)*qpow(n-k-i,n)%mod+mod)%mod,f*=-1; (ans*=c(n,n-k))%=mod; if(k!=0)ans=ans*2%mod; printf("%lld\n",ans); return 0; }