带权高维前缀和
这个感觉很有用啊。对于一个\(n\)维，每一维长度为\(k\)的东西，并且每一维的贡献系数是固定的\(w_{y,x}\)表示一维中\(x\)对\(y\)的贡献系数。所以\(W_{Y,X}=\prod w_{y,x}\)。然后我们考虑怎么快速求这个。我们设\(f_{i,S,S'}\)表示当前处理到\(i\)维的时候，比他高的内些维都是\(S\)的这些数中，对低于\(i\)维的数是\(S'\)的所有贡献是多少。转移我们只需要把\(S\)的第\(i+1\)维删去，设为\(T\)，然后枚举第\(i+1\)维，设枚举了两个\(j,k\)，那么我们将\(f_{i,T,S'+j}\)和\(f_{i,T,S'+k}\),互相转移，为什么是\(S'\)和\(S'\)转移，其余数对\(S'\)贡献系数一样，所以对于转移，只需要管当前维的贡献系数就行了。我们发现设三维是冗余的，可以压成一维，像状压一样。这个做法还可以推广到从每一维长度维\(x\)变成长度为\(y\)
一个比较万能的模板
int len = pow(K, n);// 原来的长度for(int l1 = M, l2 = 1, cnt = 0; cnt < n; l1 *= M, l2 *= M, cnt ++) {len = len / K * M;// 变换完当前这一维的长度for(int i = 0; i < len; i += l1) {// 枚举变换后的起点int _i = i / M * K;// 原来的起点for(int y = 0, v = 0; y < M; y ++, v += l2) {for(int x = 0, u = 0; x < K; x ++, u += l2) { // 这个分别枚举第$i$维变换后和变化前分别是什么值for(int j = 0; j < l2; j ++) {g[i + v + j] += f[_i + u + j] * w[y][x];// 转移，使用临时数组}}}}for(int i = 0; i < len; i ++) f[i] = g[i], g[i] = 0;}
差分本质上是前缀和，一样
张量分解
在FWT领域有用。有了这个就不用想怎么找\(FWT\)变换了。思路是把贡献矩阵拆成若干个秩\(1\)矩阵，然后再进行正变换。这些尽可能少的秩1矩阵需要能够线性表示出贡献矩阵，然后逆变换就是高维带权前缀和。下面使用异或卷积来距离。
考虑单独的一维，贡献矩阵长这样：
其中左边是对\(C_0\)的贡献，右边是对\(C_1\)的贡献，每一个位置代表\(A_{0/1}*B_{0/1}\)对\(C_{0/1}\)的贡献。我们把他们拆成几个秩\(1\)的，发现这个两个就行了，分别是和和差。
可以线性表示是好说的。变成秩\(1\)有什么好处呢，我们可以把这两个矩阵表示成两个多项式相乘，\((A_0+A_1)*(B_0+B_1),(A_0-A_1)*(B_0-B_1)\)。所以我们正变换\(FWTA_0=A_0+A_1,FWTA_1=A_0-A_1\),\(B\)同理，然后我们对\(FWTA\)和\(FWTB\)进行点乘得到\(FWTC\)，逆变换就是\(C_0=(FWTC_0+FWTC_1)/2,C_1=(FWTC_0-FWTC_1)/2\)。这个就高维前缀和的领域了。那么我们就得到了\(C\)了。复杂度的话，一般是\(k^n*k\)，\(k\)是拆成多少个秩\(1\)矩阵，\(n\)是维数。