ARC146C Even XOR 做题记录

给定 $n$，求满足以下条件的集合 $S\in\{0,1,2,\dots,2^n-1\}$ 的个数：

对于所有 $S$ 的非空子集 $T\in S$，$T$ 均满足以下条件中的至少一个：

• $|T|$ 是奇数；
• $T$ 中元素的异或和非零；

对 $998244353$ 取模。

$1\le n\le 2\times 10^5$。

不难发现只要把每个元素都加上 $2^n$，条件就转化为 $S$ 的所有非空子集的异或和均不为 $0$。

考虑一个一个元素加入，假设现在 $S$ 中有 $i$ 个元素，则这 $i$ 个元素任意组合出来的 $2^i$ 个元素一定两两不同，其中有 $2^{i-1}$ 个元素第 $n+1$ 位为 $1$，那么新插入的 $x$ 就有 $2^n-2^{i-1}$ 种方案。

注意第一个元素有 $2^n$ 种方案。

但是这样插入是有序的，集合是无序的，所以需要乘上 $\frac{1}{(|S|)!}$

也就是说，答案为：

$\sum\limits_{k=0}^{n+1} \frac{2^n\prod\limits_{i=1}^{k-1}(2^n-2^{i-1})}{k!}$

上界是 $n+1$ 是因为插入多于 $n$ 个元素后集合中必然能异或出 $0$（线性基满了），这个东西很容易快速维护。

代码如下：

// 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;
}