「学习笔记」集合幂级数
本文是一篇学习笔记，具体的概念请参考2015年VFK的国家队论文《集合幂级数的性质及其快速算法》
集合并卷积 - 快速莫比乌斯变换
我们要求形如这样的一个卷积：
[h_S =sum_{L subseteq S}sum_{Rsubseteq S} [Lcup R=S] f_L g_R
]
回忆一下之前所学的莫比乌斯反演，本质上是把质因子看成多重集合，这里的集合并等价于莫比乌斯反演的两个数的 ( ext{lcm})，不妨直接对这个集合做莫比乌斯变换，定义：
[f'_S = sum_{Tsubseteq S} f_T
]
同理，也可以参考这个容斥得到：
[f_S = sum_{Tsubseteq S} (-1)^{|S|-|T|} f'_T
]
对这个卷积左右两边都反演一下可以得到：
[h'_S = sum_{L}sum_{R}[L cup R subseteq S]f_Lg_R \
h'_S = sum_{L}sum_{R}[L subseteq S][R subseteq S]f_Lg_R \
h'_S = sum_{L}[L subseteq S]f_Lsum_{R}[R subseteq S]g_R \
h'_S = f'_Sg'_S
]
然后只需要 (O(n2^n)) 简单递推出 (f') 就可以求解了：
集合交卷积
我们要求形如这样的一个卷积：
[h_S =sum_{L subseteq S}sum_{Rsubseteq S} [Lcap R=S] f_L g_R
]
类似关于倍数的莫比乌斯反演，将反演的式子重新定义一下就好了：
[f_S = sum_{Ssubseteq T} (-1)^{|T|-|S|} f'_T
]
集合对称差卷积 - 快速沃尔什变换
我们要求形如这样的一个卷积，其中 (igoplus) 表示异或：
[h_S =sum_{L subseteq S}sum_{Rsubseteq S} [Loplus R=S] f_L g_R
]
这里先引入一个在 VFK 《炫酷反演魔术》课件中的一个看上去没用的东西辅助推导：
[frac {1} {2^n} sum_{T subseteq 2^n} (-1)^{|S cap T|} = [S = emptyset]
]
正确性可以自己验证一下：
然后这里定义 (f) 的沃尔什变换 (f'):
[f'_S = sum_{T subseteq 2^n} f_T (-1)^{|S cap T|} \
]
考虑怎么求逆变换：
[f_S = sum_{Tsubseteq 2^n} f_T [S oplus T=emptyset] \
f_S = sum_{T subseteq 2^n} f_T frac {1} {2^n} sum_{A subseteq 2^n} (-1)^{|S oplus Tcap A|} \
f_S = frac {1} {2^n} sum_{T subseteq 2^n} f_T sum_{A subseteq 2^n} (-1)^{|S cap A|}(-1)^{|Tcap A|} \
f_S = frac {1} {2^n} sum_{A subseteq 2^n}(-1)^{|Scap A|}sum_{T subseteq 2^n} f_T (-1)^{|T cap A|} \
f_S = frac {1} {2^n} sum_{A subseteq 2^n}(-1)^{|Scap A|}f'_A \
]
然后对于原来的卷积形式进行一些变换：
[h_S = sum_{L subseteq2^n}sum_{R subseteq2^n} [Loplus Roplus S=emptyset]f_Lg_R\
h_S = sum_{L subseteq2^n}sum_{R subseteq2^n}
frac {1} {2^n} sum_{T subseteq 2^n} (-1)^{|Loplus Roplus S cap T|}f_Lg_R \
h_S = frac {1} {2^n}sum_{L subseteq2^n}sum_{R subseteq2^n}
sum_{T subseteq 2^n} (-1)^{|Lcap T|}(-1)^{|Rcap T|}(-1)^{|Scap T|}f_Lg_R \
h_S = frac {1} {2^n}sum_{T subseteq 2^n} (-1)^{|Scap T|} sum_{L subseteq2^n}(-1)^{|Lcap T|}f_Lsum_{R subseteq2^n}
(-1)^{|Rcap T|}g_R
]
根据之前推出的沃尔什变换：
[h_S = frac {1} {2^n}sum_{T subseteq 2^n} (-1)^{|Scap T|}f'_Sg'_S \
h'_S =f'_S g'_S
]
与上面类似的，接下来只需要 (O(n2^n)) 递推出 (f') 即可。
子集卷积
我们要求形如这样的一个卷积：
[h_S =sum_{T subseteq S} f_T g_{(S-T)}
]
直接变换不太好做，不如加上一维 (cnt) 表示集合中的元素个数，并转变一下卷积形式：
[h_S =sum_{L subseteq S}sum_{Rsubseteq S} [Lcup R=S][cnt_L+cnt_R=cnt_S] f_L g_R
]
对于 (cnt) 相同的 (f ,g) 放在一起做快速莫比乌斯变换，对于 (cnt) 相同的 (h) 枚举一个 (L) 的大小后直接点乘即可，复杂度 (O(n^22^n))
子集卷积在递推上的应用
可以当做上一块的一个例题来看 「WC2018」州区划分：
预处理出每一个集合划成一个州是否可行，计算出 (g_S) 当州可行时为 (sum_S^p) 否则为 (0)
设 (f_S) 表示当前选取集合为 (S) 时的满意度之和，不难得到递推式：
[f_S = sum_{T subseteq S} frac{f_T g_{(S-T)}}{sum_S^p}
]
提出一个 (sum_S^p) 可以得到：
[frac{f_S}{{sum_S^p}} = sum_{T subseteq S} f_T g_{(S-T)}
]
后面是一个熟悉的子集卷积的形式，观察到都是由 (cnt) 的 (f) 转移到 (cnt) 大的 (f) ，对 (g) 求莫比乌斯变换后直接分层点乘即可。
注意点乘完处理回去的时候由一些细节，子集卷积后只有 (cnt_S=) 当前枚举的大小的位置答案是正确的，要把不正确的位置清 (0) 不然会影响后面的递推值。
Code
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
#define int ll
const int N = 25, Len = 5000005, mod = 998244353;
vector<int> g[N];
int f[N][Len], h[N][Len], sum[Len], dig[Len], fa[N], w[N], n, m, p;
inline void up(int &x, int y){
x = (x + y >= mod ? x + y - mod : (x + y < 0 ? x + y + mod : x + y));
}
inline int ask(int x){ return x == fa[x] ? x : fa[x] = ask(fa[x]); }
inline int Pow(int a, int b){
int ans = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ans = ans * a % mod;
return ans;
}
inline int check(int s){
int tot = 0;
for(int i = 0; i < n; i++) fa[i] = i;
for(int i = 0; i < n; i++) if((1 << i) & s){
for(int j = 0; j < g[i].size(); j++)
if((1 << g[i][j]) & s){
int p = ask(i), q = ask(g[i][j]);
if(p != q) fa[p] = q;
}
}
for(int i = 0; i < n; i++)
tot += ((s >> i) & 1) & (fa[i] == i);
return tot > 1;
}
inline void FMT(int A[], int sgn){
for(int i = 0; i < n; i++)
for(int s = 0; s < (1 << n); s++)
if((1 << i) & s) up(A[s], A[s^(1<<i)] * sgn);
}
signed main(){
read(n), read(m), read(p);
for(int i = 1, x, y; i <= m; i++){
read(x), read(y), x--, y--;
g[x].push_back(y), g[y].push_back(x);
}
for(int i = 0; i < n; i++) read(w[i]);
for(int s = 1; s < (1 << n); s++){
int flag = 0;
for(int i = 0; i < n; i++) if((1 << i) & s){
int deg = 0;
for(int j = 0; j < g[i].size(); j++)
deg += (s >> g[i][j]) & 1;
if(deg & 1) flag = 1;
sum[s] += w[i], dig[s]++;
}
if((flag || check(s)) && dig[s] != 1)
h[dig[s]][s] = Pow(sum[s], p);
}
for(int i = 0; i <= n; i++) FMT(h[i], 1);
f[0][0] = 1, FMT(f[0], 1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++)
for(int s = 0; s < (1 << n); s++)
up(f[i][s], h[j][s] * f[i-j][s] % mod);
FMT(f[i], -1);
for(int s = 0; s < (1 << n); s++) if(dig[s] == i)
(f[i][s] *= Pow(Pow(sum[s], p), mod - 2)) %= mod;
else f[i][s] = 0;
if(i != n) FMT(f[i], 1);
}
cout << (f[n][(1<<n)-1] % mod + mod) % mod;
return 0;
}