FWT 学习笔记
类似 FFT 地，FWT 也有这样的代码实现：
inline int add(int x){return x>=mod?x-mod:x;}
inline int sub(int x){return x<0?x+mod:x;}
inline void fwt(int *f,int len,int flg){
for(int i=1;i相比于 FMT，FWT 有一半的常数并且可以执行异或操作。
uoj310. 黎明前的巧克力
题意：给定集合 \(S\)，计数 \(S1,S2,S3\) 互不相交，并为 \(S\)，且 \(\oplus S3=0\) 的方案数。
题解：显然有 \(dp\)：\(f_{i,j}=f_{i-1,j},f_{i,j}=2f_{i-1,j\oplus{a_i}}\)，令 \(F_{i,0}=1,F_{i,a_i}=2\)，则答案为 \(FWT(\prod F_i)\)
考察 FWT 的性质，首先 FWT 是线性变换，可以把 \(0\) 和 \(a_i\) 拆开算。
类似 FFT 地，FWT 相当于给每一维做 FFT，于是 \(FWT(F)(n)=\sum\limits_{k=0}^{2^l-1} F_k\prod\limits_{j=0}^l (-1)^{n_jk_j}=\sum\limits_{k=0}^{2^l-1} F_k(-1)^{n\&k}\)
于是显然 \(F_0=1\) 的 FWT 就是每一位都是 \(1\)，\(F_{a_i}=2\) 的 FWT 就是一堆 \(2\) 和 \(-2\)
于是我们只用知道最终有多少个 \(-1\) 和 \(3\) 就好了，显然我们知道和就能解出来，而和就是整体的 FWT
#include
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=998244353;
const int iv2=(mod+1)/2;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
inline int add(int x){return x>=mod?x-mod:x;}
inline int sub(int x){return x<0?x+mod:x;}
inline void fwt(int *f,int len,int flg){
for(int i=1;i>=1;
}return res;
}
int main(){
n=read();
for(int i=1,x;i<=n;i++)
x=read(),a[x]++;
fwt(a,len,1);
for(int i=0;i CF662C Binary Table
首先很容易想到 \(O(2^n)\) 枚举翻转行集合，然后 \(O(m)\) 判断 \(0/1\) 最小值。
令 \(cnt_i\) 表示数值个数，\(a_i\) 表示状态 \(i\) 的 \(0/1\) 最小值，则翻转集合为 \(S\) 的答案为 \(F_S=\sum cnt_i a_{i\oplus S}\)，显然的 FWT 形式。
#include
using namespace std;
#define inf 1e16
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
#define ll long long
const int N=1<<20;
int n,m,lim;
ll a[N+5],b[N+5];
inline void fwt(ll *f,int len,int flg){
for(int i=2;i<=len;i<<=1)
for(int j=0,p=i/2;j CF850E Random Elections
太着急看题解了，下次可以固定一个时间强制思考。
三人等价，不妨假设 \(A\) 赢了 \(B,C\)，将 \(AB,AC,BC\) 也用 \(0/1\) 表示，则有 \(AB,AC\) 为 \(00\) 或 \(11\) 时有一种方案，否则两种。
则我们将 \(F\) 跟自己卷一遍，然后每个位置乘上二的 \(0\) 个数次方加入答案即可。
#include
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int maxn=2e5+10;
const int mod=1e9+7;
const int iv2=(mod+1)/2;
inline int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;y>>=1;
}return res;
}
inline int add(int x){return x>=mod?x-mod:x;}
inline int sub(int x){return x<0?x+mod:x;}
inline void fwt(int *f,int len,int flg){
for(int i=2;i<=len;i<<=1)
for(int j=0,p=i/2;j WC2018 州区划分
首先可以得到一个简单的 \(3^n\) dp，轻松拿到 \(n\leqslant 15\) 的部分分。
发现瓶颈在于解决形如 \(f_i=\sum\limits_{j|k=i,j\&k=0} f_jg_k\)，直接上子集卷积即可。
#include
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=998244353;
const int iv2=(mod+1)/2;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
inline int add(int x){return x>=mod?x-mod:x;}
inline int sub(int x){return x<0?x+mod:x;}
inline void fwt(int *f,int len,int flg){
for(int i=2;i<=len;i<<=1)
for(int j=0,l=i/2;j>=1;
}return res;
}
inline int calc(int j,int i){
int v=1ll*w[j]*iw[i]%mod;
return ksm(v,p);
}
vectorG[N];
#define pb push_back
int vis[N],lg[1<>t&1)dfs(sta,t);
}
int main(){
freopen("P4221.in","r",stdin);
freopen("P4221.out","w",stdout);
n=read(),m=read(),p=read();
for(int i=1,u,v;i<=m;i++){
u=read()-1,v=read()-1;
lk[1<>1]+(i&1);
if(ppc[i]==1)con[i]=1,ok[i]=1;
else{
w[i]=(w[i&(i-1)]+w[i&(-i)])%mod;
lk[i]=lk[i&(i-1)]|lk[i&(-i)];
con[i]=1;memset(vis,0,sizeof(vis));
dfs(i,lg[i&(-i)]);
for(int j=0;j>j&1)con[i]&=vis[j];
ok[i]=con[i];
for(int j=0;j>j&1)&&(ppc[lk[1<