题目大意

$n$ 排两列，塞 $n$ 对情侣，求恰好 $k$ 对情侣没有被拆散的数量。对 $998244353$ 取模。

题解

注意到，答案表达式为

$$\binom{n}{k}\cdot n^{\underline{k}}\cdot 2^k\cdot f_{n-k} $$

其中 $f_i$ 是 $i$ 对情侣全被拆散的数量。有

$$f_i=4i(i-1)\left(f_{i-1}+2(i-1)f_{i-2}\right) $$

代码

const int N = 5e6 + 10, mod = 998244353;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

inline int add (int a, int b) { return a + b > mod? a + b - mod: a + b; }
inline int dec (int a, int b) { return a < b? a - b + mod: a - b; }
inline int mul (int a, int b) { return 1ll * a * b % mod; }

namespace Main {
	int n, k;
	int f[N];
	int fac[N], ifac[N], p2[N];

	int qpow (int a, int b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int binom(int n, int m) {
		if (m > n) return 0;
		return mul(fac[n], mul(ifac[m], ifac[n - m]));
	}

	int main () {
		fac[0] = p2[0] = 1;
		f[0] = 1, f[1] = 0;
		for (int i = 1; i <= N - 10; i++) {
			fac[i] = mul(fac[i - 1], i), p2[i] = mul(p2[i - 1], 2);
			if (i > 1) f[i] = add(mul(mul(mul(4, i), i - 1), f[i - 1]), 
					mul(mul(mul(mul(8, i), i - 1), i - 1), f[i - 2]));
		}
		ifac[N - 10] = qpow (fac[N - 10], mod - 2);
		for (int i = N - 10; i; --i) ifac[i - 1] = mul(ifac[i], i);

		for (int t = read(); t--; ) {
			n = read(), k = read();
			int ans = mul(binom(n, k), mul(p2[k], mul(fac[n], ifac[n - k])));
			ans = mul(ans, f[n - k]);
			printf ("%d\n", ans);
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}