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,TS,TS,T，使得∣S∣∉S,∣T∣∉T|S|\notin S,|T|\notin T∣S∣∈/S,∣T∣∈/T的方案数。
由于选手都不会高精度，所以答案只需要对998244353998244353998244353取模即可。
输入格式
一行一个整数nnn。
输出格式
一行，一个整数，表示答案。
输入输出样例 #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%100\%100%的数据，保证1≤n≤1051 \le n \le 10^51≤n≤105。
重收录自 XDUCPC 2021 网络赛 B。
C++实现
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmod=998244353;constintmaxn=1e5;intn;intfac[maxn+1];intinv[maxn+1];intpower(intbase,intfreq,intmod){inttmp=base,ans=1;while(freq){if(freq&1)ans=ans*tmp%mod;freq>>=1;tmp=tmp*tmp%mod;}returnans;}voidinit(){fac[0]=1;for(inti=1;i<=maxn;i++){fac[i]=fac[i-1]*i%mod;}inv[maxn]=power(fac[maxn],mod-2,mod);for(inti=maxn-1;i>=0;i--){inv[i]=inv[i+1]*(i+1)%mod;}}intC(intn,intm){if(n<m)return0;returnfac[n]*inv[m]%mod*inv[n-m]%mod;}signedmain(){init();cin>>n;if(n==1){cout<<0<<endl;return0;}n-=2;if(n%2==0){cout<<(power(2,n,mod)-C(n,n/2)+mod)%mod;}else{cout<<power(2,n,mod);}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
