高维前缀和

主要内容

昨天（\(\texttt{2022.2.28}\)）打 ARC 的 D 题时，恍然发现我不会高维前缀和，匆匆来学一下。

比如二维前缀和 \(s_{i,j}\) 表示在一个二维平面上从 \((1,1)\) 到 \((i,j)\) 的所有点的权值之和，我们定义高维前缀和 \(s_{p_1,p_2,p_3,\cdots,p_n}\) 表示所有 \((q_1,q_2,q_3,\cdots,q_n)\) 并且满足 \(q_1\le p_1,q_2\le p_2,\cdots,q_n\le p_n\) 的所有点的权值之和。

如何求解高维前缀和呢？

举个例子，二维前缀和可以用一下代码来求：

for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 	 sum[i][j]+=sum[i-1][j];
for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 	 sum[i][j]+=sum[i][j-1];

类比一下，高维前缀和可以用如下方式求解：

// 假设前缀和是 q 进制的。 
int val[N]={1,q,q^2,q^3,...,q^{N-1}};
for(int opt=1;opt<=N;opt++)
	 for(int i=0;i<=MAX;i++)
	 	 if((i/val[opt])%q>=1)
	 	 	 sum[i]+=sum[i-val[opt]];

每一位都从这一位减一转移过来，其实高维前缀和也可以被想为一个 Dp 的过程，类似 Dp 的转移更好理解。

例题

CF772D Varying Kibibits

定义 \(f(S)\) 表示一个由若干个数组成的集合 \(S\) 中，返回值十进制每一位上的数为所有数中这一位的最小值。

给定 \(n\) 个数组成的集合 \(T\)，求：

\[\oplus_{x=0}^{999999}\left(x\times\left(\left(\sum_{S\subseteq T,S\not=\emptyset,f(S)=x}\left(\sum_{y\in S}y\right)^2\right)\bmod 1000000007\right)\right) \]

\(n\le 10^6,t_i< 10^6\)。

想到高维前缀和之后，难点就是怎样从当前这一位比它大 \(1\) 的位置转移过来。

主要问题是平方和的合并问题，发现其实就是这样一个过程：

\[a_1^2+a_2^2~\texttt{add}~b_1^2+b_2^2+b_3^2\Rightarrow(a_1+b_1)^2+(a_1+b_2)^2+(a_1+b_3)^2+(a_1+b_1)^2+(a_2+b_2)^2+(a_2+b_3)^2 \]

这样好办了，在每一位记下所有集合的 \(sum\) 的和、所有集合的 \(sum^2\) 的和与集合数量，直接转移即可。

发现这样求出来的是 \(f(x)\) 大于等于它的答案，所以最后还要进行一次差分。