【代数】高维前缀和
WeLikeStudying · · 算法·理论
- 高维前缀和有传统的方法和非传统的方法：传统的是容斥：
- 另一种方法：
- 定义
n 维非负整数向量a=(a_1,a_2,\cdots,a_n) 的偏序关系\le 为：a\le b\leftrightarrow a_1\le b_1,a_2\le b_2,\cdots ,a_n\le b_n -
- 定义
n 维非负整数向量的空间|a| 为：\prod_{i=1}^na_i - 已知定义域
U=\{a|a\le m\} （a,m 都是长度为n 的向量）的n 元函数f(a) 。 - 计算定义域为
U 的n 元函数：g(a)=\sum_{b\le a}f(b) - 传统的基于容斥原理的方法时间是
O(2^n|m|) 的。 - 非传统的方法是动态规划。
- 设
h(a,i) 为除前i 维的所有维度都与向量a 相同的点对g(a) 的贡献，易得：h(a,0)=f(a) h(a,n)=g(a) h(0,j)=f(0)=g(0) - 设
n 维向量b 满足对于它的任何一维的值b_j 都有b_j=a_j-[i=j] ，则：h(a,i)=h(a,i-1)+h(b,i) - 时间复杂度为
O(n|m|) 。 - 类似地，还有高维后缀和（我只把改变的部分写上）：
g(a)=\sum_{a\le b}f(b) b_j=a_j+[i=j] - 高维前缀差分：
f(a)=\sum_{b\le a}g(b) h(a,i)=h(a,i-1)-h(b,i-1) - 高维后缀差分：
f(a)=\sum_{a\le b}g(b) h(a,i)=h(a,i-1)-h(b,i-1) b_j=a_j+[i=j] - 虽然仿照高维前缀和，这些推导是相当平凡的，但是由于某些原因，仍然希望各位意识到差分为什么是
h(b,i-1) ，而且结合我一开始的那张图，问题会变得容易。 - 对了，举前缀差分一例，现象相当有趣。
- 设：
\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 的形式而且对于其它向量恰好毫无贡献，更严谨的基于可重集的证明（莫比乌斯反演）。 - 怎么似李？莫比乌西反演？
- 高维前缀和本身并不复杂，但它的变化时常让人感到惊讶。
变形1
- 举例。
- 经典的高维前缀和的应用（虽然我当时不是这么想的），关于质因子次数做高维前缀和，考虑到枚举到某个质因子时不是它的倍数的可以不更新，时间复杂度同埃拉托斯特尼筛法
O(n\log\log n) 。 - 简单变形。
变形2
-
$$f(S)=\sum_{T\subseteq S}g(T)$$ - 的式子时实际上使用的是高维前缀和的方法减少时间复杂度（要不然再枚举一遍子集还是
3^n ），详细见有关博客。
变形3
- 计算一个无向图的独立集的数目怎么做？
- 朴素的枚举是
O(m2^n)-O(2^n) 的（可以预处理每个点的禁止集合，查询时合并），考虑折半枚举。 - 设枚举点集大小为
a ，考虑与另一个n-a 大小的点集合并，中途的有些点可能不能要了，所以要查询f(S,i) 即在点集S 中选出个独立集的方案数。 - 如果是
O(3^{n-a}) 的朴素求法的话，取a\sim \frac{\log_23}{1+\log_23}x ，得到复杂度：O(3^{\frac1{1+\log_23}n})\sim O(1.96^n) - 并没有好多少，在实际应用中和
O(2^n) 无差别。 - 但是如果在转移使用高维前缀和的话，时间复杂度就是
O(2^{n-a}+(n-a)2^{n-a}) ，取a\sim \frac {n+\log_2n}2 ，时间复杂度就是：O(\sqrt{n2^n}) - 不知道比原来小多少。
- 虽然这题只需要枚举所有状态后搞一个高位前缀和即可，但所有类似的子集枚举动态规划都可以尝试用这样的方式优化。
- 大概就是把：
for(int S=0;S<(1<<n);++S) for(int B=(S-1)&S;B;B=(B-1)&S) f[S]=a_function(f[S],f[S^B]); - 换成：
for(int i=0;i<n;++i) for(int S=0;S<(1<<n);++S) if(S&(1<<i))f[S]=a_function(f[S],f[S^(1<<i)]);