介绍
一维前缀和 : $ s[i] = s[i - 1] + a[i] $
二维前缀和: $s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] $
当然也可以这么写:
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
a[i][j] += a[i - 1][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
a[i][j] += a[i][j - 1];
\(n\) 维前缀和, 我们可以做 \(n\) 次一维前缀和,差不多这个样子, 跟二维前缀和是类似的。
for(int i[1] = 1; i[1] <= n; i[1]++)
for(int i[2] = 1; i[2] <= n; i[2]++)
//...
a[i[1]][i[2]][i[3]] ... += a[i[1] - 1] ...;
for(int i[1] = 1; i[1] <= n; i[1]++)
for(int i[2] = 1; i[2] <= n; i[2]++)
//...
a[i[1]][i[2]][i[3]] ... += a[i[1]][i[2] - 1] ...;
...
例题
Ⅰ. P5495 Dirichlet 前缀和
根据唯一分解定理,将每个素数看成一维,然后相当于是子集和,用高维前缀和即可。状态压缩,可以仔细思考。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
#define uint unsigned int
uint seed;
inline uint getnext(){
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return seed;
}
bool _u;
int n;
uint b[N], ans;
bool ispri[N];
bool _v;
int main(){
cerr << abs(&_u - &_v) << " MB\n";
n = read(), seed = read();
for(int i = 1; i <= n; ++i) b[i] = getnext();
ispri[1] = 1;
for(int i = 1; i <= n; ++i){
if(!ispri[i])
for(int j = i; j <= n; j += i)
b[j] += b[j / i], ispri[j] = 1;
ans ^= b[i];
}
printf("%lld\n", ans);
return 0;
}
Ⅱ. [ARC100E] Or Plus Max
将题目转成对于每个 \(K\) 求 \(i | j = K\) 的最大值,然后就是求子集前缀最大值。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = (1 << 19) + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
bool _u;
int n;
ll ans;
struct node{
ll x, y;
node operator + (const node &p){
node z;
if(x > p.x) z.x = x, z.y = max(y, p.x);
else z.x = p.x, z.y = max(x, p.y);
return z;
}
}a[N];
bool _v;
int main(){
cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
n = read();
for(int i = 0; i < (1 << n); ++i) a[i].x = read(), a[i].y = -1e18;
for(int i = 0; i < n; ++i)
for(int j = 0; j < (1 << n); ++j)
if(j & (1 << i)) a[j] = a[j] + a[j ^ (1 << i)];
for(int i = 1; i < (1 << n); ++i){
ans = max(ans, a[i].x + a[i].y);
printf("%lld\n", ans);
}
return 0;
}