给定 ,求满足以下条件的集合 的个数:
对于所有 的非空子集 , 均满足以下条件中的至少一个:
- 是奇数;
- 中元素的异或和非零;
对 取模。
。
不难发现只要把每个元素都加上 ,条件就转化为 的所有非空子集的异或和均不为 。
考虑一个一个元素加入,假设现在 中有 个元素,则这 个元素任意组合出来的 个元素一定两两不同,其中有 个元素第 位为 ,那么新插入的 就有 种方案。
注意第一个元素有 种方案。
但是这样插入是有序的,集合是无序的,所以需要乘上
也就是说,答案为:
上界是 是因为插入多于 个元素后集合中必然能异或出 (线性基满了),这个东西很容易快速维护。
代码如下:
// Problem: [ARC146C] Even XOR
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc146_c
// Memory Limit: 1 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
using namespace std;
const int p=998244353,S=200005;
int n,pw2[S],prod[S];
inline int qpow(int x,int y)
{
int res=1;
for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
return res;
}
int main()
{
scanf("%d",&n);
pw2[0]=1;
for(int i=1;i<=n+1;i++) pw2[i]=1ll*pw2[i-1]*2%p;
prod[0]=pw2[n];
for(int i=1;i<=n;i++) prod[i]=1ll*prod[i-1]*(pw2[n]-pw2[i-1]+p)%p;
int ans=1; // k=0
for(int k=1,fra=1;k<=n+1;k++)
{
fra=1ll*fra*k%p;
ans=(ans+1ll*prod[k-1]*qpow(fra,p-2)%p)%p;
}
printf("%d\n",ans);
return 0;
}