[codeforces 1342E] Placing Rooks 容斥原理

Educational Codeforces Round 86 (Rated for Div. 2)  比赛人数15356

[codeforces 1342E]   Placing Rooks   容斥原理

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1342/problem/E

思路同https://www.cnblogs.com/axiomofchoice/p/12783795.html

首先有一个重要的结论，即每一行都一个车/每一列都有一个车，两者至少满足其一。

那么先假设车占据了任一列。经过简单操作发现，所有车占据的行数恰好等于 n−k，不相信的可以画个棋盘搞一下。

AC代码如下

#include <stdio.h>
#define mod 998244353
#define maxn 200010
#define LL long long
LL n,k;
LL fact[maxn],inv[maxn];//fact n!;inv 乘法逆元
LL quick_pow(LL a,LL b){//快速幂LL ret=1;while(b){if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}
void init(){LL i;scanf("%lld%lld",&n,&k);fact[0]=1;for(i=1;i<=n;i++)fact[i]=fact[i-1]*i%mod;//计算排列数inv[n]=quick_pow(fact[n],mod-2);for(i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;//计算排列数的乘法逆元
}
LL C(LL n,LL m){//计算组合数return fact[n]*inv[n-m]%mod*inv[m]%mod;
}
void solve(){LL ans=0,i;if(k==0){printf("%lld\n",fact[n]);return;}//特判if(k>n-1){printf("0\n");return;}//特判for(i=0;i<=n-k-1;i++){//i表示空的行数if(i%2) ans=(ans-quick_pow(n-k-i,n)*C(n-k,i)%mod)%mod;else ans=(ans+quick_pow(n-k-i,n)*C(n-k,i)%mod)%mod;}ans=ans*C(n,n-k)%mod;ans=ans*2%mod;//行，列情况相同。ans=(ans+mod)%mod;//防止出现负数printf("%lld\n",ans);
}
int main(){init();solve();return 0;
}