「题单题解」集合幂级数入门
Coffee_zzz
·
·
算法·理论
ARC100E Or Plus Max
给定一个长度为 2^n 的序列 a_0,a_1,\dots,a_{2^n-1}。对于每个 1 \le k \le 2^n-1，求最大的 a_i+a_j，满足 i \lor j \le k。
:::info[题解]
考虑求出 $i \lor j \subseteq k$ 时的答案，这样做一个前缀 $\text{max}$ 即可得到题目让我们求的内容。
设 $f_S$ 表示所有满足 $a_i \subseteq S$ 的 $a_i$ 的最大值，$g_S$ 表示所有满足 $a_i \subseteq S$ 的 $a_i$ 次大值，做一个类高维前缀和即可处理出数组 $f$ 和数组 $g$，于是 $ans_k=\max(ans_{k-1},f_k+g_k)$。
时间复杂度 $\mathcal O(2^n n)$。
:::
:::success[代码]
```c++
const int N=1<<18;
int n,V,f[N],g[N],ans[N];
void solve(){
cin>>n,V=1<<n;
for(int i=0;i<V;i++) cin>>f[i];
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(f[i|k]<f[i]) g[i|k]=f[i|k],f[i|k]=f[i];
else if(g[i|k]<f[i]) g[i|k]=f[i];
if(g[i|k]<g[i]) g[i|k]=g[i];
}
}
for(int i=1;i<V;i++) ans[i]=max(ans[i-1],f[i]+g[i]),cout<<ans[i]<<endl;
}
```
:::
## [CF449D Jzzhu and Numbers](https://codeforces.com/problemset/problem/449/D)
给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，求有多少个非空子序列 $a_{i_1},a_{i_2},\dots,a_{i_k}$ 满足这些数的按位与为 $0$。答案对 $10^9+7$ 取模。
$2$ 秒，$1 \le n \le 10^6$，$0 \le a_i \le 10^6$。
:::info[题解]
直接计算按位与为 $0$ 的非空子序列的数量有点困难，因此考虑对于每一个 $S$，计算按位与是 $S$ 的超集的非空子序列的数量 $f_S$，再做一个高维差分得到按位与等于 $S$ 的非空子序列的数量 $g_S$，那么答案即为 $g_0$。
接下来考虑怎么计算 $f_{S}$。显然，对于所有 $a_i \supseteq S$，$a_i$ 可选可不选，但不能每个都不选；而对于所有 ${a_i \nsupseteq S}$，$a_i$ 一定不能选。于是可以记 $c_S$ 表示序列 $a$ 中满足 $a_i=S$ 的 $a_i$ 的数量，$d_S$ 表示序列 $a$ 中满足 $a_i \supseteq S$ 的 $a_i$ 的数量，对 $c_S$ 做一个高维后缀和得到 $d_S$，那么 $f_S$ 就等于 $2^{d_S}-1$，再做高维差分得到 $g_0$ 即可。
时间复杂度 $\mathcal O(n + V \log V)$。
:::
:::success[代码]
```c++
const int V=1<<20,N=V+5,mod=1e9+7;
int n,pw[N],c[N],f[N];
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
void And(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c) add(f[i],f[i^k]);
else add(f[i],mod-f[i^k]);
}
}
}
void solve(){
cin>>n;
for(int i=1,x;i<=n;i++) cin>>x,c[x]++;
And(V,c,1);
pw[0]=1;
for(int i=1;i<V;i++) pw[i]=pw[i-1]*2%mod;
for(int i=0;i<V;i++) f[i]=pw[c[i]]-1;
And(V,f,0);
cout<<f[0]<<endl;
}
```
:::
## [P3175 [HAOI2015] 按位或](https://www.luogu.com.cn/problem/P3175)
现有一个初值为 $0$ 的变量 $x$，每一秒会随机一个小于 $2^n$ 的非负整数 $y$ 并执行 $x \leftarrow x \lor y$，其中随机到 $i$ 的概率为 $p_i$，求 $x$ 变成 $2^n-1$ 的期望时间。
$1$ 秒，$1 \le n \le 20$，$0 \le p_i \le 1$，$\sum p_i=1$。
:::info[题解]
设 $k_i$ 表示第 $i$ 位变成 $1$ 的时间，$\max(S)$ 表示所有满足 $i \in S$ 的 $i$ 中 $k_i$ 的最大值，$\min(S)$ 表示所有满足 $i \in S$ 的 $i$ 中 $k_i$ 的最小值，那么 min-max 容斥可以得到：
$$
E(\max(U))=\sum_{S \subseteq U,S\ne \varnothing} (-1)^{|S|-1}E(\min(S))
$$
$E(\max(U))$ 即为答案，于是考虑怎么求 $E(\min(S))$。
设 $f_S$ 表示 $\sum\limits_{S \cup T \ne \varnothing} p_T$，那么相当于每秒有 $f_S$ 的概率满足条件，于是可以得到 $E(\min(S))=\dfrac{1}{f_S}$。
又因为 $f_S=\sum\limits_{S \cup T \ne \varnothing} p_T=1-\sum\limits_{S \cup T = \varnothing} p_T=1-\sum\limits_{T \subseteq (U\setminus S)} p_T$，所以对 $p$ 做一个高维前缀和即可得到 $f$。
时间复杂度 $\mathcal O(2^nn)$。
:::
:::success[代码]
```c++
const int S=(1<<20)+5,eps=1e-9;
int n,V,popcnt[S];
double p[S],f[S],ans;
void FMT(int V,double *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) f[i|k]+=f[i];
else f[i|k]-=f[i];
}
}
}
void solve(){
cin>>n,V=1<<n;
for(int i=0;i<V;i++) cin>>p[i];
FMT(V,p,1);
for(int i=0;i<V;i++) for(int j=1;j<V;j<<=1) if(i&j) popcnt[i]++;
for(int i=0;i<V;i++) f[i]=1-p[V-1-i];
for(int i=1;i<V;i++){
if(f[i]<=eps) return printf("INF"),void();
if(popcnt[i]&1) ans+=1.0/f[i];
else ans-=1.0/f[i];
}
printf("%.12lf",ans);
}
```
:::
## [ABC288G 3^N Minesweeper](https://atcoder.jp/contests/abc288/tasks/abc288_g)
给定一个长度为 $3^n$ 的序列 $A_0,A_1,\dots,A_{3^n-1}$。对于两个小于 $3^n$ 的非负整数 $x,y$，若 $x$ 和 $y$ 在三进制下的每一位的差的绝对值都不大于 $1$，则 $f(x,y)=1$，否则 $f(x,y)=0$。
现有一个长度为 $3^n$ 的 $01$ 序列 $B_0,B_1,\cdots,B_{3^n-1}$，满足 $A_i=\sum\limits_{j=0}^{3^n-1} f(i,j)B_j$，求序列 $B$。
$2$ 秒，$1 \le n \le 12$，保证有解。
:::info[题解]
当 $n=1$ 时，根据题意可以得到：
$$
\begin{cases}
a_0=b_0+b_1\\
a_1=b_0+b_1+b_2\\
a_2=b_1+b_2\\
\end{cases}
$$
解得：
$$
\begin{cases}
b_0=a_1-a_2\\
b_1=a_0+a_2-a_1\\
b_2=a_1-a_0\\
\end{cases}
$$
当 $n\gt 1$ 时，类似于 FWT：由于位运算在每一位上是独立的，所以我们对每一位都做一次这样的变换即可。
时间复杂度 $\mathcal O(3^n n)$。
:::
:::success[代码]
```c++
const int N=15,S=6e5+5;
int n,V,a[S],pw[N];
void solve(){
cin>>n,pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*3;
V=pw[n];
for(int i=0;i<V;i++) cin>>a[i];
for(int k=1;k<V;k*=3){
for(int i=0;i<V;i++){
if((i/k)%3) continue;
int x=a[i],y=a[i+k],z=a[i+k+k];
a[i]=y-z;
a[i+k]=x+z-y;
a[i+k+k]=y-x;
}
}
for(int i=0;i<V;i++) cout<<a[i]<<' ';
}
```
:::
## [ABC212H Nim Counting](https://atcoder.jp/contests/abc212/tasks/abc212_h)
给定两个整数 $n,k$ 和一个大小为 $k$ 的集合 $A=\{a_1,a_2,\dots,a_k\}$。对于所有 $\sum\limits_{i=1}^n k^i$ 种石子堆数 $m \in [1,n]$ 且每堆石子的数量 $s_i \in A$ 的 Nim 游戏，计算先手获胜的游戏数。答案对 $998244353$ 取模。
$2$ 秒，$1 \le n \le 2\times10^5$，$1 \le a_i,k \lt 2^{16}$，$a_i$ 两两不同。
:::info[题解]
根据 Nim 游戏的性质，我们可以知道，只有当选出的 $m$ 堆石子的数量的异或和不等于 $0$ 时先手才必胜。
设 $f_i$ 表示序列 $a$ 中满足 $a_j=i$ 的 $a_j$ 的数量，$ans_{i,j}$ 表示选了 $i$ 堆石子且石子数量的异或和为 $j$ 时的答案，那么有：
$$
ans_{i,j}=\sum_{s_1=0}^{V-1}\sum_{s_2=0}^{V-1}\cdots\sum_{s_i=0}^{V-1} [s_1\oplus s_2\oplus \cdots \oplus s_i=j] \prod_{k=1}^i f_{s_k}
$$
注意到这就是异或卷积的形式。设 $g=\text{IFWT}\left(\sum\limits_{k=1}^n \text{FWT}^k(f)\right)$，那么我们要求的相当于 $g_1\sim g_{V-1}$ 的和。
设 $F=\text{FWT}(f)$，根据 FWT 的线性性，我们可以对 $F$ 的每一位都执行 $F_i \leftarrow {F_i}^k$，这样就求出了 $\text{FWT}^k(f)$；
再次根据 FWT 的线性性，我们可以对 $F$ 的每一位都执行 $F_i \leftarrow \sum\limits_{k=1}^n{F_i}^k$，这样就求出了 $\sum\limits_{k=1}^n\text{FWT}^k(f)$，于是我们对其做一个 IFWT 即可求出答案。
其中 $\sum\limits_{k=1}^n{F_i}^k$ 可以用等比数列求和公式计算，注意特判 $F_i=1$ 的情况。
时间复杂度 $\mathcal O(n+V \log V)$。
:::
:::success[代码]
```c++
const int N=2e5+5,V=1<<16,mod=998244353;
int n,k,f[N];
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int ad(int a,int b){
a+=b;
if(a>=mod) a-=mod;
return a;
}
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
void Xor(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
int x=f[i],y=f[i^k];
f[i]=ad(x,y),f[i^k]=ad(x,mod-y);
}
}
for(int i=0;i<V;i++) f[i]=1ll*f[i]*c%mod;
}
void solve(){
cin>>n>>k;
for(int i=1,a;i<=k;i++) cin>>a,f[a]++;
Xor(V,f,1);
for(int i=0;i<V;i++){
if(f[i]==1) f[i]=n;
else f[i]=1ll*(ksm(f[i],n)-1)*ksm(f[i]-1,mod-2)%mod*f[i]%mod;
}
Xor(V,f,ksm(V,mod-2));
int sum=0;
for(int i=1;i<V;i++) add(sum,f[i]);
cout<<sum<<endl;
}
```
:::
## [CF662C Binary Table](https://codeforces.com/problemset/problem/662/C)
给定一个 $n$ 行 $m$ 列的表格，每个元素均为 $0$ 或 $1$。每次操作可以选择一行或一列，把 $0$ 和 $1$ 翻转，即把 $0$ 变为 $1$ 并把 $1$ 变为 $0$。求经过若干次操作后，表格中 $1$ 的数量的最小值。
$6$ 秒，$1 \le n \le 20$，$1 \le m \le 10^5$。
:::info[题解]
设第 $i$ 列的二进制数为 $T_i$，考虑枚举每一行是否进行操作，并贪心地决定每一列是否进行操作，则答案可以表示为：
$$
\min_{S=0}^{2^n-1} \sum_{i=1}^m \min(\text{popcount}(S \oplus T_i),n-\min(\text{popcount}(S \oplus T_i))
$$
这个形式不太好快速计算，因此考虑做一个变换。设 $f_S=\sum\limits_{i=1}^m[T_i=S]$，$g_S=\min(\text{popcount}(S),n-\text{popcount}(S))$，那么答案可以被表示为：
$$
\min_{S=0}^{2^n-1} \sum_{T'=0}^{2^n-1} f(T')g(S\oplus T')
$$
注意到这就是异或卷积的形式。对 $f$ 和 $g$ 做一个异或卷积，取得到的序列中每一项的最小值即可。
时间复杂度 $\mathcal O(2^nn+nm)$。
:::
:::success[代码]
```c++
const int N=22,K=(1<<20)+5,M=1e5+5;
int n,m,V;
ll f[K],g[K],mi=1e18;
string s[N];
int popcount(int x){
int res=0;
while(x){
if(x&1) res++;
x>>=1;
}
return res;
}
void Xor(int V,ll *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
ll x=f[i],y=f[i^k];
f[i]=x+y,f[i^k]=x-y;
}
}
for(int i=0;i<V;i++) f[i]=f[i]/c;
}
void solve(){
cin>>n>>m,V=1<<n;
for(int i=0;i<n;i++) cin>>s[i];
for(int j=0;j<m;j++){
int val=0;
for(int i=0;i<n;i++) if(s[i][j]=='1') val+=(1<<i);
f[val]++;
}
for(int i=0;i<V;i++) g[i]=min(popcount(i),n-popcount(i));
Xor(V,f,1),Xor(V,g,1);
for(int i=0;i<V;i++) f[i]=f[i]*g[i];
Xor(V,f,V);
for(int i=0;i<V;i++) mi=min(mi,f[i]);
cout<<mi<<endl;
}
```
:::
## [CF103202M United in Stormwind](https://codeforces.com/gym/103202/problem/M)
给定 $n$ 个长度为 $m$ 的 $01$ 串 $s_0,s_1,\dots,s_{n-1}$，每个 $01$ 串的下标从 $0$ 开始。求有多少个 $\{0,1,\dots,m-1\}$ 的非空子集 $S$ 满足，在只保留每个 $01$ 串中下标 $i\in S$ 的位置后，存在至少 $k$ 对不同的 $(x,y)$，使得 $0 \le x \lt y \lt n$ 且变化后的 $s_x \ne s_y$。
$2$ 秒，$1 \le n \le 2\times10^5$，$1 \le m \le 20$，$1 \le k \le \dfrac{n(n-1)}2$。
:::info[题解]
设 $c_w$ 表示值为 $w$ 的 $01$ 串的数量，$f_S$ 表示满足 $0 \le x \lt y \lt n$ 且 $s_x$ 和 $s_y$ **恰好**在下标 $i \in S$ 的位置不同的 $(x,y)$ 的数量；特殊地，为了方便，令 $f_S=0$。把 $w$ 和 $S$ 都看成一个二进制数，容易得到转移方程：
$$
f_i=\dfrac{1}{2}\sum_{j=0}^{2^m-1} c_jc_{i\oplus j}
$$
于是对 $c$ 做一个异或卷积即可计算出 $f$。
设 $g_S$ 表示在只保留每个 $01$ 串中下标 $i\in S$ 的位置后满足条件的 $(x,y)$ 的数量，那么每个 $f_T$ 会对所有满足 $S \cap T \ne \varnothing$ 的 $g_S$ 做出贡献，推一下式子可以得到：
$$
\begin{aligned}
g_S &= \sum_{S \cap T \ne \varnothing} f_T\\
&=\sum_{T \subseteq U} f_T-\sum_{S \cap T=\varnothing} f_T\\
&=\sum_{T \subseteq U} f_T-\sum_{T \subseteq (U\setminus S)} f_{T}
\end{aligned}
$$
计算一下 $f$ 的高维前缀和即可快速得到 $g_S$。答案即为 $\sum\limits_{S \subseteq U}[g_S \ge k]$。
:::
:::success[代码]
```c++
const int S=1<<20;
int n,m,V,ans;
ll k,c[S],f[S];
void Or(int V,ll *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) f[i|k]+=f[i];
else f[i|k]-=f[i];
}
}
}
void Xor(int V,ll *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
ll x=f[i],y=f[i|k];
f[i]=x+y,f[i|k]=x-y;
}
}
if(c!=1) for(int i=0;i<V;i++) f[i]/=c;
}
void solve(){
cin>>n>>m>>k,V=1<<m;
for(int i=1;i<=n;i++){
string s;
int res=0;
cin>>s;
for(int j=0,p=1;j<m;j++,p<<=1) if(s[j]=='B') res+=p;
c[res]++;
}
Xor(V,c,1);
for(int i=0;i<V;i++) f[i]=c[i]*c[i];
Xor(V,f,V*2),f[0]=0,Or(V,f,1);
for(int i=1;i<V;i++) if(f[V-1]-f[V-1-i]>=k) ans++;
cout<<ans<<endl;
}
```
:::
## [P3349 [ZJOI2016] 小星星](https://www.luogu.com.cn/problem/P3349)
给定一个包含 $n$ 个结点和 $m$ 条边的简单无向图 $G=(V,E_G)$ 和一棵包含 $n$ 个结点的树 $T=(V,E_T)$，求有多少个 $1\sim n$ 的排列 $p$ 满足：对于每个 $(i,j) \in E_T$，均有 $(p_i,p_j) \in E_G$。
$1$ 秒，$2 \le n \le 17$，$1 \le m \le \dfrac{n(n-1)}{2}$。
:::info[题解]
考虑在树上做一个 DP：设 $f_{u,i,s}$ 表示，考虑到结点 $u$，$p_u=i$ 且以 $u$ 为根的子树内使用了 $s$ 二进制下为 $1$ 的数的方案数。初始时 $f_{u,i,2^i}=1$，转移时枚举儿子结点 $v$，那么转移方程形如：
$$
f'_{u,i,p}=\sum_{(i,j) \in E_G}\sum_{s\lor t=p,s\land t=0} f_{u,i,s}\times f_{v,j,t}
$$
注意到，$s \land t=0$ 的限制实际上是没用的，因为只有 $\text{popcount}(s)$ 等于当前考虑的结点数量的状态 $s$ 才会贡献到答案里，是否要求 $s \land t=0$ 不会影响答案，于是我们可以直接把转移方程看作：
$$
f'_{u,i,p}=\sum_{(i,j) \in E_G}\sum_{s\lor t=p} f_{u,i,s}\times f_{v,j,t}
$$
这就是或卷积的形式。设 $F_{u,i}=\text{FMT}(f_{u,i})$，那么有：
$$
F'_{u,i,s}=\sum_{(i,j) \in E_G} F_{u,i,s}\times F_{v,j,s}
$$
直接转移后再把每个 $F_{root,i}$ IFMT 回去即可。
时间复杂度 $\mathcal O(2^nn^3)$。
:::
:::success[代码]
```c++
const int N=17,S=1<<17;
int n,m,V,e[N][N];
ll f[N][N][S],tmp[S],ans;
vector <int> ve[N];
void FWT(int V,ll *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) f[i|k]+=f[i];
else f[i|k]-=f[i];
}
}
}
void dfs(int u,int fa){
for(int i=0;i<n;i++) for(int k=0;k<V;k++) if(k&(1<<i)) f[u][i][k]=1;
for(auto v:ve[u]){
if(v==fa) continue;
dfs(v,u);
for(int i=0;i<n;i++){
for(int k=0;k<V;k++) tmp[k]=0;
for(int j=0;j<n;j++){
if(!e[i][j]) continue;
for(int k=0;k<V;k++) tmp[k]+=f[u][i][k]*f[v][j][k];
}
for(int k=0;k<V;k++) f[u][i][k]=tmp[k];
}
}
}
void solve(){
cin>>n>>m,V=1<<n;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,e[u-1][v-1]=1,e[v-1][u-1]=1;
for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u-1].pb(v-1),ve[v-1].pb(u-1);
dfs(0,0);
for(int i=0;i<n;i++) FWT(V,f[0][i],0),ans+=f[0][i][V-1];
cout<<ans;
}
```
:::
## [P6846 [CEOI 2019] Amusement Park](https://www.luogu.com.cn/problem/P6846)
给定一个包含 $n$ 个结点和 $m$ 条边的简单有向图 $G=(V,E)$，保证 $G$ 中不存在二元环。
对于 $E$ 的一个子集 $E'$，称 $E'$ 是 $E$ 的好子集，当且仅当翻转 $E'$ 中的边的方向后，$G$ 中不存在环。
求 $E$ 的所有好子集的大小之和。答案对 $998244353$ 取模。
$3$ 秒，$1 \le n \le 18$，$0 \le m \le \dfrac{n(n-1)}{2}$。
:::info[题解]
注意到，对于一种合法方案，把所有边均翻转后仍然合法，且两种方案的翻转边数之和为 $m$，所以我们可以考虑计算合法方案数 $c$，那么原问题的答案即为 $\dfrac{cm}{2}$。
设 $f_S$ 表示以 $S$ 为点集的导出子图的合法方案数。转移时考虑枚举 $S$ 的子集 $T$，钦定 $T$ 中的结点的入度均为 $0$，那么显然 $T$ 需要是独立集，这种情况会对 $f_S$ 造成 $f_{S\setminus T}$ 的贡献。
设 $c_S=1/0$ 表示 $S$ 是或不是独立集，容斥一下可以得到转移方程：
$$
f_S=\sum_{T \subseteq S,T \ne \varnothing} (-1)^{|T|-1}c_Tf_{S\setminus T}
$$
考虑使用半半在线卷积优化：注意到 $|S|=k$ 的所有 $f_S$ 只会从 $|T|\lt k$ 的 $f_T$ 中转移过来，因此可以按照 $|S|$ 从小到大进行子集卷积，每做完一层就对该层的 $f$ 做一遍 IFMT，保留 $|S|=k$ 的 $S$ 后再 FMT 回去即可。
时间复杂度 $\mathcal O(2^nn^2)$。
:::
:::success[代码]
```c++
const int N=18,S=1<<18,mod=998244353;
int n,m,V,c[S],f[N+1][S],g[N+1][S],popcnt[S];
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
void FMT(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) add(f[i|k],f[i]);
else add(f[i|k],mod-f[i]);
}
}
}
void solve(){
cin>>n>>m,V=1<<n,f[0][0]=1;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,c[(1<<(u-1))|(1<<(v-1))]++;
FMT(V,c,1),FMT(V,f[0],1);
for(int i=1;i<V;i++){
for(int j=1;j<V;j<<=1) if(i&j) popcnt[i]++;
if(c[i]) g[popcnt[i]][i]=0;
else if(popcnt[i]&1) g[popcnt[i]][i]=1;
else g[popcnt[i]][i]=mod-1;
}
for(int k=1;k<=n;k++) FMT(V,g[k],1);
for(int k=1;k<=n;k++){
for(int i=0;i<k;i++){
int j=k-i;
for(int x=0;x<V;x++) add(f[k][x],1ll*f[i][x]*g[j][x]%mod);
}
FMT(V,f[k],0);
for(int x=0;x<V;x++) if(popcnt[x]!=k) f[k][x]=0;
if(k<n) FMT(V,f[k],1);
}
cout<<1ll*f[n][V-1]*m%mod*((mod+1)/2)%mod;
}
```
:::
## [P4221 [WC2018] 州区划分](https://www.luogu.com.cn/problem/P4221)
给定一个包含 $n$ 个结点和 $m$ 条边的无向图，第 $i$ 个结点有点权 $w_i$。
现需要将这 $n$ 个结点划分成若干个有序的组，设 $V_i$ 为第 $i$ 组中的结点所组成的集合，那么需要满足 $V_i \ne \varnothing$ 且原图以 $V_i$ 为点集的导出子图不存在在欧拉回路。
定义第 $i$ 个组的满意度为第 $i$ 个组的权值和在前 $i$ 个组的权值和中所占比例的 $p$ 次幂。即：
$$
\left( \dfrac{\sum\limits_{u \in V_i} w_u}{\sum\limits_{j=1}^i\sum\limits_{u \in V_j} w_u} \right)^p
$$
定义一个划分方案的满意度为所有组的满意度的乘积，求所有合法的划分方案的满意度之和。答案对 $998244353$ 取模。
$10$ 秒，$1 \le n \le 21$，$0 \le m \le \dfrac{n(n-1)}{2}$，$1 \le w_i \le 100$，$0 \le p \le 2$。
:::info[题解]
首先考虑如何判断一个点集 $V$ 是否合法。设原图以 $V$ 为点集的导出子图为 $G$，若 $G$ 不连通则一定合法，否则若 $G$ 中的每个结点的度数均为偶数则合法，反之不合法。
设 $c_S=1/0$ 表示点集 $S$ 合法或不合法，$f_S$ 表示点集为 $S$ 的所有划分方案的满意度之和，$g_S$ 表示 $\left(\sum\limits_{i\in S}w_i \right)^p$，容易得到转移方程：
$$
f_S=\dfrac{1}{g_S}\sum_{T\subset S} f_T c_{S\setminus T}g_{S\setminus T}
$$
考虑使用半半在线卷积优化：注意到 $|S|=k$ 的所有 $f_S$ 只会从 $|T|\lt k$ 的 $f_T$ 中转移过来，因此可以按照 $|S|$ 从小到大进行子集卷积，每做完一层就对该层的 $f$ 做一遍 IFMT，保留 $|S|=k$ 的 $S$ 后乘上 $\dfrac 1{g_S}$ 再 FMT 回去即可。
时间复杂度 $\mathcal O(2^nn^2)$。
:::
:::success[代码]
```c++
const int N=22,M=300,S=1<<21,mod=998244353;
int n,m,p,V,w[N],f[N][S],g[N][S],ppc[S],c[S],inv[S];
bool vis[N];
vector <int> ve[N];
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
void dfs(int u){
vis[u]=1;
for(auto v:ve[u]){
if(vis[v]) continue;
dfs(v);
}
}
void FWT(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) add(f[i|k],f[i]);
else add(f[i|k],mod-f[i]);
}
}
}
void solve(){
cin>>n>>m>>p,V=1<<n;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v,u--,v--;
ve[u].pb(v),ve[v].pb(u);
}
for(int u=0;u<n;u++) cin>>w[u];
for(int i=0;i<V;i++) for(int u=0;u<n;u++) if(i&(1<<u)) ppc[i]++;
for(int i=0;i<V;i++){
for(int u=0;u<n;u++){
if(i&(1<<u)) vis[u]=0,add(g[ppc[i]][i],w[u]);
else vis[u]=1;
}
if(p==0) g[ppc[i]][i]=1;
else if(p==2) g[ppc[i]][i]=1ll*g[ppc[i]][i]*g[ppc[i]][i]%mod;
for(int u=0;u<n;u++) if(i&(1<<u)){dfs(u);break;}
inv[i]=ksm(g[ppc[i]][i],mod-2),c[i]=0;
for(int u=0;u<n;u++) if(!vis[u]){c[i]=1;break;}
if(c[i]) continue;
for(int u=0;u<n;u++){
if(!(i&(1<<u))) continue;
int cnt=0;
for(auto v:ve[u]) if(i&(1<<v)) cnt++;
if(cnt%2==1){c[i]=1;break;}
}
if(!c[i]) g[ppc[i]][i]=0;
}
f[0][0]=1;
FWT(V,f[0],1);
for(int k=0;k<=n;k++) FWT(V,g[k],1);
for(int k=1;k<=n;k++){
for(int i=0;i<k;i++) for(int x=0;x<V;x++) add(f[k][x],1ll*f[i][x]*g[k-i][x]%mod);
FWT(V,f[k],0);
for(int x=0;x<V;x++){
if(ppc[x]==k) f[k][x]=1ll*f[k][x]*inv[x]%mod;
else f[k][x]=0;
}
if(k<n) FWT(V,f[k],1);
}
cout<<f[n][V-1]<<endl;
}
```
:::
## [CF850E Random Elections](https://codeforces.com/problemset/problem/850/E)
给定一个长度为 $2^n$ 的 $01$ 序列 $f_0,f_1,\dots,f_{2^n-1}$，并随机 $n$ 个长度为 $3$ 的排列 $p_0,p_1,\dots,p_{n-1}$。
考虑三个初始为 $0$ 的整数 $a,b,c$，并对于每个小于 $n$ 的非负整数 $i$ 进行下面的操作：
- 若 $p_{i,1}>p_{i,2}$，则 $a \leftarrow a+2^i$。
- 若 $p_{i,2}>p_{i,3}$，则 $b \leftarrow b+2^i$。
- 若 $p_{i,3}>p_{i,1}$，则 $c \leftarrow c+2^i$。
求操作结束后不满足 $f_a=f_b=f_c$ 的概率与 $6^n$ 的乘积。答案对 $10^9+7$ 取模。
$2$ 秒，$1 \le n \le 20$，$f_i \in \{0,1\}$。
:::info[题解]
转化一下即可得到，我们需要求出所有随机方案中，不满足 $f_a=f_b=f_c$ 的方案数。
考虑排列实际上带来的限制是什么：不能同时满足 $p_{i,1}>p_{i,2}$ 和 $p_{i,2}>p_{i,3}$ 和 $p_{i,3}>p_{i,1}$，也不能同时满足 $p_{i,1}<p_{i,2}$ 和 $p_{i,2}<p_{i,3}$ 和 $p_{i,3}<p_{i,1}$；也就是说，对于每个二进制位，$a,b,c$ 不能全为 $0$ 或全为 $1$；所以，$a,b,c$ 需要满足 $a \lor b \lor c=2^n-1$ 且 $a \land b\land c=0$。
那么现在问题变成了，求有多少个 $0 \le a,b,c \lt 2^n$，满足 $a \lor b \lor c=2^n-1$ 和 $a \land b\land c=0$，并且不满足 $f_a=f_b=f_c$。
显然，$(f_a,f_b,f_c)$ 的值可以是 $(1,0,1),(1,0,0),(0,1,1),(0,1,0),(1,1,0),(0,0,1)$。由于 $a,b,c$ 是等价的，不妨钦定 $f_a=1$ 且 $f_b=0$，此时计算出的方案包含 $(f_a,f_b,f_c)=(1,0,0)$ 和 $(f_a,f_b,f_c)=(1,0,1)$ 的情况，再乘上 $3$ 即可得到包含所有情况的答案。
于是，现在相当于需要从所有满足 $f_x=1$ 的 $x$ 中选一个当 $a$，从所有满足 $f_y=0$ 的 $y$ 中选一个当 $b$，而 $c$ 只需要满足每一位上不是三个 $0$ 或三个 $1$ 即可。
仍然分别考虑每一位：如果 $a$ 和 $b$ 在这一位上的值相等，则 $c$ 在这一位上只有一种选择方案；而如果 $a$ 和 $b$ 在这一位上的值不同，则 $c$ 在这一位上有两种选择方案。于是可以得到，当 $a$ 和 $b$ 已经确定时，$c$ 的选择方案有 $2^{\text{popcount}(a \oplus b)}$ 种。
那么现在只需要对于每一个 $x \in [0,2^n)$ 求出，有多少对 $(a,b)$ 满足 $f_a=1$ 且 $f_b=0$ 且 $a\oplus b=x$。设 $p_i=[f_i=1]$，$q_i=[f_i=0]$，对 $p$ 和 $q$ 做一个异或卷积即可。记得给此时的答案乘上 $3$。
时间复杂度 $\mathcal O(2^nn)$。
:::
:::success[代码]
```c++
const int N=(1<<20)+5,mod=1e9+7;
int n,V,p[N],q[N],g[N],ans;
string s;
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return res;
}
int ad(int a,int b){
a+=b;
if(a>=mod) a-=mod;
return a;
}
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
int popcount(int x){
int res=0;
while(x){
if(x&1) res++;
x>>=1;
}
return res;
}
void Xor(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
int x=f[i],y=f[i^k];
f[i]=ad(x,y),f[i^k]=ad(x,mod-y);
}
}
for(int i=0;i<V;i++) f[i]=1ll*f[i]*c%mod;
}
void solve(){
cin>>n>>s,V=1<<n;
for(int i=0;i<V;i++) p[i]=(s[i]=='1'),q[i]=(s[i]=='0');
Xor(V,p,1),Xor(V,q,1);
for(int i=0;i<V;i++) g[i]=1ll*p[i]*q[i]%mod;
Xor(V,g,ksm(V,mod-2));
for(int i=0;i<V;i++) add(ans,1ll*g[i]*ksm(2,popcount(i))%mod);
cout<<3ll*ans%mod<<endl;
}
```
:::
## [ABC213G Connectivity 2](https://atcoder.jp/contests/abc213/tasks/abc213_g)
给定一个包含 $n$ 个结点和 $m$ 条边的简单无向图 $G=(V,E)$。对于每个结点 $k(2 \le k \le n)$，求有多少个 $E$ 的子集 $E'$ 满足 $G'=(V,E')$ 中结点 $1$ 与结点 $k$ 连通。答案对 $998244353$ 取模。
$3$ 秒，$2 \le n \le 17$，$0 \le m \le \dfrac{n(n-1)}{2}$。
:::info[题解]
对于图 $G=(V,E)$ 和集合 $S \subseteq V$，设 $f_S$ 等于 $G$ 的点集为 $S$ 的**连通子图**的个数，$g_S$ 等于 $G$ 的点集为 $S$ 的**子图**的个数，那么答案可以表示为：
$$
ans_k=\sum_{\{1,k\} \subseteq S \subseteq V} f_S \times g_{V\setminus S}
$$
接下来考虑怎么求 $f_S$ 和 $g_S$。
$g_S$ 是好求的，只需要计算一下 $E$ 中满足 $u \in S$ 且 $v \in S$ 的边 $(u,v)$ 的数量 $cnt$，那么答案即为 $2^{cnt}$。
$f_S$ 直接求比较困难，因此考虑正难则反，计算点集为 $S$ 的**不连通子图**的个数 $h_S$，那么 $f_S$ 就等于 $g_S-h_S$。
对于 $h_S$，因为我们只关心 $1 \in S$ 的集合 $S$ 的 $f_S$ 的值，所以我们可以将点集 $S$ 拆成**不连通的**两部分：
- 结点 $1$ 所在的连通块；
- 结点 $1$ 所在的连通块以外的部分。
对于 $1 \not\in S$ 的 $S$，不妨令 $f_S=0$，那么可以得到：
$$
\begin{aligned}
f_S &=g_S-h_S\\
&=g_S-\sum_{1 \in T \subset S}f_T \times g_{S \setminus T}\\
&=g_S-\sum_{T \subset S}f_T \times g_{S \setminus T}
\end{aligned}
$$
考虑使用半半在线卷积优化：注意到 $|S|=k$ 的所有 $f_S$ 只会从 $|T|\lt k$ 的 $f_T$ 中转移过来，因此可以按照 $|S|$ 从小到大进行子集卷积，每做完一层就对该层的 $f$ 做一遍 IFMT，保留 $1 \in S$ 且 $|S|=k$ 的 $S$，并将这样的 $S$ 对应的 $f_S$ 修改为 $g_S-f_S$，最后再 FMT 回去即可。
时间复杂度 $\mathcal O(2^nn^2)$。
:::
:::success[代码]
```c++
const int N=18,S=1<<17,M=150,mod=998244353;
int n,m,V,c[S],f[N][S],g[N][S],popcnt[S],pw[M];
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
int ad(int a,int b){
a+=b;
if(a>=mod) a-=mod;
return a;
}
void FMT(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) add(f[i|k],f[i]);
else add(f[i|k],mod-f[i]);
}
}
}
void solve(){
cin>>n>>m,V=1<<n,pw[0]=1;
for(int i=1;i<M;i++) pw[i]=pw[i-1]*2%mod;
for(int i=0;i<V;i++) for(int j=1;j<V;j<<=1) if(i&j) popcnt[i]++;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,c[(1<<(u-1))|(1<<(v-1))]++;
FMT(V,c,1);
for(int i=0;i<V;i++) g[popcnt[i]][i]=pw[c[i]];
for(int k=1;k<=n;k++) FMT(V,g[k],1);
for(int k=1;k<=n;k++){
for(int i=0;i<k;i++){
int j=k-i;
for(int x=0;x<V;x++) add(f[k][x],1ll*f[i][x]*g[j][x]%mod);
}
FMT(V,f[k],0);
for(int x=0;x<V;x++){
if((x&1)&&(popcnt[x]==k)) f[k][x]=ad(g[k][x],mod-f[k][x]);
else f[k][x]=0;
}
FMT(V,f[k],1);
}
for(int k=1;k<=n;k++) FMT(V,f[k],0),FMT(V,g[k],0);
for(int k=1;k<n;k++){
int ans=0;
for(int x=0;x<V;x++) if((x&1)&&(x&(1<<k))) add(ans,1ll*f[popcnt[x]][x]*g[popcnt[V-1-x]][V-1-x]%mod);
cout<<ans<<endl;
}
}
```
:::
## [P6570 [NOI Online #3 提高组] 优秀子序列](https://www.luogu.com.cn/problem/P6570)
给定一个长度为 $n$ 的序列 $A=\{a_1,\dots,a_n\}$。对于 $A$ 的一个子序列 $B=\{a_{b_1},\dots,a_{b_m}\}(0 \le m \le n,1 \le b_1 \lt \dots \lt b_m \le n)$：
- 称 $B$ 是 $A$ 的优秀子序列，当且仅当对于任意 $1 \le i \lt j \le m$，都满足 $a_{b_i}\land a_{b_j}=0$；
- 定义子序列 $B$ 的价值为 $\varphi\left(1+\sum\limits_{i=1}^m a_{b_i}\right)$，其中 $\varphi(x)$ 表示小于等于 $x$ 的正整数中与 $x$ 互质的数的个数。
求 $A$ 的所有优秀子序列的价值之和。答案对 $10^9+7$ 取模。
$2$ 秒，$1 \le n \le 10^6$，$0 \le a_i \le 2\times10^5$。
:::info[题解]
注意到优秀子序列的限制其实就是每个二进制位上最多出现一个 $1$，那么 $\varphi\left(1+\sum\limits_{i=1}^m a_{b_i}\right)$ 就可以转化为 $\varphi\left(1+\bigvee\limits_{i=1}^m a_{b_i}\right)$。
设 $f_s$ 表示按位或是 $s$ 的子序列的个数，$g_s$ 表示 $a$ 中 $a_i=s$ 的 $a_i$ 的数量，容易得到转移方程：
$$
f_s=\sum\limits_{\text{lowbit}(s) \subseteq t \subseteq s}f_{s-t}g_{t}
$$
其中要求 $\text{lowbit(s)} \subseteq t$ 是为了做到不重。
可以考虑按照 $\text{lowbit}(s)$ 从大到小转移，每次只用 $\text{lowbit}(t)>i$ 的 $t$ 做子集卷积，计算出 $\text{lowbit}(s)=i$ 的 $f_s$，那么总复杂度是 $\mathcal O\left(\sum\limits_{i=1}^{\log V} i^22^i\right)=\mathcal O(V \log^2 V)$。
注意 $g_0$ 要特殊处理一下：转移时不考虑 $g_0$，转移结束后再给每个 $f_s$ 乘上 $2^{g_0}$。线性筛求出 $\varphi(i)$，答案即为 $\sum\limits_{s=0}^{V-1} f_s \times\varphi(s+1) $。
时间复杂度 $\mathcal O(n+V \log^2 V)$。
:::
:::success[代码]
```c++
const int N=1e6+5,L=18,V=1<<18,mod=1e9+7;
int n,f[L+1][V],g[L+1][V],h[L+1][V],F[N],G[N],popcnt[V],lowbit[V],phi[V+1],pri[V+1],tot,ans,pw=1;
bool vis[V+1];
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
void init(){
phi[1]=1;
for(int i=2;i<=V;i++){
if(!vis[i]) pri[++tot]=i,phi[i]=i-1;
for(int j=1;i*pri[j]<=V&&j<=tot;j++){
int k=i*pri[j];
vis[k]=1,phi[k]=phi[i]*(pri[j]-1);
if(i%pri[j]==0){phi[k]=phi[i]*pri[j];break;}
}
}
}
void FMT(int V,int *f,int c){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
if(c==1) add(f[i|k],f[i]);
else add(f[i|k],mod-f[i]);
}
}
}
void solve(){
init(),lowbit[0]=1,F[0]=1;
for(int i=0;i<V;i++) for(int j=1;j<V;j<<=1) if(i&j) popcnt[i]++;
for(int i=1;i<V;i++) lowbit[i]=i&-i;
cin>>n;
for(int i=0,a;i<n;i++) cin>>a,G[a]++;
for(int p=L-1;p>=0;p--){
int B=1<<p,m=L-p,W=1<<m;
for(int k=0;k<=m;k++) memset(f[k],0,W*4),memset(g[k],0,W*4),memset(h[k],0,W*4);
for(int i=0;i<V;i+=B+B) f[popcnt[i]][i>>p]=F[i];
for(int i=B;i<V;i+=B+B) g[popcnt[i]][i>>p]=G[i];
for(int i=0;i<m;i++) FMT(W,f[i],1);
for(int j=1;j<=m;j++) FMT(W,g[j],1);
for(int k=1;k<=m;k++){
for(int i=0;i<k;i++){
int j=k-i;
for(int x=0;x<W;x++) add(h[k][x],1ll*f[i][x]*g[j][x]%mod);
}
FMT(W,h[k],0);
}
for(int x=1;x<W;x+=2) F[x<<p]=h[popcnt[x]][x];
}
for(int i=0;i<G[0];i++) pw=pw*2%mod;
for(int i=0;i<V;i++) add(ans,1ll*pw*F[i]%mod*phi[i+1]%mod);
cout<<ans<<endl;
}
```
:::
## [UOJ310 黎明前的巧克力](https://uoj.ac/problem/310)
给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，你需要选出 $\{1,2,\dots,n\}$ 的两个不交子集 $S_1,S_2$（$S_1$ 和 $S_2$ 可以为空集，但不能均为空集），满足：
$$
\bigoplus_{i \in S_1} a_i = \bigoplus_{i \in S_2} a_i
$$
求满足要求的方案数。答案对 $998244353$ 取模。
$1$ 秒，$1 \le n \le 10^6$，$0 \le a_i \le 10^6$。
:::info[题解]
先忽略 $S_1$ 和 $S_2$ 不能均为空集的条件，考虑枚举 $T=S_1 \cup S_2$，那么 $\bigoplus\limits_{i\in T} a_i$ 需要为 $0$，且每一个 $i \in T$ 可以任选被分到 $S_1$ 或 $S_2$ 中，于是题意可以转化为：定义一个集合 $S$ 的权值为 $2^{|S|}$，求所有满足 $\bigoplus\limits_{i\in T} a_i=0$ 的 $\{1,2,\dots,n\}$ 的子集 $T$ 的权值之和。
设 $f_i=2x^{a_i}+1$，那么我们相当于要对所有 $f_i$ 做一个异或卷积，求 $[x^0]\prod\limits_{i=1}^n f_i$。
接下来考虑怎么计算 $\prod\limits_{i=1}^n\text{FWT}(f_i)$。设 $F_i=\text{FWT}(f_i)$，$G= \prod\limits_{i=1}^n F_i$，$V=2^{20}$，由于 $f_i$ 只有两项的值非 $0$，因此考虑手动把 $\text{FWT}(f_i)$ 拆开：
$$
\begin{aligned}
F_{i,j}&=\sum_{k=0}^{V-1} f_{i,k} \times (-1)^{\text{popcount}(j \land k)} \\
&=f_{i,0}\times(-1)^0+f_{i,a_i}\times(-1)^{\text{popcount}(j \land a_i)}\\
&=1+2 \times (-1)^{\text{popcount}(j \land a_i)}
\end{aligned}
$$
于是我们发现，$F_i$ 的每一项只会是 $-1$ 或 $3$。设 $x_j=\sum\limits_{i=1}^n [F_{i,j}=-1]$，$y_j=\sum\limits_{i=1}^n [F_{i,j}=3]$，那么 $G_j$ 就等于 $(-1)^{x_j}\times3^{y_j}$。
接着考虑怎么求 $x_j$ 和 $y_j$。我们可以计算 $H=\sum\limits_{i=1}^n F_i$，这样就可以得到 $3y_j-x_j=H_j$；又因为 $x_j+y_j=n$，所以 $x_j=\dfrac{3n-H_j}{4}$，$y_j=\dfrac{n+H_j}{4}$。其中，根据 FWT 的线性性，$H$ 可以通过计算 $h_j=\sum\limits_{i=1}^n f_{i,j}$ 再计算 $\text{FWT}(h)$ 得到。
对 $G$ 做一个 IFWT 即可得到异或卷积的结果，取 $\text{IFWT}(G)$ 的第 $0$ 项即为答案。注意此时的答案包含了 $S_1$ 和 $S_2$ 均为空集的情况，需要给答案减去 $1$。
时间复杂度 $\mathcal O(n+V\log V)$。双倍经验：[CF1906K Deck-Building Game](https://codeforces.com/problemset/problem/1906/K)。
:::
:::success[代码]
```c++
const int V=1<<20,N=V+5,mod=998244353;
int n,pw1[N],pw3[N],inv,f[N],h[N];
int ad(int a,int b){
a+=b;
if(a>=mod) a-=mod;
return a;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
void FWT(int V,int *f){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
int x=f[i],y=f[i^k];
f[i]=x+y,f[i^k]=x-y;
}
}
}
void IFWT(int V,int *f){
for(int k=1;k<V;k<<=1){
for(int i=0;i<V;i++){
if(i&k) continue;
int x=f[i],y=f[i^k];
f[i]=ad(x,y),f[i^k]=ad(x,mod-y);
}
}
for(int i=0;i<V;i++) f[i]=1ll*f[i]*inv%mod;
}
void solve(){
cin>>n,f[0]=n;
for(int i=1,a;i<=n;i++) cin>>a,f[a]+=2;
FWT(V,f);
pw1[0]=pw3[0]=1,inv=ksm(V,mod-2);
for(int i=1;i<=n;i++) pw1[i]=-pw1[i-1],pw3[i]=3ll*pw3[i-1]%mod;
for(int i=0;i<V;i++){
int x=(3*n-f[i])/4,y=(n+f[i])/4;
h[i]=1ll*(mod+pw1[x])*pw3[y]%mod;
}
IFWT(V,h);
cout<<(h[0]+mod-1)%mod<<endl;
}
```
:::
## [CF1119H Triple](https://codeforces.com/problemset/problem/1119/H)
给定 $f_i=d_0x^{a_{i,0}}+d_1x^{a_{i,1}}+d_2x^{a_{i,2}}$，求所有 $f_i$ 的异或卷积 $g=\prod\limits_{i=1}^n f_i$。答案对 $998244353$ 取模。
$1.5$ 秒，$1 \le n \le 10^5$，$1 \le k \le 17$，$0 \le d_i \le 10^9$，$0 \le a_{i,j} \lt 2^k$。
:::info[题解]
不妨将三元组推广至更一般的情况：给出 $d_i(0 \le i \lt m)$ 和 $a_{i,j}(1 \le i \le n,0 \le j \lt m,0 \le a_{i,j} \lt 2^k)$，令集合幂级数 $f_i=\sum\limits_{i=0}^{m-1} d_ix^{a_{i,j}}$，求所有 $f_i$ 的异或卷积 $g=\prod\limits_{i=1}^n f_i$。
令 $F_i=\text{FWT}(f_i)$，$G=\text{FWT}(g)$，那么有 $G=\prod\limits_{i=1}^n F_i$。考虑对于每一位 $p$ 求出 $[x^p]\prod\limits_{i=1}^n F_i=\prod\limits_{i=1}^n [x^p] F_i$，这样即可求出 $G$，再做一个 IFWT 就可以得到 $g$ 了。
由于 $[x^p]F_i=\sum\limits_{j=0}^{m-1} (-1)^{\text{popcount}(p \land a_{i,j})} d_j$，$d_j$ 前的系数只有 $\pm 1$，因此 $[x^p]F_i$ 的取值只有 $2^m$ 种，于是考虑求出 $[x^p]\prod\limits_{i=1}^n F_i$ 中每种取值的出现次数，再快速幂得到 $G_p$。
接下来，我们对于每一位 $p$，考虑如何求出 $[x^p]\prod\limits_{i=1}^n F_i$ 中每种取值的出现次数。
设 $c_s(0 \le s \lt 2^m)$ 表示第 $p$ 位中 $\sum\limits_{j=0}^{m-1} (-1)^{[2^j \subseteq s]} d_j$ 的出现次数，那么有 $c_s=\sum\limits_{i=1}^n\prod\limits_{j=0}^{m-1} \left[ (-1)^{\text{popcount}(p \land a_{i,j})}=(-1)^{[2^j\subseteq s]} \right]$，不过这样计算的时间复杂度无法接受，我们需要找到 $2^m$ 个线性无关的方程来求解 $c$。这启发我们对于每一个 $T \subseteq \{0,1,\dots,m-1\}$，仅将 $z_{i,T}=\bigoplus\limits_{j \in T} a_{i,j}$ 代入集合幂级数。令集合幂级数 $h_T=\sum\limits_{i=1}^n x^{z_{i,T}}$，$H_T=\text{FWT}(h_T)$。
考虑 $c_s$ 对 $[x^p]H_T$ 的贡献。根据 FWT 的线性性可以得到，$[x^p]H_T=\sum\limits_{i=1}^n (-1)^{\text{popcount}(p\land z_{i,T})}$。又因为 $\text{popcount}(i \land (j \oplus k)) \equiv \text{popcount}(i \land j)+\text{popcount}(i \land k) \pmod 2$（这个性质可以拆位理解），所以 $\sum\limits_{i=1}^n(-1)^{\text{popcount}(p\land z_{i,T})}=\sum\limits_{i=1}^n\prod\limits_{j\in T} (-1)^{\text{popcount}(p \land a_{i,j})}$。
于是我们可以把 $T$ 看成一个二进制数 $t$，那么对于 $j \in [0,m)$，只有当 $2^j \subseteq s$ 且 $2^j \subseteq t$ 时，$c_s$ 会对 $[x^p] H_T$ 造成 $-1$ 倍的贡献，因此 $c_s$ 一共会对 $[x^p] H_T$ 造成 $(-1)^{\text{popcount}(s \land t)}$ 倍的贡献，得到：
$$
[x^p]H_T=\sum_{s=0}^{2^m-1} (-1)^{\text{popcount}(s \land t)}c_s
$$
容易发现这其实就是对 $c$ 做 FWT 后 $x^T$ 的系数。于是我们只需要对于每一个 $T$ 求出 $C_T=H_{T,p}$，做一个 IFWT 得到 $c$，快速幂计算出 $[x^p]G$，最后再 IFWT 得到 $g$ 即可。
时间复杂度 $\mathcal O(nm2^m+(m+k)2^{m+k})$。
:::
:::success[代码]
```c++
const int N=1e5+5,K=1<<17,P=3,M=1<<3,mod=998244353,inv=(mod+1)/2;
int n,m,k,kk,d[P],a[N][P],z[M][N],c[N],h[M][K],g[K],w[M];
int ad(int a,int b){
a+=b;
if(a>=mod) a-=mod;
return a;
}
void add(int &a,int b){
a+=b;
if(a>=mod) a-=mod;
}
int ksm(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
void FWT(int *f,int V,int c){
for(int i=1;i<V;i<<=1){
for(int j=0;j<V;j++){
if(j&i) continue;
int x=f[j],y=f[j|i];
f[j]=ad(x,y),f[j|i]=ad(x,mod-y);
}
}
if(c!=1) for(int i=0;i<V;i++) f[i]=1ll*f[i]*c%mod;
}
void solve(){
cin>>n>>kk,m=3,k=17;
for(int i=0;i<m;i++) cin>>d[i],d[i]%=mod;
for(int i=0;i<M;i++){
for(int j=0;j<m;j++){
if(i&(1<<j)) add(w[i],mod-d[j]);
else add(w[i],d[j]);
}
}
for(int i=1;i<=n;i++) for(int j=0;j<m;j++) cin>>a[i][j];
for(int t=0;t<M;t++){
for(int i=1;i<=n;i++) for(int j=0;j<m;j++) if(t&(1<<j)) z[t][i]^=a[i][j];
for(int i=1;i<=n;i++) h[t][z[t][i]]++;
FWT(h[t],K,1);
}
for(int p=0;p<K;p++){
for(int t=0;t<M;t++) c[t]=h[t][p];
FWT(c,M,ksm(inv,m));
g[p]=1;
for(int i=0;i<M;i++) g[p]=1ll*g[p]*ksm(w[i],c[i])%mod;
}
FWT(g,K,ksm(inv,k));
for(int i=0;i<(1<<kk);i++) cout<<g[i]<<' ';
}
```
:::