前夕
为了抵御以尼古拉奥尔丁为首的上古龙族的入侵，地球的守护者 Yopilla 集齐了 (n) 种人类文明的本源力量 —— 世界之力。
Yopilla 打算使用若干种技能来对抗尼古拉奥尔丁的进攻。每种技能由若干种世界之力构成。换句话说，一共有 (2 ^ n) 种技能，Yopilla 要使用若干种技能来对抗尼古拉奥尔丁。
大战前夕，Yopilla 走在波士顿的街头，突然看见天空中飞过了 (4) 只白鸽，他便洞察了战胜尼古拉奥尔丁的秘密：只要他使用的技能中，都含有的世界之力的种类数恰好为 (4) 的倍数，他便可以打败敌人。
Yopilla 想知道，他有多少种使用技能的情况，能战胜敌人。请你替 Yopilla 回答这个问题，答案对 (998244353) 取模即可。
对于所有数据，(1 le n le {10} ^ 7)。
题解
http://jklover.hs-blog.cf/2020/04/13/Loj-6358-前夕/#more
考虑容斥，钦定交集中包含了(k)个元素（实际包含了大于等于(k)个）的总方案数为
[g(k)=inom n k (2^{2^{n-k}}-1)
]
因为容斥系数不明显，所以考虑构造出容斥系数(f)，使得
[ ext{ans} =sum_{i=0}^n f(k)g(k)
]
对于交集大小为(x)的某种方案，我们希望它被算([xmod 4=0])次，而按照( ext{ans}=sum f(k)g(k))计算时，它实际上被算了(sum_{i=0}^x inom x if(i))次。
于是可以得出([xmod 4=0]=sum_{i=0}^x inom x i f(i))。
利用二项式反演和单位根反演可以得到
[f(x)=sum_{i=0}^x (-1)^{x-i} inom x i [imod 4=0] \
=sum_{i=0}^x(-1)^{x-i}inom x i frac{1}{4}sum_{j=0}^3 (omega_{4}^i)^j \
=frac{1}{4} sum_{j=0}^3 sum_{i=0}^xinom x i(-1)^{x-i} (omega_{4}^j)^i \
=frac{1}{4} sum_{j=0}^3(omega_4^j-1)^x
]
注意选择一个技能都没有的集合和一个集合都不选择是不同的方案。
而上述分析只考虑了前者的贡献,最后答案还要加上(1)，表示一个集合都不选。
时间复杂度(O(n))。
CO int N=1e7+10;
int fac[N],ifac[N];
int f[N],g[N];
IN int C(int n,int m){
return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main(){
int n=read<int>();
fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
ifac[n]=fpow(fac[n],mod-2);
for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
for(int i=n,k=2;i>=0;--i,k=mul(k,k))
g[i]=mul(C(n,i),k-1);
int w=fpow(3,(mod-1)/4);
for(int j=0,k=1;j<4;++j,k=mul(k,w))
for(int i=0,pw=1;i<=n;++i,pw=mul(pw,k-1))
f[i]=add(f[i],pw);
int ans=0;
for(int i=0;i<=n;++i)
ans=add(ans,mul(f[i],g[i]));
ans=mul(ans,fpow(4,mod-2));
printf("%d
",ans+1);
return 0;
}