炫酷反演魔术

一道经典题

我们先说点水爆了的内容吧！

• 说从前有 $n$ 个人，编号为 $1, \dots, n$。
• 这 $n$ 个人站成一排，编号为 $i$ 的人不能站在第 $i$ 个。
• 求方案数。
• $n \leq 10^5$

感觉地球人都知道怎么做

可以用小学生的容斥来解决！

小学生的容斥

• 作为小学生，我们只会算 $3$ 个人！
• 考虑随便站，一共 $3!$ 种站法。
• 然后减去 $1$ 号站对了的站法 $2!$
• 然后减去 $2$ 号站对了的站法 $2!$
• 然后减去 $3$ 号站对了的站法 $2!$
• 然后加上 $1, 2$ 号站对了的站法 $1!$
• 然后加上 $2, 3$ 号站对了的站法 $1!$
• 然后加上 $3, 1$ 号站对了的站法 $1!$
• 然后减去都站对了的站法 $1!$
• 于是得到答案是 $2$

中学生的容斥

• 作为中学生，我们可以发现刚才的过程是：容斥斥斥容容容斥。
• 注意容斥的系数一定是正负一。选若干个人我们显然可以用组合数。
• 大胆猜想小(bu)心(yong)证明之后，对于一般的 $n$，我们可以得到：
• \begin{equation} \sum_{k = 0}^{n}{(-1)^k\binom{n}{k} (n - k)!} \end{equation}
• 搞完啦～

容斥的幕后

\begin{equation} \sum_{k = 0}^{n}{(-1)^k\binom{n}{k} (n - k)!} \end{equation}

• 为啥恰好是 $+1$ 或者 $-1$？
• 原理：考虑一个恰有 $m$ 个人站对了的方案（$m \geq 1$），那么在考虑 $0$ 到 $m - 1$ 个人的时候，会一不小心把这组方案算这么多次：（见下一页）

\begin{eqnarray} & & \sum_{k = 0}^{m - 1}{(-1)^k \binom{m}{k}} \\ & = & \sum_{k = 0}^{m}{(-1)^k \binom{m}{k}} - (-1)^{m} \\ & = & (1 + (-1))^{m} - (-1)^{m} \\ & = & -(-1)^{m} \end{eqnarray}

• 既然是 $-(-1)^m$，那就强行加回来！于是有 $m$ 个人站对了的方案就全被消了

另一个角度

• 我们证明的过程中，其实主要就是用了这货： \begin{equation} \sum_{k = 0}^{n}{(-1)^k\binom{n}{k}} = 0 \end{equation}

• 请注意上面的式子有个例外，就是 $n = 0$ 时左边为 $1$。正确的写法是： \begin{equation} \sum_{k = 0}^{n}{(-1)^k\binom{n}{k}} = [n = 0] \end{equation}

  其中 $[P]$ 即 $P$ 成立时为 $1$，不成立时为 $0$。

一点小性质

• 设 $f(n)$ 为 $n$ 个人随便站的方案数。
• 设 $g(n)$ 为 $n$ 个人都站错的方案数。
• 如果知道 $g$ 的表达式，那么我们可以通过枚举有多少人站错了位置来得到 $f$： \begin{equation} f(n) = \sum_{k = 0}^{n}{\binom{n}{k} g(k)} \end{equation}

• 等等我们好像是不知道 $g$ 而知道 $f$ 吧！

  

魔术

• 首先说一句废话： \begin{equation} g(n) = \sum_{m = 0}^{n} [n - m = 0] \binom{n}{m} g(m) \end{equation}
• 回忆我们刚才发现的性质： \begin{equation} \sum_{k = 0}^{n}{(-1)^k\binom{n}{k}} = [n = 0] \end{equation}
• 代进去： \begin{equation} g(n) = \sum_{m = 0}^{n} \sum_{k = 0}^{n - m} (-1)^k \binom{n - m}{k} \binom{n}{m} g(m) \end{equation}

• 注意 $\binom{n - m}{k} \binom{n}{m}$ 意思是在 $n$ 个里面两个子集一个大小为 $m$ 另一个大小为 $k$，所以和 $\binom{n}{k} \binom{n - k}{m}$ 其实是等价的。
• \begin{eqnarray} g(n) & = & \sum_{m = 0}^{n} \sum_{k = 0}^{n - m} (-1)^k \binom{n - m}{k} \binom{n}{m} g(m) \\ & = & \sum_{m = 0}^{n} \sum_{k = 0}^{n - m} (-1)^k \binom{n}{k} \binom{n - k}{m} g(m) \end{eqnarray}
• 交换两个求和符号： \begin{equation} g(n) = \sum_{k = 0}^{n} (-1)^k \binom{n}{k} \sum_{m = 0}^{n - k} \binom{n - k}{m} g(m) \end{equation}
• 注意最右边的那个小朋友！其实就是 $f$！

• 变成： \begin{equation} g(n) = \sum_{k = 0}^{n} (-1)^k \binom{n}{k} f(n - k) \end{equation}
• 把下标换得漂亮点： \begin{equation} g(n) = \sum_{k = 0}^{n} (-1)^{n - k} \binom{n}{k} f(k) \end{equation}

又一道经典题

• 求长度为 $n$ 且仅包含小写英文字母且循环节长度恰为 $n$ 的字符串的个数。
• 循环节……就是最短的复制若干遍后拼起来跟原串相等的字符串。
• $n \leq 10^9$

感觉地球人都知道怎么做

• 一忘皆空！哈哈我假设你们都不会莫某某的反演了。
• 设 $f(n)$ 表示长度为 $n$ 的字符串的个数。
• 设 $g(n)$ 表示长度为 $n$ 的且周期为 $n$ 的字符串的个数。

• 而且：

  \begin{equation} f(n) = \sum_{d \mid n}{g(d)} \end{equation}

• $f$ 显然好求，他就是 $26^n$。看起来如果这里有个反演就爽了。

魔术准备

• 回忆二项式反演时我们干了什么。
• 找到了一个 if 语句： \begin{equation} \sum_{k = 0}^{n}{(-1)^k\binom{n}{k}} = [n = 0] \end{equation}
• 说了一句废话： \begin{equation} g(n) = \sum_{m = 0}^{n} [n - m = 0] \binom{n}{m} g(m) \end{equation}
• 然后带进去搞搞居然就凑出来了个 $f$。

魔术

• 我们如法炮制。由于现在是各种整除，所以我们可以利用两数之比为 $1$ 来判定是否等于 $n$。

• 我们设函数 $\mu(n)$ 满足：

  \begin{equation} \sum_{d \mid n} \mu(d) = [n = 1] \end{equation}

  可以知道 $\mu(\prod_p p^\alpha) = \prod_p [\alpha = 1](-1)$ （为啥是这个式子以后再侃 = =）

• 接下来说一句废话

  \begin{equation} g(n) = \sum_{m \mid n} [\frac{n}{m} = 1]g(m) \end{equation}

• 代进去！

  \begin{equation} g(n) = \sum_{m \mid n} \sum_{d \mid \frac{n}{m}} \mu(d) g(m) \end{equation}

• 注意 $d \mid \frac{n}{m}$ 其实就是 $md \mid n$，所以跟 $m \mid \frac{n}{d}$ 等价。似曾相识，对不？
• 交换两个求和符号： \begin{equation} g(n) = \sum_{d \mid n} \mu(d) \sum_{m \mid \frac{n}{d}} g(m) \end{equation}
• $f$ 君好久不见。

• \begin{equation} g(n) = \sum_{d \mid n} \mu(d) f(\frac{n}{d}) \end{equation}

• 把下标换得漂亮点：

  \begin{equation} g(n) = \sum_{d \mid n} \mu(\frac{n}{d}) f(d) \end{equation}

莫比乌斯反演

所以我们就得到了酱紫的东西：（妈呀其实这也是容斥）

\begin{eqnarray} f(n) & = & \sum_{d \mid n} g(d)\\ g(n) & = & \sum_{d \mid n} \mu(\frac{n}{d}) f(d) \end{eqnarray}

魔术幕后

• 首先要有一个性质，比如这样：

  \begin{equation} \sum_{d \mid n} \mu(d) = [n = 1] \end{equation}

• 但是你会发现我们其实真正用的是这个： \begin{equation} [m \mid n] \sum_{d \mid \frac{n}{m}} \mu(d) = [\frac{n}{m} = 1] = [n = m] \end{equation}
• 令 $c = md$ 左边可以写成这样： \begin{equation} \sum_{c \mid n} [m \mid c] \mu(\frac{c}{m}) \end{equation}

矩阵形式

• 令 $A_{c, n} = [c \mid n]$，$B_{m, c} = [m \mid c] \mu(\frac{c}{m})$
• 刚才的结论就是 $BA = I$
• 刚才解 $Ax = b$ 的推导过程就是： \begin{eqnarray} x & = & Ix \\ x & = & (BA)x \\ x & = & B(Ax) \\ x & = & Bb \end{eqnarray}

• 所以瞬间这个魔术就无聊了。找那个神奇的“性质”难度等同于找逆矩阵。

  

下三角矩阵

= =……我还是得说几句。刚才我们看到的要反演原式……

• \begin{eqnarray} f(n) & = & \sum_{k = 0}^{n} \binom{n}{k} g(k)\\ f(n) & = & \sum_{d \mid n} g(d) \end{eqnarray}
• 他们都有一个共同特点，就是 $f(n)$ 所依赖的 $g(k)$ 都满足 $k \leq n$。

• 妈呀这不就是下三角矩阵？那逆矩阵还用我来说？

  

魔术

• 现在我们来推 $k \leq n$ 的一般情况，即：

  \begin{equation} f(n) = \sum_{k = 1}^{n} a_{n, k} g(k) \end{equation}

• 不过你已经知道对手的底牌了，其实就没什么意思了。由于是线性变换，所以我们就是要算每个 $f(m)$ 对答案的贡献。
• 所以对于每一个 $m$ 我们求出当 $f(m) = 1$ 而其它的 $f$ 都是 $0$ 的情况下的 $g$ 就行了，用 $\mu(n, m)$ 来表示这个解。

• 那么一定满足性质：

  \begin{equation} \sum_{k = 1}^{n} a_{n, k} \mu(k, m) = [n = m] \end{equation}

  这个可以递推求出。

• 然后我们不用废话了，答案很明显了：

  \begin{equation} g(n) = \sum_{k = 1}^{n} \mu(n, k) f(k) \end{equation}

• 魔术变完了！

• = =+ 成功骗过若干位小朋友。这个魔术没有任何实际效果，因为这个倒霉的 $\mu$ 啊就是逆矩阵，刚才推了半天等于白推。数论里的 $\mu$ 能求出表达式也不是每个 $\mu$ 都能搞的。
• 假如你不能手推出 $\mu$ 的表达式，那么还不如 $O(n^2)$ 裸消元。
• 曾经看见过“偏序集上的莫比乌斯函数”！但是对于一般情况感觉它设了个逆矩阵然后弃疗了？也可能是我读书少……T_T……
• 弃疗吧……大概就这样了。

另一方向的莫比乌斯反演？

• \begin{eqnarray} f(n) & = & \sum_{n \mid d} g(d)\\ g(n) & = & \text{萌萌哒} \end{eqnarray}
• 问萌萌哒是什么？

\begin{equation} \text{萌萌哒} = \sum_{n \mid d} \mu(\frac{d}{n}) f(d) \end{equation}

UOJ Round #5 C

• 令 $p = 998244353$（$7 \times 17 \times 2^{23} + 1$，一个质数）。

• 给你整数 $n, c, d$。现在有整数 $x_1, \dots, x_n$ 和 $b_1, \dots, b_n$ 满足 $0 \leq x_1, \dots, x_n, b_1, \dots, b_n < p$，且对于 $1 \leq i \leq n$ 满足：

  \begin{equation} \sum_{j = 1}^{n} \gcd(i, j)^c \cdot \lcm(i, j)^d \cdot x_j \equiv b_i \pmod{p} \end{equation}

• 有 $q$ 个询问，每次给出 $b_1, \dots, b_n$，请你解出 $x_1, \dots, x_n$ 的值。
• $n \leq 10^5$, $nq \leq 3 \times 10^5$

• 首先学过小学奥数的我们知道：$\lcm(i, j) = \frac{ij}{\gcd(i. j)}$。所以这题其实是：

  \begin{equation} \sum_{j=1}^n \gcd(i,j)^{c - d} \cdot i^d \cdot j^d \cdot x_j = b_i \end{equation}

• 但是其实这种题都可做： \begin{equation} \sum_{j=1}^n f(\gcd(i,j)) \cdot g(i) \cdot h(j) \cdot x_j = b_i \end{equation}

• 其实关键的坑人的地方在于 $f(\gcd(i,j))$。假设我有一个函数 $f_r(n)$，满足 $f(n) = \sum_{d \mid n}{f_r(d)}$。知道 $f$ 后 $f_r$ 是很好搞的，只要莫比乌斯反演就行了。
• 为什么要这样？因为我们知道如果 $d \mid \gcd(i, j)$ 那么肯定有 $d \mid i$ 且 $d \mid j$，反之亦然。这样就把讨厌的 $\gcd$ 给去掉了。

• 所以我们可以写出这样的等式：

  \begin{equation} \sum_{j = 1}^n \sum_{d}[d \mid i][d \mid j] \cdot f_r(d) \cdot g(i) \cdot h(j) \cdot x_j = b_i \end{equation}

• 接下来怎么办？好像并没有简化问题。我们老样子把两个求和符号反过来，得到：

  \begin{equation} \sum_{d} \sum_{j=1}^n [d \mid i][d \mid j] \cdot f_r(d) \cdot g(i) \cdot h(j) \cdot x_j = b_i \end{equation}

• 然后我们移一下项： \begin{equation} \sum_{d \mid i} f_r(d) \sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j = b_i / g(i) \end{equation}

• 仔细观察，发现 $\sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j$ 的意思是把所有 $j$ 是 $d$ 的倍数的 $h(j) \cdot x_j$ 加起来。反正这个只跟 $d$ 的值有关，我们记为 $z_d$。于是我们得到： \begin{equation} \sum_{d \mid i} f_r(d) z_d = b_i / g(i) \end{equation}
• 这个式子的意思是，对于每个 $i$，把所有 $d$ 是 $i$ 的约数的 $f_r(d) z_d$ 加起来，得到结果 $b_i / g(i)$。现在我们知道右边，想求左边，莫比乌斯反演就行了。

• 这样得到就得到了 $f_r(d) z_d$。想得到 $z_d$？由于 $f_r(d)$ 已经求出，所以除一下就行。
• 但是 $z_d$ 并不是最终答案。回忆 $z_d$ 的表达式： \begin{equation} z_d = \sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j \end{equation}
• 现在知道左边，想求右边，还是莫比乌斯反演。
• 嗯，现在我们知道了 $h(j) x_j$，那么 $x_j$ 就好求了。

• 小细节：由于中间过程涉及了除法，所以就会带来无解和多解的情况，这个自己玩吧。
• 咳，预备，起！这题其实就是把 $b$ 除以 $g(i)$ 然后莫比乌斯反演，然后除以 $f$ 的莫比乌斯反演，再进行莫比乌斯反演，再除以 $h(j)$，三个莫比乌斯反演掷地有声。

题外话

• 这题其实就是求了 $A_{i, j} = f(\gcd(i, j)) \cdot g(i) \cdot h(j)$ 的逆矩阵。

• 见过有人对一个数组求它的莫比乌斯反演是：

  1. 筛法筛素数！
  2. 筛法同时求莫比乌斯函数！

  3. $O(\sqrt{n})$ 枚举约数，狄利克雷卷积！

     

丢代码跑：

\begin{equation} f(n) = \sum_{d \mid n} g(d) \end{equation}

  for (int i = 1; i <= n; i++)
      g[i] = f[i];
  for (int i = 1; i <= n; i++)
      for (int j = i + i; j <= n; j += i)
          g[j] -= g[i];

又一道经典题

• 有两个长度为 $2^n$ 的数列 $a_0, \dots, a_{2^n-1}$，$b_0, \dots, b_{2^n-1}$。
• 求数列 $c$，其中 \begin{equation} c_r = \sum_{p, q} [p \or q = r] a_p b_q \end{equation}
• $n \leq 20$

感觉地球人都知道怎么做

• 显然我们把下标看作集合为妙。下面不区分普通的数和集合。
• 那么原式相当于 $p \cup q = r$ 的 $p, q$ 给 $r$ 做贡献。但是 $p \cup q = r$ 并不好处理。
• 注意到 $[p \cup q \subseteq s] = [p \subseteq s][q \subseteq s]$，这样能把贡献拆开。
• 我们对于一个数列 $a$ 定义 $a'$ 满足 $a'_s = \sum_{p \subseteq s} a_p$。

• 已知 $a$ 求 $a'$ 这个 $O(n2^n)$ DP下就行对吧，其实就是个高维前缀和。
• \begin{eqnarray} c'_r & = & \sum_{p, q} [p \or q \subseteq r] a_p b_q \\ & = & \sum_{p, q} [p \subseteq r][q \subseteq r] a_p b_q \\ & = & \sum_{p} [p \subseteq r] a_p \sum_{q}[q \subseteq r] b_q \\ & = & a'_r b'_r \end{eqnarray}
• 反演君我看见你了！现在已知 $c'$ 要求 $c$。

• 其实这个很无脑啊，倒着写就行了。

• 方便代码能力弱的选手：

  for (int i = 0; i < n; i++)
      for (int s = 0; s < (1 << n); s++)
          if (s >> i & 1)
              f[s] += f[s ^ 1 << i];

  无脑反着写：

  for (int i = 0; i < n; i++)
      for (int s = 0; s < (1 << n); s++)
          if (s >> i & 1)
              f[s] -= f[s ^ 1 << i];

魔术

• 不过要是用于数学推导的话代码君是推不动滴。所以我们还是来按以前方法直接上吧。

• 然后发现一个比较显然的性质：（妈呀其实就是二项式反演里的那个玩意儿）

  \begin{equation} \sum_{r \subseteq p} (-1)^{\lvert r \rvert} = [p = 0] \end{equation}

  这里的 $\lvert r \rvert$ 表示集合的大小。

• 然后像以前一样做：

  \begin{eqnarray} g(p) & = & \sum_{q \subseteq p} [p - q = 0] g(q) \\ & = & \sum_{q \subseteq p} \sum_{r \subseteq p - q} (-1)^{\lvert r \rvert} g(q) \\ & = & \sum_{r \subseteq p} (-1)^{\lvert r \rvert} \sum_{q \subseteq p - r} g(q) \\ & = & \sum_{r \subseteq p} (-1)^{\lvert r \rvert} f(p - r) \\ & = & \sum_{r \subseteq p} (-1)^{\lvert p \rvert - \lvert r \rvert} f(r) \end{eqnarray}

小练习：多重子集反演

• 多重子集即允许元素出现多次的集合。
• \begin{eqnarray} f(S) & = & \sum_{T \subseteq S} g(T)\\ g(S) & = & \text{沼跃鱼} \end{eqnarray}
• 问沼跃鱼是什么？

• 定义 $\mu(S)$，$S$ 包含重复元素则为 $0$，否则为 $(-1)^{\lvert S \rvert}$。（嘛。。。就是容斥时的系数）
• 可以知道： \begin{eqnarray} \sum_{T \subseteq S} \mu(T) = [S = 0] \end{eqnarray}

• 于是：

  \begin{eqnarray} f(S) & = & \sum_{T \subseteq S} g(T)\\ g(S) & = & \sum_{T \subseteq S} \mu(S - T) f(T) \end{eqnarray}

  你会觉得非常似曾相识！

• 一个数可以对应着一个多重子集，即它的素因数分解。

  所以以多重子集的角度来看，数论里的莫比乌斯函数简直显然得不能再显然了。

又一道经典题

• 有两个长度为 $n$ 的数列 $a_0, \dots, a_{n-1}$，$b_0, \dots, b_{n-1}$。
• 求数列 $c$，其中 \begin{equation} c_r = \sum_{p, q} [(p + q) \bmod n = r] a_p b_q \end{equation}
• $n$ 是 $2$ 的整数次幂，$n \leq 2^{20}$。

感觉地球人都知道怎么做

• 数论中走街串巷杀题越货之必备良品——复数。
• 设 $\epsilon$ 是单位根，即满足 $\epsilon^n = 1$ 的……那个长得很像单位的根，即 $e^{-\frac{2 \pi i}{n}}$。
• 显然： \begin{equation} \sum_{k = 0}^{n - 1} \epsilon^{vk} = \frac{\epsilon^{nvk} - 1}{\epsilon^{vk} - 1} = 0 \end{equation}
• 有什么问题？

• 学过小学数学的我们知道，等比数列公比为 $1$ 时要特判。看，if 来了：

  \begin{equation} \frac{1}{n}\sum_{k = 0}^{n - 1} \epsilon^{vk} = [v \bmod n = 0] \end{equation}

魔术

• 注意到：

  \begin{eqnarray} & & [(p + q) \bmod n = r] \\ & = & [(p + q - r) \bmod n = 0] \\ & = & \frac{1}{n}\sum_{k = 0}^{n - 1} \epsilon^{(p + q - r)k} \\ & = & \frac{1}{n}\sum_{k = 0}^{n - 1} \epsilon^{-rk} \epsilon^{pk} \epsilon^{qk} \end{eqnarray}

  这三部分几乎是独立的！

• \begin{eqnarray} c_r & = & \sum_{p, q} [(p + q) \bmod n = r] a_p b_q \\ & = & \sum_{p, q} \frac{1}{n} \sum_{k = 0}^{n - 1} \epsilon^{-rk} \epsilon^{pk} \epsilon^{qk} a_p b_q \\ & = & \frac{1}{n} \sum_{k = 0}^{n - 1} \epsilon^{-rk} \sum_{p, q} \epsilon^{pk} a_p \epsilon^{qk} b_q \\ & = & \frac{1}{n} \sum_{k = 0}^{n - 1} \epsilon^{-rk} \sum_{p} \epsilon^{pk} a_p \sum_{q} \epsilon^{qk} b_q \\ \end{eqnarray}
• 抓到你了！反演君！

另一个方向的子集反演？

• 有两个长度为 $2^n$ 的数列 $a_0, \dots, a_{2^n-1}$，$b_0, \dots, b_{2^n-1}$。
• 求数列 $c$，其中 \begin{equation} c_r = \sum_{p, q} [p \and q = r] a_p b_q \end{equation}
• $n \leq 20$

教练我不会创新！

• 妈呀那你就把集合取反然后搞 $\or$。
• 然后就没有然后了。。。至少对于码代码来说这样就够了。

• 如果要用于推导：

  \begin{eqnarray} f(S) & = & \sum_{S \subseteq T} g(T)\\ g(S) & = & \sum_{S \subseteq T} (-1)^{\lvert T \rvert - \lvert S \rvert} f(T) \end{eqnarray}

子集卷积

• 有两个长度为 $2^n$ 的数列：$a_0, \dots, a_{2^n-1}$ 和 $b_0, \dots, b_{2^n-1}$。
• 求数列 $c$，其中 \begin{equation} c_r = \sum_{p \subseteq r} a_p b_{r - p} \end{equation}
• 要求 $O(n^2 2^n)$

• \begin{eqnarray} c_r & = & \sum_{p, q \subseteq r} [p \and q = 0][p \or q = r] a_p b_q \\ & = & \sum_{p, q \subseteq r} [p \and q = 0]\sum_{v \subseteq r} (-1)^{\lvert r \rvert - \lvert v \rvert} [p \subseteq v][q \subseteq v] a_p b_q \\ & = & \sum_{v \subseteq r} (-1)^{\lvert r \rvert - \lvert v \rvert} \sum_{p, q \subseteq v} [p \and q = 0] a_p b_q \\ & = & \sum_{v \subseteq r} (-1)^{\lvert r \rvert - \lvert v \rvert} \sum_{u \subseteq v} (-1)^{\lvert u \rvert} \sum_{p} [u \subseteq p \subseteq v] a_p \sum_{q} [u \subseteq q \subseteq v] b_q \\ \end{eqnarray}

• 妈呀不会做了！

  

• 失败的原因是又用交集又用并集，让我们统一成并集吧！
• 多记录一维，$c_{r, i}$ 表示 $\sum_{p \subseteq r} [\lvert p \rvert = i] a_p b_{r - p}$。

• 这样就爽多了：

  \begin{eqnarray} c_{r, i} & = & \sum_{p, q \subseteq r} [\lvert p \rvert = i] [\lvert q \rvert = \lvert r \rvert - i] [p \or q = r] a_p b_q \\ & = & \sum_{p, q \subseteq r} [\lvert p \rvert = i][\lvert q \rvert = \lvert r \rvert - i] \sum_{v \subseteq r} (-1)^{\lvert r \rvert - \lvert v \rvert} [p \subseteq v] [q \subseteq v] a_p b_q \\ & = & \sum_{v \subseteq r} (-1)^{\lvert r \rvert - \lvert v \rvert} \sum_{p, q \subseteq v} [\lvert p \rvert = i] [\lvert q \rvert = \lvert r \rvert - i] a_p b_q \\ & = & \sum_{v \subseteq r} (-1)^{\lvert r \rvert - \lvert v \rvert} \sum_{p \subseteq v} [\lvert p \rvert = i] a_p \sum_{q \subseteq v} [\lvert q \rvert = \lvert r \rvert - i] b_q \end{eqnarray}

• 搞定！
• 只要对 $a$ 定义 $a'$ 满足 $a'_{p, i} = \sum_{s \subseteq p} [\lvert s \rvert = i] a_s$，然后就行了。
• 显然都能在 $O(n^2 2^n)$ 时间内搞定。