P5495 Dirichlet前缀和
题意
给定长度为(n)的序列(a_i),求出长度为(n)的数列(b)满足
[b_k = sum_{i|k}a_i
]
对(b)取模(2^{32})
[1 leq n leq 2 imes10^7
]
分析
(a_i)贡献到(b_j)当且仅当任意(k),(alpha_k leq eta_k),其中(alpha ,eta)分别为(p_k)的指数
实际上就是对于质因子的高维前缀和,用处理高维前缀和的一般方法即可
[T(n) =sum_p lfloor frac{n}{p}
floor = O(nloglogn)
]
代码
for(int i = 0;i < cnt;i++){
for(int j = 1;j * prime[i] <= n;j++){
a[prime[i] * j] += a[j];
}
}
高维前缀和
对于二维可以使用不容斥的方法
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
a[i][j] += a[i][j - 1];
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
a[i][j] += a[i - 1][j];
三维类似
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
for(int k = 1;k <= p;k++)
a[i][j][k] += a[i - 1][j][k];
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
for(int k = 1;k <= p;k++)
a[i][j][k] += a[i][j - 1][k];
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
for(int k = 1;k <= p;k++)
a[i][j][k] += a[i][j][k - 1];
对于所有(0 leq i le 2^n - 1),求解(sum_{jsubset i} a_j)
若是枚举子集我们知道复杂度是(O(3^n)),若使用高维前缀和复杂度可以降为(O(n2^n))
代码
for(int j = 0;j < n;j++)
for(int i = 0;i < (1 << n);i++)
if((i >> j) & 1) f[i] += f[i ^ (1 << j)];
由于(i)是正序枚举,计算时(i xor (1 << j))还在上层,因此直接加即可