问题1.1 前缀和与差分：对于矩阵（二维数组）(fi,j)n×m(f_{i,j})_{n\times m}(fi,j )n×m ，令 gi,j=∑x=1i∑y=1jfx,y\displaystyle g_{i,j}=\sum_{x=1}^i\sum_{y=1}^jf_{x,y}gi,j =x=1∑i y=1∑j fx,y 。
一个众所周知的计算方法是按照递推式 gi,j=gi−1,j+gi,j−1−gi−1,j−1+fi,jg_{i,j}=g_{i-1,j}+g_{i,j-1}-g_{i-1,j-1}+f_{i,j}gi,j =gi−1,j +gi,j−1 −gi−1,j−1 +fi,j 逐行列递推填表。
请你给出另一种已知 fff 求 ggg 的算法，并给出一种已知 ggg 求 fff 的算法。
问题1.2 能否把上述的 222 维情形的问题推广到 333 维？或者进一步推广到 nnn 维？
问题2.1 考虑 nnn 维，每一维都是 0/10/10/1 的情形（此时坐标是一个 010101 向量，不妨看成集合），设 g(S)=∑T⊂Sf(T)\displaystyle g(S)=\sum_{T\subset S}f(T)g(S)=T⊂S∑ f(T)，若已知 ggg，能否反推出 f(S)f(S)f(S)？尝试证明你的结论。
问题2.2 类似的，考虑“后缀和”的情景，g(S)=∑T⊂Sf(T)\displaystyle g(S)=\sum_{T\subset S}f(T)g(S)=T⊂S∑ f(T)，已知 ggg，能否反推出 f(S)f(S)f(S)？
问题2.3 二项式反演：若 f(S)f(S)f(S) 只与 ∣S∣|S|∣S∣ 有关，令 f(S)=f∣S∣f(S)=f_{|S|}f(S)=f∣S∣ ，尝试重写上面的式子？
问题2.4 应用：一个有 NNN 个元素的集合有 2N2^N2N 个不同子集（包含空集），现在要在这 2N2^N2N 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 KKK，求取法的方案数，答案模 109+710^9+7109+7。[BZOJ2839 集合计数]
问题2.5 莫比乌斯函数与莫比乌斯反演：定义莫比乌斯函数 μ\muμ：若 nnn 含有平方因子，μ(n)=0\mu(n)=0μ(n)=0；否则 μ(n)=(−1)w(n)\mu(n)=(−1)^{w(n)}μ(n)=(−1)w(n)，其中 w(n)w(n)w(n) 为 nnn 的质因子个数，试证明：∑d∣nμ(d)=[n=1]\displaystyle\sum_{d|n}\mu(d)=[n=1]d∣n∑ μ(d)=[n=1]。
问题3.1 与/或卷积：对于已知函数 f0,⋯ ,2n−1f_{0,\cdots,2n−1}f0,⋯,2n−1 ，设 gx=∑y∣x=xfy,px=∑y&x=xfy\displaystyle g_x=\sum_{y∣x=x}f_y,p_x=\sum_{y\&x=x}f_ygx =y∣x=x∑ fy ,px =y&x=x∑ fy ，回顾求高维前缀和的方法，能否用类似的思想求出 ggg 数组和 ppp 数组？
问题3.2 给出 2n2^n2n 个数：a0,a1,⋯ ,a2n−1a_0,a_1,\cdots,a_{2^n−1}a0 ,a1 ,⋯,a2n−1 。之后对于 1≤k≤2n−11\leq k\leq2^n−11≤k≤2n−1，求出：maxi∣j≤kai+aj\displaystyle\max_{i|j\leq k}ai+aji∣j≤kmax ai+aj [ARC100E]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
答案
说实话，今天听得有点懵
问题1.1
设数组 gi,j′=gi,j−1′+fi,j\displaystyle g'_{i,j}=g'_{i,j-1}+f_{i,j}gi,j′ =gi,j−1′ +fi,j
然后设数组 gi,j′′=gi−1,j′′+gi,j′g''_{i,j}=g''_{i-1,j}+g'_{i,j}gi,j′′ =gi−1,j′′ +gi,j′
每一维单独进行计算
如何理解？
把一维理解成一个多项式，如果把一个数列 {an}\{a_n\}{an } 抽象成一个多项式函数 f(x)f(x)f(x)，则变成 f(x)=a0x0+a1x1+⋯+anxnf(x)=a_0x^0+a_1x^1+\cdots+a_nx^nf(x)=a0 x0+a1 x1+⋯+an xn
如果变成 {an}\{a_n\}{an } 的前缀和，那就是 F(x)=a0x0+(a0+a1)x1+(a0+a1+a2)x2+⋯+(a0+a1+⋯+an)xnF(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^nF(x)=a0 x0+(a0 +a1 )x1+(a0 +a1 +a2 )x2+⋯+(a0 +a1 +⋯+an )xn
发现 F(x)=f(x)⋅(1+x+x2+⋯+xn)F(x)=f(x)\cdot(1+x+x^2+\cdots+x^n)F(x)=f(x)⋅(1+x+x2+⋯+xn)
同理，如果变成一个二维矩阵，可以理解为 F(x,y)=(∑0≤i≤n∑0≤j≤nai,jxiyj)⋅(1+x+y+xy+x2+y2+⋯ )=(∑0≤i,j≤nai,jxiyj)⋅(∑i=0nxi)⋅(∑i=0nyi)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)F(x,y)=(0≤i≤n∑ 0≤j≤n∑ ai,j xiyj)⋅(1+x+y+xy+x2+y2+⋯)=(0≤i,j≤n∑ ai,j xiyj)⋅(i=0∑n xi)⋅(i=0∑n yi)
这样便是同一维一样的形式了，因而可以拆开一维一维求，不会影响。这就是生成函数
其中，1+x+x2+⋯=11−x1+x+x^2+\cdots=\dfrac{1}{1-x}1+x+x2+⋯=1−x1 ，怎么证明？
令 A=∑i=0∞xi\displaystyle A=\sum_{i=0}^\infty x^iA=i=0∑∞ xi，则 xA=∑i=1∞xi\displaystyle xA=\sum_{i=1}^\infty x^ixA=i=1∑∞ xi
两式相减，得 (x−1)A=1(x-1)A=1(x−1)A=1，化简得 A=11−xA=\dfrac{1}{1-x}A=1−x1
或者，考虑到因式分解的角度，给 AAA 乘上一个 1−x1-x1−x，得到 A(1−x)=1A(1-x)=1A(1−x)=1，因而 A=11−xA=\dfrac{1}{1-x}A=1−x1 ，可以理解为逆元操作，且逆元唯一
* 形式幂级数，这是 11−x\dfrac{1}{1-x}1−x1 的泰勒展开式，但是它具有收敛半径 R=(−1,1)R=(-1,1)R=(−1,1)，二者的值只在这个范围内相等
* 定义除法：若 a⋅b=ca\cdot b=ca⋅b=c，则 a=cba=\dfrac{c}{b}a=bc
在形式幂级数上，可以理解为对于每一维的变量 xix_ixi 乘以了 11−xi\dfrac{1}{1-x_i}1−xi 1
差分同理，相当于对于每一维除以 11−xi\dfrac{1}{1-x_i}1−xi 1 ，即等价于乘以了 1−xi1-x_i1−xi
问题1.2
gx0,x1,⋯ ,xn−1=∑S⊆{0,⋯ ,n−1}(−1)∣S∣g{xi(xi∈S),xi−1(i∉S)}+fx0,x1,⋯ ,xn−1\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}}gx0 ,x1 ,⋯,xn−1 =S⊆{0,⋯,n−1}∑ (−1)∣S∣g{xi (xi ∈S),xi −1(i∈/S)} +fx0 ,x1 ,⋯,xn−1
容斥原理计算高维前缀和差分，时间复杂度 O(2n)O(2^n)O(2n)
但是可以像问题1.1一样进行每一维单独的前缀和或差分
问题2.1
对于一个集合的幂集，也可以理解为一种前缀和，长为 nnn 的集合相当于包含了一个 nnn 维的坐标，第 iii 维是 000 表示不选，111 表示选，因而对于 T⊂ST\subset ST⊂S 而言，代表 T≺ST\prec ST≺S
如果需要从前缀和反推，就相当于差分，完全可以理解为子集和的差分
代码形式：
某种程度上，这个叫做莫比乌斯变换（FMTFMTFMT），本质就是高维前缀和或差分
问题2.2
后缀和与前缀和几乎相同，只不过枚举顺序倒过来而已
问题2.3
二项式反演，可以写成高维前缀和公式对应：
设 UUU 为全集，则 {an}{bn}\{a_n\}\{b_n\}{an }{bn } 两个数列的下标为 UUU 的所有子集 SSS
则本质为 bS=∑T⊆SaT,aS=∑T⊆S(−1)∣T∣−∣S∣bT\displaystyle b_S=\sum_{T\subseteq S}a_T,a_S=\sum_{T\subseteq S}(-1)^{|T|-|S|}b_TbS =T⊆S∑ aT ,aS =T⊆S∑ (−1)∣T∣−∣S∣bT
定义数列 {an′}\{a'_n\}{an′ }，每一项运算规则为 ai′=∑∣S∣=iaS=∑j≤i(−1)j−ibj′\displaystyle a_i'=\sum_{|S|=i}a_S=\sum_{j\leq i}(-1)^{j-i}b'_jai′ =∣S∣=i∑ aS =j≤i∑ (−1)j−ibj′
同理定义 {bn′}\{b_n'\}{bn′ }，其中 bi′=∑∣S∣=ibS=∑j≤i(−1)j−iaj′\displaystyle b'_i=\sum_{|S|=i}b_S=\sum_{j\leq i}(-1)^{j-i}a'_jbi′ =∣S∣=i∑ bS =j≤i∑ (−1)j−iaj′
问题2.4
容斥原理
考虑让两个集合交集恰好为 SSS，其中 ∣S∣=K|S|=K∣S∣=K，由于交集的限制较烦，考虑去掉“只包含 SSS”的限制
设 aSa_SaS 表示交集恰好为 SSS 方案数，bSb_SbS 表示交集包含 SSS 的方案数，因而 bS=∑T⊇SaT\displaystyle b_S=\sum_{T\supseteq S}a_TbS =T⊇S∑ aT
因而 {bn}\{b_n\}{bn } 有 22n−∣S∣−12^{2^{n-|S|}}-122n−∣S∣−1 种。然后差分回去即可。
问题2.5
对于整数的整除关系，可以理解为高维坐标，如 60=22×3×560=2^2\times3\times560=22×3×5，因而理解为 60=(2,1,1,0,⋯ )60=(2,1,1,0,\cdots)60=(2,1,1,0,⋯)，即把整数想象成无穷维的坐标中的点，第 iii 维的坐标代表有多少个质因子 pip_ipi ，其中 pip_ipi 表示第 iii 个质数。
定义 ci×j=ai×bjc_{i\times j}=a_i\times b_jci×j =ai ×bj 表示无穷维的数列乘法，即高维情况下的下标加法，即 ci×j,k=ai,k+bj,kc_{i\times j,k}=a_{i,k}+b_{j,k}ci×j,k =ai,k +bj,k
前缀和 Si=∑j×k=iajS_i=\displaystyle\sum_{j\times k=i}a_jSi =j×k=i∑ aj ，等价于枚举了 iii 的所有因数，即 Si=∑j∣iajS_i=\displaystyle\sum_{j|i}a_jSi =j∣i∑ aj
同理适用于差分。
对于一维差分，本身等价于乘以 1−x1-x1−x，如果写成无穷维的向量，就是 (1,−1,0,0,⋯ )(1,-1,0,0,\cdots)(1,−1,0,0,⋯)，因而等价于对于每一维乘上这样一个向量的变换，即 a=S×μ\displaystyle a=S\times\mua=S×μ，其中 μ\muμ 的每一维都是 v⃗=(1,−1,0,0,⋯ )\vec{v}=(1,-1,0,0,\cdots)v=(1,−1,0,0,⋯)，μ\muμ 就是莫比乌斯函数
莫比乌斯函数 μ(x)=∏v(ci)\displaystyle\mu(x)=\prod v(c_i)μ(x)=∏v(ci )，其中 x=p1c1p2c2⋯x=p_1^{c_1}p_2^{c_2}\cdotsx=p1c1 p2c2 ⋯，p1,p2,⋯p_1,p_2,\cdotsp1 ,p2 ,⋯ 均为质数
问题3.1
如果把按位与和按位或理解为高维坐标的话，按位与运算相当于每一维取 min\minmin，按位或运算相当于每一维取 max\maxmax
ggg 相当于枚举子集，即高维前缀和；ppp 就相当于高维后缀和。
进一步的，如果计算 hx∣y=fx×gyh_{x|y}=f_x\times g_yhx∣y =fx ×gy ，定义 Fx=∑t⊆xft\displaystyle F_x=\sum_{t\subseteq x}f_tFx =t⊆x∑ ft ，GGG 和 HHH 同理，则有 Hx=Fx×GxH_x=F_x\times G_xHx =Fx ×Gx ，即快速莫比乌斯变换
问题3.2
对 aaa 做一个下标子集和，若 iii 是 SSS 的子集，jjj 也是 SSS 的子集，那么 i∣ji|ji∣j 恰好就是 SSS 的所有子集的枚举，因而可以利用前缀和容斥做。
但是，i∣j⊆ki|j\subseteq ki∣j⊆k 有点问题，无法保证 i∣j≤ki|j\leq ki∣j≤k，不过幸好 max\maxmax 可以重复贡献
