【代数】美好的昔日

WeLikeStudying · 2022-02-05 16:45:16 · 算法·理论

• \text{For auld lang syne, my dear,}
• \text{For auld lang syne,}
• \text{We'll tak a cup o'kindness yet,}
• \text{For auld lang syne!}

错排问题

• 话说天地初开，有 n 个人，编号为 1 到 n。
• 这 n 个人站成一排，使得第 i 个人不能站在第 i 个位置。
• 我且问你，这方案数如何计算？

容斥原理

• 作者实在是太菜了，只会算 n=3。
• 考虑随便站，一共有 3! 种站法。
• 减去 1 号站对了的 2! 种。
• 减去 2 号站对了的 2! 种。
• 减去 3 号站对了的 2! 种。
• 加上 1,2 号站对了的 1! 种。
• 加上 1,3 号站对了的 1! 种。
• 加上 2,3 号站对了的 1! 种。
• 最后减去都站对了的 0! 种。
• 于是得到答案是 2。
• 注意到容斥的系数是正负 1，而算人可以用组合数。 \sum_{i=0}^n(-1)^iC(n,i)(n-i)!
• 搞完了！

容斥原理的背后

• 为啥容斥系数是 (-1)^i？
• 因为在计算 m 个人时（m>1），我们在之前提到了 m 个人（中的 k 个）的方案数是： \sum_{i=0}^{m-1}(-1)^iC(m,i)=1-(-1)^m
• 所以如果要正确就一定要加上 (-1)^m。
• 容斥原理的证明就是利用了： \sum_{i=0}^m(-1)^mC(m,i)=[n=0]

二项式反演

• 设 f(n) 为 n 个人随便站的方案数。
• 考虑枚举随便站有多少人站错，有： f(n)=\sum_{i=0}^nC(n,i)g(i)
• 那么如果我们知道 g(n) 就可以用它求 f(n) 了（？）！
• 当然不止于此，接下来引入一个个人更愿意称为套路的东西。
• 说一句性质： \sum_{i=0}^m(-1)^iC(m,i)=[n=0]
• 说一句废话（？）： g(n)=\sum_{i=0}^n[n-i=0]C(n,i)g(i)
• 将性质代入废话： g(n)=\sum_{i=0}^n\sum_{j=0}^{n-i}(-1)^jC(n-i,j)C(n,i)g(i)
• 考虑到 C(n,i)\times C(n-i,j)=C(n,j)\times C(n-j,i)：（相当于在 n 个元素的集合中选择大小为 i 和 j 的不相交子集） g(n)=\sum_{i=0}^n\sum_{j=0}^{n-i}(-1)^iC(n-j,i)C(n,j)g(i)
• 交换求和号： g(n)=\sum_{i=0}^n\sum_{j=0}^{n-i}(-1)^iC(n-i,j)C(n,i)g(j) g(n)=\sum_{i=0}^n(-1)^iC(n,i)\sum_{j=0}^{n-i}C(n-i,j)g(j)
• 捕捉 f 君： g(n)=\sum_{i=0}^n(-1)^iC(n,i)f(n-i) g(n)=\sum_{i=0}^n(-1)^{n-i}C(n,i)f(i)
• 让我们端详一下： f(n)=\sum_{i=0}^nC(n,i)g(i) g(n)=\sum_{i=0}^n(-1)^{n-i}C(n,i)f(i)
• 哟，这不是二项式反演吗，怎么跑来混在我们的容斥原理里了。
• 那么啥是反演呢？

反演的定义

• 假设存在函数 f,g 满足： f(n)=\sum_{k}a(n,k)g(k)
• 已知 f 求 g 是平凡的，已知 g 求 f 就是反演。
• 是不是想到了啥？高斯消元！过于平凡。
• 特别的反演可以为解题提供思路。

反方向的二项式反演（？）

• 套路。
• 计数技巧。

没有循环节的字符串

• 求长度为 n 且仅包含小写英文字母且循环节长度恰为 n 的字符串的个数。

莫比乌斯反演

• 设 f(n) 是长度为 n 且仅包含小写英文字母的字符串的个数。
• 设 g(n) 是长度为 n 且仅包含小写英文字母且循环节长度恰为 n 的字符串的个数。
• 枚举循环节长度，有： f(n)=\sum_{d|n}g(d)
• 套路。

反演的背后

• 设矩阵 A,B 满足 a_{i,j}=[i|j],b_{i,j}=[i|j]\mu(\frac ji)。
• 那么我们刚才推出的结论就是 AB=I。
• 刚才就是在解方程 Ag=f，ABg=Bf，g=Bf。
• 即找逆矩阵。
• 这里提醒一下前两个特殊情况的 A 都是下三角矩阵，所以消元是 O(n^2) 的。

反方向的莫比乌斯反演（？）

• 套路。

UOJ某题目

• 怎样跑得更快。

某经典题目

• 有两个集合 U 的子集到实数的单射 a,b，定义单射 c 为： c(S)=\sum_{P\cup Q=S}a(P)b(Q)
• 求单射 c。
• 暴力枚举子集的复杂度为 O(3^{|U|})。
• 算贡献需要好拆分，这个不好拆，什么好拆？ [P\cup Q\subseteq S]=[P\subseteq S][Q\subseteq S]
• 设： f'(S)=\sum_{P\subseteq S}f(P)
• 那么就很无脑了：通过高维前缀和算出 a',b'，乘起来得到 c'，高维前缀差分再算出 c，这一切的复杂度被控制在 O(|U|2^{|U|})：
• 正变换：

  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)];

子集反演

- 对了，举前缀差分一例，现象相当有趣。
- 设：
$$\frac ab=(a_1-b_1,a_2-b_2,\cdots,a_n-b_n)$$
$$\mu(a)=\prod_{i=1}^n[a_i\le 1](-1)^{a_i}$$
$$f(a)=\sum_{b\le a}g(b)\leftrightarrow g(a)=\sum_{b\le a}\mu\bigg(\frac ab\bigg)f(b)$$
- 怎么推出来的，其实就是考虑向量 $a$，将它对大于等于它且每个维度相差都不超过 $1$ 的 $2^k$ 个向量的贡献表示出来，发现它刚好形成了规则的正负 $1$ 的形式而且对于其它向量恰好毫无贡献。
- 怎么似李？莫比乌西反演？

• 咱们数学推导就可以用那个反演，最终得到（更严谨的推导）。 f(S)=\sum_{P\subseteq S}g(P) f(S)=\sum_{P\subseteq S}(-1)^{|S|-|T|}g(P)

一些变形

• 关于与运算。
• 关于多重子集。
• 关于子集卷积。

离散傅里叶变换

• 已知 n 是 2 的整数次幂，给出长度为 n 的向量 a,b ，求 c 满足： c_k=\sum_{(i+j)\bmod n=k}a_ib_j
• 很久以前写的博客终于派上用场。
• 贴一下核心的结论： f(n)=\sum_{k=1}^ng(k)\omega_n^k g(n)=\frac 1n\sum_{k=1}^nf(k)\omega_n^{-k}

反演背后

• 看起来反演可以解决一些卷积： c(k)=\sum_{\text{表达式}(i,j)}a(i)b(j)
• 我们就是要让原本紧密联系的表达式分开来，也就是要求我们找到一种变换。
• 方法大概是正变换一下，乘起来再逆变换一下。

总结

• 这只是一些概念，留待补充练习。