马上noip了我在学点啥
问题
求集合并卷积,即(h_S=sum_{Lin S}sum_{Rin S}[Lcup R]f_L*g_R)
要求更严一点,求子集卷积,即(h_S=sum_{Lin S}sum_{Rin S}[Lcup R=S][Lcap R=varnothing]f_L*g_R=sum_{Lin S}f_L*g_{S-L})
Sol
先看集合并卷积
最暴力的做法就是(O(2^n))分别枚举(L,R),(O(4^n))的将答案加到(h)里去 我觉得不行
下面是个高妙做法:
- 定义(f)的莫比乌斯变换为(hat f),其中(hat {f_{S}}=sum_{Tin S}f_T)
- 我们对卷积式两边同时做莫比乌斯变换:(hat{h_S}=sum_{Lin S}sum_{Rin S}[Lcup Rin S]f_L*g_R)。
- 由于([Lcup Rin S]=[Lin S][Rin S]),所以(hat{h_S}=sum_{Lin S}sum_{Rin S}f_L*g_R)。
- 即(hat{h_S}=(sum_{Lin S}f_L)*(sum_{Rin S}g_R))。
于是问题就在如何快速求出(f)和(g)莫比乌斯变换。
这东西是个子集和,可以高维前缀和优化到(O(n imes 2^n))。
但是我们求出来的只是(hat{h_S}),我们还需要减去它的子集和,就需要再做一遍高维差分,复杂度同样是(O(n imes 2^n))。
void FMT(int *A, int o) {// o 为识别因子
for (int i = 1; i < ST; i <<= 1)//ST-1 表示全集
for (int j = 0; j < ST; j++)
if (i&j) (A[j] += A[j^i]*o) %= mod;
}
下面我们看子集卷积
它的条件比集合并卷积更苛刻,要求(L)和(R)的集合不能相交。
我们可以在卷积时多加一维,维护集合的大小,如(f_{i,S})表示集合中有(i)个元素,集合表示为(S)。显然,当(i)和(S)的真实元素个数相等时才是合法的。初始时,我们只把(f_{cnt|S|,S})的值赋成原来的(f_S),然后做一遍莫比乌斯变换,(h_{i,S}=sum_{j=0}^if_{j,S}*g_{i-j,S})。
还是上代码吧
for (int i = 0; i <= n; i++) FMT(g[i], 1);
for (int i = 0; i <= n; i++) FMT(f[i], 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++)
for (int k = 0; k < ST; k++)
(h[i][k] += 1ll*f[j][k]*g[i-j][k]%mod) %= mod;
FMT(h[i], -1);
for (int k = 0; k < ST; k++) if (cnt[k] != i) h[i][k] = 0;
if (i != n) FMT(h[i], 1);
}