高维前缀和

对于求高维前缀和，我的理解是在维度数乘总点数的复杂度下求前缀和。
首先可以先看看二维前缀和。
如果使用容斥的方法，像这样：

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;
}