题意
有n种元素，则共有(2^n)个不同的集合。
求所有选择集合的方案，使得选择的集合的交集大小为4的倍数。
Solution
考虑(f(k))，表示交集大小至少为k的选择集合方案数。
容易得到(f(k) = C_{n}^{k} (2^{2^{n-k}}-1))
我们考虑构造一个容斥系数(alpha(k))，使得满足如下等式：
(ans = sum_{k=0}^{n} f(k) alpha(k))
我们考虑每一个方案的贡献，设这个方案中集合的并集大小是(x)，那么显然有它的贡献为([4|x])
我们考虑这个方案在哪里被计算过，显然是所有(k<=x)的(f(k))
于是其贡献亦可以被表示为(sum_{k=0}^x C_{x}^{k} alpha(k)) ，其中C的意思即为钦定这k个是被(f(k))统计到的k个。
于是有：([4 mid x] = sum_{k=0}^x C_{x}^{k} alpha(k))
根据二项式反演，(alpha(x) = sum_{k=0}^{x} (-1)^{x-k} C_{x}^{k} [4 mid k])
接下来引入单位根反演：
(forall k,有[n mid k]=frac{1}{n} sum_{i=0}^{n-1} omega_{n}^{ik})
证明：
显然，当(n mid k)时，(ik)为(n)的倍数，右边式子即为(frac{1}{n} imes n = 1)
而(n mid k)时，后面的式子是一个等比数列求和，可以发现分子始终为0。
那，把这个单位根反演暴力代入上式
[egin{aligned}
alpha(x) &= sum_{k=0}^{x} (-1)^{x-k} C_{x}^{k} frac{1}{4} sum_{i=0}^{3} omega_{4}^{ik}\
&= frac{1}{4} sum_{i=0}^{3} sum_{k=0}^{x} C_{x}^{k} (-1)^{x-k} (omega_{4}^{i})^{k}\
&= frac{1}{4} sum_{i=0}^{3} (-1+omega_{4}^{i})^x \
end{aligned}
]
然后就可以求了，注意要做到严格(O(n))。
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int div2=499122177;
const int div4=748683265;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int n,int k){
int ret=1;
while(k){
if(k&1)ret=mul(ret,n);
n=mul(n,n);
k>>=1;
}
return ret;
}
const int N=10000000;
int n;
int f[10000010];
int fac[10000010],ifac[10000010];
int pow2[10000010];
int w[4],now[4];
void pre(){
pow2[0]=2;
for(int i=1;i<=N;++i)pow2[i]=mul(pow2[i-1],pow2[i-1]);
fac[0]=1;
for(int i=1;i<=N;++i)fac[i]=mul(fac[i-1],i);
ifac[N]=qpow(fac[N],mod-2);
for(int i=N-1;i>=0;--i)ifac[i]=mul(ifac[i+1],i+1);
int wn=qpow(3,(mod-1)/4);
int ww=1;
for(int i=0;i<4;++i,ww=mul(ww,wn)){
w[i]=dec(ww,1);
}
}
int C(int n,int m){
return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main(){
scanf("%d",&n);
pre();
for(int i=0;i<=n;++i){
f[i]=mul(C(n,n-i),dec(pow2[n-i],1));
}
now[0]=now[1]=now[2]=now[3]=1;
int ans=1;
for(int i=0;i<=n;++i){
int res=0;
for(int j=0;j<4;++j){
res=add(res,now[j]);
now[j]=mul(now[j],w[j]);
}
ans=add(ans,mul(f[i],mul(res,div4)));
}
printf("%d
",ans);
}