Note -「SOS DP」高维前缀和

本文差不多算是翻译了一遍 CF blog?id=45223 就是抄了一遍,看不懂可以去原文。

当然我的翻译并不是完全遵从原文的。

Part. 1 Introduction

平时我们怎么求高维前缀和?容斥对吧,复杂度多少?\(\mathcal{O}(n^{d}\times2^{d})\)(\(n\) 每维元素个数,默认同阶,\(d\) 维度)。

这好吗?这不好。

Part. 2 Ying Wen

For 个 example,二维,容斥这么写对吧?

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

事实上我们还可以分维来前缀和:

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

复杂度多少?\(\mathcal{O}(n^{d}\times d)\),厉害吧。

对应到 SOS DP(sum over subsets),我们把每一维整到集合上去来求子集和。

形式化地定义子集和,即给定一个有 \(2^{n}\) 个元素的数组 \(A\),定义函数:

\[\text{sub-sum}(mask)=\sum_{i\subseteq mask}A_{i} \]

写成位运算的形式:

\[\text{sub-sum}(mask)=\sum_{mask\text{ & }i=i}A_{i} \]

学过 FWT 的巨佬可能发现了什么,可是这和我没关系。

看不懂?没关系,我们有严谨的代码定义:

for(int mask = 0;mask < (1<<N); ++mask){
	for(int i = 0;i < (1<<N); ++i){
		if((mask&i) == i){
			F[mask] += A[i];
		}
	}
}

这是什么垃圾复杂度,用高维前缀和可得以下代码:

for (int j = 0; j < n; ++j) {
  for (int i = 0; i < (1 << n); ++i) {
    if((i >> j) & 1)  f[i] += f[i ^ (1 << j)];
  }
}
上一篇:LVS、Nginx、HAproxy有什么区别?工作中你怎么选择?


下一篇:go - 6.2 常用函数之字符串