ARC146C Even XOR 做题记录

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

对于所有 SS 的非空子集 TST\in STT 均满足以下条件中的至少一个:

  • T|T| 是奇数;
  • TT 中元素的异或和非零;

998244353998244353 取模。

1n2×1051\le n\le 2\times 10^5

不难发现只要把每个元素都加上 2n2^n,条件就转化为 SS 的所有非空子集的异或和均不为 00

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

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

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

也就是说,答案为:

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

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

代码如下:

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