高维前缀和

主要内容

昨天（\(\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\) 的位置转移过来。

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

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

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

\(\texttt{code}\)

[ARC100C] Or Plus Max

直接维护最大和第二大的即可。

CF1208F Bits And Pieces

给定 \(n\) 个数的数组 \(d\)，找到 \(i<j<k\) 的 \(i,j,k\)，使得 \(d_i|(d_j \& d_k)\) 最大。

\(3\le n\le 10^6,0\le d_i\le 2\times 10^6\)。

考虑枚举每一位的 \(d_i\)，预处理可行的 \(\infty\oplus d_i\) 的子集的最大值（如果 \(d_i\) 这一位为 \(1\)，答案肯定有 \(1\)）。

但是好像假了，去看题解了。。

\(\bigstar\texttt{Hint-1}\)：我们可以考虑计算出 \(d_i\) 部分包含的最小的 \(i\) 和 \(d_j\&d_k\) 部分包含的最大的 \(j\)。

上边的可以用高维前缀和快速搞定，之后好像有不会了。。

\(\bigstar\texttt{Hint-2}\)：之后发现答案是从高到第决定的，只用维护第 \(i\) 位为 \(1\) 的最大值即可，从高位到低位判断这一位是否为 \(1\)，每次 \(\mathcal{O(n)}\) 验证，这样压缩到了 \(\mathcal{O(maxbit\times n)}\)。（验证部分代码如下）

inline bool check(int x)
{
	 for(int i=0;i<=MAX;i++)
	 	 if(dp[i].mini<dp[x^(x&i)].maxk) return true;
	 return false;
}

这道题都要看两个 hint，我太菜了呀！！

CF449D Jzzhu and Numbers

给定长为 \(n\) 的序列 \(\{a\}\)，计算从中选出一些数使得它们与起来等于 \(0\) 的方案数。

\(n,a_i\le 10^6\)。

有一个牛逼的状态：设 \(dp(s)\) 表示选出的数与起来为 \(s\) 的超集的方案数。

发现其实不用一开始就将方案数算出来，可以记下可以选择的数的数量，那么方案数直接就是 \(2^{dp(s)}\)。

那么计算出超集后再容斥就是答案了。

\(\bigstar\texttt{important}\)：记得减去空集的情况，因为每次计算都存在空集。

n=rd();
for(int i=1,x;i<=n;i++) x=rd(),dp[x]++;
for(int p=1;p<=20;p++)
	 for(int i=0;i<=1000000;i++)
	 	 if(!(i & (1<<(p-1))))
	 	 	 dp[i]+=dp[i+(1<<(p-1))];
for(int i=0;i<=1000000;i++)
{
	 if(__builtin_popcount(i)&1) ans=(ans-ksm(2,dp[i])+1+mod)%mod;
	 else ans=(ans+ksm(2,dp[i])-1)%mod;
}
printf("%d\n",ans%mod);