【转载】思考题：前缀和差分思想延伸

FanBoys

2026-08-05 19:35:35

发布于：安徽

7阅读

0回复

0点赞

问题1.1 前缀和与差分：对于矩阵（二维数组） $(f_{i,j})_{n\times m}$ ，令 $\displaystyle g_{i,j}=\sum_{x=1}^i\sum_{y=1}^jf_{x,y}$ 。

一个众所周知的计算方法是按照递推式 $g_{i,j}=g_{i-1,j}+g_{i,j-1}-g_{i-1,j-1}+f_{i,j}$ 逐行列递推填表。

请你给出另一种已知 $f$ 求 $g$ 的算法，并给出一种已知 $g$ 求 $f$ 的算法。

问题1.2 能否把上述的 $2$ 维情形的问题推广到 $3$ 维？或者进一步推广到 $n$ 维？

问题2.1 考虑 $n$ 维，每一维都是 $0/1$ 的情形（此时坐标是一个 $01$ 向量，不妨看成集合），设 $\displaystyle g(S)=\sum_{T\subset S}f(T)$ ，若已知 $g$ ，能否反推出 $f(S)$ ？尝试证明你的结论。

问题2.2 类似的，考虑“后缀和”的情景， $\displaystyle g(S)=\sum_{T\subset S}f(T)$ ，已知 $g$ ，能否反推出 $f(S)$ ？

问题2.3 二项式反演：若 $f(S)$ 只与 $|S|$ 有关，令 $f(S)=f_{|S|}$ ，尝试重写上面的式子？

问题2.4 应用：一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$ ，求取法的方案数，答案模 $10^9+7$ 。[BZOJ2839 集合计数]

问题2.5 莫比乌斯函数与莫比乌斯反演：定义莫比乌斯函数 $\mu$ ：若 $n$ 含有平方因子， $\mu(n)=0$ ；否则 $\mu(n)=(−1)^{w(n)}$ ，其中 $w(n)$ 为 $n$ 的质因子个数，试证明： $\displaystyle\sum_{d|n}\mu(d)=[n=1]$ 。

问题3.1 与/或卷积：对于已知函数 $f_{0,\cdots,2n−1}$ ，设 $\displaystyle g_x=\sum_{y∣x=x}f_y,p_x=\sum_{y\&x=x}f_y$ ，回顾求高维前缀和的方法，能否用类似的思想求出 $g$ 数组和 $p$ 数组？

问题3.2 给出 $2^n$ 个数： $a_0,a_1,\cdots,a_{2^n−1}$ 。之后对于 $1\leq k\leq2^n−1$ ，求出： $\displaystyle\max_{⁡i|j\leq k}ai+aj$ [ARC100E]

答案

说实话，今天听得有点懵

问题1.1

设数组 $\displaystyle g'_{i,j}=g'_{i,j-1}+f_{i,j}$

然后设数组 $g''_{i,j}=g''_{i-1,j}+g'_{i,j}$

每一维单独进行计算

如何理解？

把一维理解成一个多项式，如果把一个数列 $\{a_n\}$ 抽象成一个多项式函数 $f(x)$ ，则变成 $f(x)=a_0x^0+a_1x^1+\cdots+a_nx^n$

如果变成 $\{a_n\}$ 的前缀和，那就是 $F(x)=a_0x^0+(a_0+a_1)x^1+(a_0+a_1+a_2)x^2+\cdots+(a_0+a_1+\cdots+a_n)x^n$

发现 $F(x)=f(x)\cdot(1+x+x^2+\cdots+x^n)$

同理，如果变成一个二维矩阵，可以理解为 $F(x,y)=\displaystyle(\sum_{0\leq i\leq n}\sum_{0\leq j\leq n}a_{i,j}x^iy^j)\cdot(1+x+y+xy+x^2+y^2+\cdots)=(\sum_{0\leq i,j\leq n}a_{i,j}x^iy^j)\cdot(\sum_{i=0}^nx^i)\cdot(\sum_{i=0}^ny^i)$

这样便是同一维一样的形式了，因而可以拆开一维一维求，不会影响。这就是生成函数

其中， $1+x+x^2+\cdots=\dfrac{1}{1-x}$ ，怎么证明？

令 $\displaystyle A=\sum_{i=0}^\infty x^i$ ，则 $\displaystyle xA=\sum_{i=1}^\infty x^i$

两式相减，得 $(x-1)A=1$ ，化简得 $A=\dfrac{1}{1-x}$

或者，考虑到因式分解的角度，给 $A$ 乘上一个 $1-x$ ，得到 $A(1-x)=1$ ，因而 $A=\dfrac{1}{1-x}$ ，可以理解为逆元操作，且逆元唯一

形式幂级数，这是 $\dfrac{1}{1-x}$ 的泰勒展开式，但是它具有收敛半径 $R=(-1,1)$ ，二者的值只在这个范围内相等
定义除法：若 $a\cdot b=c$ ，则 $a=\dfrac{c}{b}$

在形式幂级数上，可以理解为对于每一维的变量 $x_i$ 乘以了 $\dfrac{1}{1-x_i}$

差分同理，相当于对于每一维除以 $\dfrac{1}{1-x_i}$ ，即等价于乘以了 $1-x_i$

问题1.2

$\displaystyle g_{x_0,x_1,\cdots,x_{n-1}}=\sum_{S\subseteq\{0,\cdots,n-1\}}(-1)^{|S|}g_{\{x_i(x_i\in S),x_i-1(i\notin S)\}}+f_{x_0,x_1,\cdots,x_{n-1}}$

容斥原理计算高维前缀和差分，时间复杂度 $O(2^n)$

但是可以像问题1.1一样进行每一维单独的前缀和或差分

问题2.1

对于一个集合的幂集，也可以理解为一种前缀和，长为 $n$ 的集合相当于包含了一个 $n$ 维的坐标，第 $i$ 维是 $0$ 表示不选， $1$ 表示选，因而对于 $T\subset S$ 而言，代表 $T\prec S$

如果需要从前缀和反推，就相当于差分，完全可以理解为子集和的差分

代码形式：

//伪代码
for(int i=0;i<n;i++)
    for(int S=0;S<(1<<n);S++)
        if((S>>i)&1)
            a[S]-=a[S^(1<<i)];

某种程度上，这个叫做莫比乌斯变换（ $FMT$ ），本质就是高维前缀和或差分

问题2.2

后缀和与前缀和几乎相同，只不过枚举顺序倒过来而已

问题2.3

二项式反演，可以写成高维前缀和公式对应：

设 $U$ 为全集，则 $\{a_n\}\{b_n\}$ 两个数列的下标为 $U$ 的所有子集 $S$

则本质为 $\displaystyle b_S=\sum_{T\subseteq S}a_T,a_S=\sum_{T\subseteq S}(-1)^{|T|-|S|}b_T$

定义数列 $\{a'_n\}$ ，每一项运算规则为 $\displaystyle a_i'=\sum_{|S|=i}a_S=\sum_{j\leq i}(-1)^{j-i}b'_j$

同理定义 $\{b_n'\}$ ，其中 $\displaystyle b'_i=\sum_{|S|=i}b_S=\sum_{j\leq i}(-1)^{j-i}a'_j$

问题2.4

容斥原理

考虑让两个集合交集恰好为 $S$ ，其中 $|S|=K$ ，由于交集的限制较烦，考虑去掉“只包含 $S$ ”的限制

设 $a_S$ 表示交集恰好为 $S$ 方案数， $b_S$ 表示交集包含 $S$ 的方案数，因而 $\displaystyle b_S=\sum_{T\supseteq S}a_T$

因而 $\{b_n\}$ 有 $2^{2^{n-|S|}}-1$ 种。然后差分回去即可。

问题2.5

对于整数的整除关系，可以理解为高维坐标，如 $60=2^2\times3\times5$ ，因而理解为 $60=(2,1,1,0,\cdots)$ ，即把整数想象成无穷维的坐标中的点，第 $i$ 维的坐标代表有多少个质因子 $p_i$ ，其中 $p_i$ 表示第 $i$ 个质数。

定义 $c_{i\times j}=a_i\times b_j$ 表示无穷维的数列乘法，即高维情况下的下标加法，即 $c_{i\times j,k}=a_{i,k}+b_{j,k}$

前缀和 $S_i=\displaystyle\sum_{j\times k=i}a_j$ ，等价于枚举了 $i$ 的所有因数，即 $S_i=\displaystyle\sum_{j|i}a_j$

同理适用于差分。

对于一维差分，本身等价于乘以 $1-x$ ，如果写成无穷维的向量，就是 $(1,-1,0,0,\cdots)$ ，因而等价于对于每一维乘上这样一个向量的变换，即 $\displaystyle a=S\times\mu$ ，其中 $\mu$ 的每一维都是 $\vec{v}=(1,-1,0,0,\cdots)$ ， $\mu$ 就是莫比乌斯函数