打卡信奥刷题（3199）用C++实现信奥题 P8106 [Cnoi2021] 数学练习

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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容