对于求高维前缀和，我的理解是在维度数乘总点数的复杂度下求前缀和。
首先可以先看看二维前缀和。
如果使用容斥的方法，像这样：
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
}
}
那么就是\(2^w\times n\times m\)。（\(w\)是维度）
假设说我们考虑先枚举维度。
在第一维，定义\(g_{i,j}=\sum_{k=1}^i a_{k,j}\)。
在第二维，定义\(f_{i,j}=\sum_{k=1}^j g_{i,k}\)。
则\(f\)数组就是\(a\)数组的二维前缀和数组。
照这个方法推广到\(w\)维就可以了。
但是高维要如何开数组？我的理解是用一种类似于哈希的方式，例如下面这道题：
洛谷P5495
给定长度为\(n\)的\(a\)数组，求长度为\(n\)的\(b\)数组。\(b_j=\sum_{i\mid j} a_i\)
这里我们把质数作为维度，例如$2,0,1,0,\dots $就是\(2\)这一维是\(2\)，\(5\)这一维是\(1\)，其他维都是\(0\)的状态，直接哈希成\(2^2\times 3^0\times 5^1\times \dots =20\)，有效状态一共\(n\)个，用高维前缀和直接解决。
代码：
#include<iostream>
#define uint unsigned int
using namespace std;
uint seed;
inline uint getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
int n;
bool prime[20000010];
int ss[2000010];
uint a[20000010];
void oula(){
for(int i=2;i<=n;i++){
if(prime[i]==0){
ss[++ss[0]]=i;
}
for(int j=1;j<=ss[0]&&ss[j]*i<=n;j++){
prime[i*ss[j]]=1;
if(i%ss[j]==0){
break;
}
}
}
}
int main(){
cin>>n>>seed;
oula();
for(int i=1;i<=n;i++){
a[i]=getnext();
}
for(int i=1;i<=ss[0];i++){
for(int j=1;j*ss[i]<=n;j++){
a[j*ss[i]]+=a[j];
}
}
uint ans=0;
for(int i=1;i<=n;i++){
ans=ans^a[i];
}
cout<<ans;
return 0;
}