自动搬运

查看原文

来自洛谷，原作者为

	3a51_ 支持刻1海0喵！

搬运于2025-08-24 22:36:02，当前版本为作者最后更新于2022-02-05 08:55:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

首先，我们设两个子集元素个数分别为 $s1,t1$。由于 $s1 \notin S$，可以得知 $s1 \in T$。同理，$t1 \in S$。所以还剩 $n-2$ 个元素，可以随便排放，只要使得 $|S|=s1$ 即可。可以从 $n-2$ 里面挑出 $s1-1$ 个放入 $S$ 中，这样 $|S|=s1$ 了。因为 $s1+t1=n$，所以此时 $|T|=t1$。满足条件。不难看出这个方法数就是 $C_{n-2}^{s1-1}$。

我们现在就可以把 $s1$ 变成 $1$ 至 $n-1$，因为空集不满足要求。列出式子:

$$C_{n-2}^{n-1-1}+C_{n-2}^{n-2-1}+C_{n-2}^{n-3-1}+\cdots+C_{n-2}^{2-1}+C_{n-2}^{1-1} $$$$=C_{n-2}^{n-2}+C_{n-2}^{n-3}+C_{n-2}^{n-4}+\cdots+C_{n-2}^{2}+C_{n-2}^{1}+C_{n-2}^{0} $$

考虑这个式子的真实含义。其实就是 $n-2$ 个人，选 $0,1,\cdots,n-3,n-2$ 个人，有多少种方案。

所以就是选若干个。每一个人都可以选/不选，根据乘法原理，可以得到原式 $=2^{n-2}$。

难道这就结束了吗？那样例 $2$ 为什么答案不是 $2^{6-2}=2^4=16$ 呢？

观察一下，发现当 $n$ 为偶数时会有一种情况：$s1=t1$。此时 $s1 \notin S$ 且 $s1 \notin T$。很明显不符合要求。所以要把这种情况排除出去。对应的，当 $n$ 为偶数的时候，答案需要少 $C_{n-2}^{\frac{n-2}{2}}$，需要减掉。考虑用一个乘法逆元及快速幂解决组合数， $2^{n-2}$ 直接for循环算就行了。如果不懂乘法逆元的话，提供一个链接，自行阅读。因为篇幅问题，这里不做过多赘述。

code

#include<iostream>
#define int long long
using namespace std;
const int Mod=998244353;
int jc[100006];
void init()
{
	jc[0]=jc[1]=1;
	for(int i=1;i<=100005;i++)
		jc[i]=(jc[i-1]%Mod*i%Mod)%Mod; 
}//预处理阶乘
int qpow(int a,int b,int c)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=res*a%Mod;
		b>>=1;
		a=a*a%Mod;
	}
	return res%Mod;
}//快速幂
int C(int a,int b)
{
	return jc[a]%Mod*qpow(jc[b],Mod-2,Mod)%Mod*qpow(jc[a-b],Mod-2,Mod)%Mod;
}//计算组合数，详细见链接
signed main()
{
	int n;
	cin>>n;
    if(n==1)
    {
        cout<<0;
        return 0;
    }//特判，否则会WA on #4
	init();//预处理阶乘
	int ans=1;
	for(int i=1;i<=n-2;i++)
		ans=(ans*2)%Mod;//计算2的n-2次方
	if(n%2==0)//如果n为偶数
	{
		int m=n-2,j=C(m,m/2);//计算组合数
		ans-=j;//将答案减去组合数
		ans+=Mod;//因为减是模意义下的，可能出现负数如6>4但6%5<4%5。所以加一个Mod再取模。
	}
	cout<<ans%Mod;//输出
	return 0;
}