C/C++教程

codeforces极简题解

本文主要是介绍codeforces极简题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CF1713F
利用lucas定理，\(b_S\)表示下标\(T\)与\(S\)无交的\(a_T\)的异或，由于部分\(b_S\)未知，不能直接iFWT。回顾容斥：\([S=\emptyset]=\sum_{T\subseteq S}(-1)^|T|\)，\([n=0]=\sum_{i=0}^{n}C(n,i)(-1)^i\)，\([n=1]=\sum_{d|n}\mu(d)\)，利用这种思想构造：令\(A=S\cap T\)，\([A=\emptyset]=\sum_{B\subseteq A} 1 \mod 2\)。得到由\(a\)得到\(b\)做法：先求超集和，再求子集和。那么用iFWT先求子集和的逆，再求超集和的逆即可。
以下的\(\sum\)都表示异或求和\(b_S=\sum_{A\subseteq S}\sum_{A\subseteq T}a_T=\sum_{T}a_T(\sum_{A\subseteq S\cap T} 1 \mod 2)=\sum_{S\cap T=\emptyset}a_T\)

这篇关于codeforces极简题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航