Placing Rooks(2300/容斥/组合)

题目 官方&代码 题意：给定 n ∗ n n*n n∗n棋盘，放置 n n n个骑士，要求：1、每个空位置都要与至少一位骑士同一行或同一列。2、刚好有 k k k对骑士产生行或列的碰撞。一个骑士，可以通过走他所在行，或者所在列，走到另一个骑士，中间无其他骑士障碍，那么这2个骑士属于一对碰撞。 思路：由于每个位置都要给骑士访问到，那么这 n n n个骑士要刚好占据 n n n行，或者占据 n n n列，这2个情况等效，我们只需讨论其一，最后答案再 ∗ 2 *2 ∗2即可，但注意当 k = 0 k=0 k=0时不需 ∗ 2 *2 ∗2。 n n n个骑士占据了 n n n行，要产生 k k k对碰撞，画图看看，容易发现，要求刚好有 n − k n-k n−k个空列，即 n n n个骑士在 k k k列中。这是个排列组合问题。 从 n n n列中选取出 c = n − k c=n-k c=n−k列出来，对于这 c c c列，共有 c n c^n cn种选择，但要减去有一个空列的情况 ( c − 1 ) n ∗ C c 1 (c-1)^n*C_{c}^1 (c−1)n∗Cc1​，加上有2个空列的情况 ( c − 2 ) n ∗ C c 2 (c-2)^n*C_{c}^2 (c−2)n∗Cc2​…，容斥下去，答案为 ∑ i = 0 c ( − 1 ) i ∗ ( c − i ) n ∗ C c i \sum_{i=0}^c(-1)^i*(c-i)^n*C_c^i ∑i=0c​(−1)i∗(c−i)n∗Cci​ 代码源自官方题解

#include

using namespace std;

const int MOD = 998244353;
const int N = 200043;

int add(int x, int y)
{
	return (x + y) % MOD;
}

int sub(int x, int y)
{
	return add(x, MOD - y);
}

int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}

int inv(int x)
{
	return binpow(x, MOD - 2);
}

int fact[N];

int C(int n, int k)
{
	return mul(fact[n], inv(mul(fact[k], fact[n - k])));
}

int main()
{
	int n, k;
	cin >> n >> k;
	
	if(k > n - 1)
	{
		cout