参考资料：论文集2015《集合幂级数的性质及其快速算法》吕凯风

从子集卷积开始

$f,g$ （当然，以集合为下标）的子集卷积为

h_S=\sum_{L\subseteq S}\sum_{R\subseteq S}[L\cap R=\varnothing][L\cup R=S]f_Lg_R

它是非常重要的集合卷积；事实上它可能是最重要的集合卷积。

$O(n^22^n)$ $f_{|L|,L}$ $g_{|R|,R}$ $h_{|L|+|R|,L\cup R}$ $h_{|S|,S}$ $L,R$ $|S|$ 大。

$(|L|,|R|)\rightarrow |L|+|R|$ 显然就是普通的序列卷积，这提示我们定义如下的

集合占位幂级数

$\sigma$ $f$ 集合占位幂级数 $[x^S]\sigma$ $i<|S|$ $[z^ix^S]\sigma=0$ $[z^{|S|}x^S]\sigma=f_S$ 。

我也知道乱改论文里的符号不太好，但是在右下角标里写太多东西就是让我很难受……

$i>|S|$ $[z^ix^S]\sigma$ 我们完全不关心。大概这就是占位罢（。显然集合占位幂级数的如下定义的卷积

\boxed{[z^rx^S]\delta=\sum_{L\cup R=S,p+q=r}[z^px^L]\sigma[z^qx^R]\tau}

就是子集卷积。

实现方法就是之前提到的经典算法，不再赘述。

接下来我们简称集合占位幂级数为集合幂级数。

集合幂级数求逆

$z^{\varnothing}$ 。

$\sigma,\tau$ or_FWT 后把对应位置的集合幂级数相乘。从而有

[x^S]\text{FWT}(\sigma)\cdot[x^S]\text{FWT}(\sigma^{-1})=[x^S]\text{FWT}(x^{\varnothing})=1

$[x^S]\text{FWT}(\sigma)$ $\text{FWT}^{-1}$ $\sigma$ 有逆当且仅当

[z^0x^{\varnothing}]\sigma\neq 0

$\text{FWT}$ $O(n^22^n)$ $O(n^2)$ 求逆。

集合幂级数 Exp 和 Ln

考虑如下定义的 Exp：

\text{Exp}(\sigma)=\sum_{i}\dfrac{\sigma^i}{i!}

$\text{FWT}$ $[x^S]$ 有线性，我们可以得到

\begin{aligned} \left[x^S\right] \text{FWT Exp}(\sigma)&=\sum_{i}\dfrac{\Big([x^S]\text{FWT}(\sigma)\Big)^i}{i!}\end{aligned}

$\text{FWT}\circ\text{Exp}=\text{Exp}\circ\text{FWT}$ 。

$\text{FWT}$ $\text{Exp}$ $\text{FWT}^{-1}$ 即可。

$\text{Ln}$ 完全类似。

$O(n^2)$ 算法。

参考代码

虽然集合占位幂级数一看就让人很有封装的欲望，但是不仅没有封装的必要而且一旦封装还会让你的常数起飞……


x
#include<bits/stdc++.h>
#include<typeinfo>
using namespace std;
const int p = 998244353, maxN = 18, mL = 1 << maxN, mN = maxN + 1, inv2 = (p + 1) >> 1;
struct Z {int x; Z(int x0 = 0) : x(x0) {}};
int inline check(int x) { return x >= p ? x - p : x; }
Z operator +(const Z a, const Z b) { return check(a.x + b.x); }
Z& operator +=(Z &a, const Z b) { return a = a + b; }
Z operator -(const Z a, const Z b) { return check(a.x - b.x + p); }
Z operator -(const Z a) {return check(p - a.x);}
Z& operator -=(Z &a, const Z b) { return a = a - b; }
Z operator *(const Z a, const Z b) { return 1LL * a.x * b.x % p; }
Z& operator *=(Z &a, const Z b) { return a = a * b; }
Z qpow(Z a, int k) {
    Z ans = 1;
    for (; k; a *= a, k >>= 1) if(k & 1) ans *= a;
    return ans;
}
Z fac[mL], ifac[mL], inv[mL];
int ppc[mL], ctz[mL];
void init() {
    inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i < mL; i++)
        fac[i] = fac[i - 1] * i,
        inv[i] = -inv[p % i] * (p / i),
        ifac[i] = ifac[i - 1] * inv[i];
    for (int i = 1; i < mL; i++) {
        ppc[i] = ppc[i >> 1] + (i & 1);
        ctz[i] = (i & 1) ? 0 : (ctz[i >> 1] + 1);
    }
}
namespace Poly {
#define forj for(Z *jf = f + 1, *jg = i - 1; jg >= g; jf++, jg--)
void Mul(Z f[], Z g[], int n) {
    for (Z *i = g + n; i >= g; i--) {
        *i *= f[0];
        forj *i += *jf * *jg;
    }
}
void Inv(Z f[], Z g[], int n) {
    memset(g, 0, (n + 1) * sizeof(Z));
    g[0] = qpow(f[0], p - 2);
    for (Z *i = g + 1; i <= g + n; i++) {
        forj *i -= *jf * *jg;
        *i *= g[0];
    }
}
Z tg[mN]; //tg = 0.5ttgg = 0.5瑇!
void copy(Z f[], Z g[], int n) { for (Z *i0 = f, *i1 = g; i0 <= f + n; i0++, i1++) *i1 = *i0; }
void Inv(Z f[], int n) { copy(f, tg, n); Inv(tg, f, n); }
void Ln(Z f[], Z g[], int n) {
    memset(g, 0, (n + 1) * sizeof(Z));
    g[0] = 0;
    for (Z *i = g + 1; i <= g + n; i++) {
        *i = (i - g) * f[i - g];
        forj *i -= (jg - g) * *jf * *jg;
        *i *= inv[i - g];
    }
}
void Ln(Z f[], int n) { copy(f, tg, n); Ln(tg, f, n); }
void Exp(Z f[], Z g[], int n) {
    memset(g, 0, (n + 1) * sizeof(Z));
    g[0] = 1;
    for (Z *i = g + 1; i <= g + n; i++) {
        forj *i += (jf - f) * *jf * *jg;
        *i *= inv[i - g];
    }
}
void Exp(Z f[], int n) { copy(f, tg, n); Exp(tg, f, n); }
#undef forj
}
struct SPS { //Set Power Series
    int n;
    Z D[mL][mN];
    void FWT() {
        for (int i = 1; i < 1 << n; i <<= 1)
        for (auto j = D; j < D + (1 << n); j += i << 1)
        for (auto k0 = j, k1 = j + i; k0 < j + i; k0++, k1++)
        for (auto l0 = *k0, l1 = *k1; l0 <= *k0 + n; l0++, l1++)
            *l1 += *l0;
    }
    void iFWT() {
        for (int i = 1; i < 1 << n; i <<= 1)
        for (auto j = D; j < D + (1 << n); j += i << 1)
        for (auto k0 = j, k1 = j + i; k0 < j + i; k0++, k1++)
        for (auto l0 = *k0, l1 = *k1; l0 <= *k0 + n; l0++, l1++)
            *l1 -= *l0;
    }
    void clear() {
        for (auto s = D; s < D + (1 << n); s++)
        for (auto j = *s; j <= *s + n; j++)
            *j = 0;
    }
    void copy(SPS &b) {
        for (auto s0 = D, s1 = b.D; s0 < D + (1 << n); s0++, s1++)
        for (auto j0 = *s0, j1 = *s1; j0 <= *s0 + n; j0++, j1++)
            *j0 = *j1;
    }
};
int main() {
    init();  // important
}