这篇文章为洛谷P8106-Cnoi2021-数学练习的题解

刚刚学完排列组合特来写一篇题解

1. 思路

首先题目要求我们将 11~nn 的数分为两个子集。
∣S∣∉S|S| \notin S 且 ∣T∣∉T|T| \notin T。
∣S∣|S| 表示的是 SS 集合中元素的个数。
由题目的特殊条件我们可以得到该条件的一个充要条件 ：
∣S∣∈T|S| \in T 且 ∣T∣∈S|T| \in S。

这样我们在 “ 安置 ” 好 ∣S∣|S| 和 ∣T∣|T| 后就可以用组合数公式轻松计算出答案了。
但是这边仍然有一个性质我们没有用到 ：
当 nn 为偶数时 ∣S∣≠∣T∣|S| \neq |T| 这是显然的，也是必要的。

2. 解法

枚举 1 ~ n-1 作为 S 集合的元素个数。
已有 $ |T| \in S$。
利用组合数公式挑选剩下 i−1i - 1 个数。
由于 nn 个数全部挑完 ， 所以剩下的数全部纳入 TT 集合。
我们只需要算 SS 集合满足题意的个数即可。
附上组合数公式 ：

  • Cmn=(n!)(n−m)!m!C_m^n=\frac{(n!)}{(n-m)!m!}

注意到除号且在模意义下 ， 所以我们需要求 逆元。
注意到此题 modmod 的特殊性 ， 所以我们可以使用 费马小定理 求解逆元。
不知道逆元建议先做做 这道题。
最后注意 特判 nn 为偶数 的情况就可以了。

3. Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
typedef long long ll;
ll mod=998244353;
ll n;
ll frac[maxn];
ll x,y;
ll inv(ll a,ll s,ll p){ // 费马小定理求逆元
	ll ans=1; 
	while(s){
		if(s&1) ans=ans*a%p;
		a=a*a%p;
		s>>=1;
	}
	return ans%p;
}
ll C(ll m,ll n){
	ll x=inv(frac[m]*frac[n-m]%mod,mod-2,mod);
    return frac[n]*x%mod;
}
int main(){
    scanf("%lld",&n);
    ll ans=0;
    frac[0]=1;
    for(ll i=1;i<=n;i++) frac[i]=frac[i-1]*i%mod; // 预处理阶乘
    ll mid=n/2;
    bool judge=false;
    if(n%2==0) judge=true;
   	for(ll i=1;i<=n-1;i++){
   		if(judge==true&&i==mid) continue; // 特判 n 为偶数
   		ans=(ans+C(i-1,n-2))%mod;
	} 
   	printf("%lld",ans);
    return 0;
}