P8106 [Cnoi2021] 数学练习

题目背景

「Cnoi2021」Cirno’s Easy Round II 热身赛开始了。

题目描述

为了让选手们重视文化课，Cirno 特意加入了一道 Kamishirasawa Keine 老师的数学练习：

求将一个集合 U={1,2,3,⋯ ,n}\texttt{U}=\{1,2,3,\cdots,n\}U={1,2,3,⋯,n} 划分成两个子集 $S,T$，使得 $|S|\notin S,|T|\notin T$ 的方案数。

由于选手都不会高精度，所以答案只需要对 $998244353$ 取模即可。

输入格式

一行一个整数 $n$。

输出格式

一行，一个整数，表示答案。

输入输出样例 #1

输入 #1

3

输出 #1

2

输入输出样例 #2

输入 #2

6

输出 #2

10

输入输出样例 #3

输入 #3

65535

输出 #3

459810767

说明/提示

样例解释

#1: 两种合法的划分方案为 {1,3},{2}\{1,3\},\{2\}{1,3},{2} 与 {2},{1,3}\{2\},\{1,3\}{2},{1,3} 。

数据范围

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$。

重收录自 XDUCPC 2021 网络赛 B。

C++实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e5;
int n;
int fac[maxn + 1];
int inv[maxn + 1];
int power(int base, int freq, int mod) {
	int tmp = base, ans = 1;
	while (freq) {
		if (freq & 1) ans = ans * tmp % mod;
		freq >>= 1;
		tmp = tmp * tmp % mod;
	}
	return ans;
}
void init() {
	fac[0] = 1;
	for (int i = 1; i <= maxn; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[maxn] = power(fac[maxn], mod - 2, mod);
	for (int i = maxn - 1; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) % mod; 
	} 
}
int C(int n, int m) {
	if (n < m) return 0;
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
	init();
	cin >> n;
	if (n == 1) {
		cout << 0 << endl;
		return 0;
	}
	n -= 2;
	if (n % 2 == 0) {
		cout << (power(2, n, mod) - C(n, n / 2) + mod) % mod; 
	} else {
		cout << power(2, n, mod); 
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容