前缀和专题
只要是可逆的操作都有可能用到前缀和qwq
多阶前缀和的一些构造
等差 1 2 3 4... ：1 0 0...前缀和再前缀和（1 1 1... -> 1 2 3...）
平方 1 4 9 16... ： 1 1 0 0... 三次前缀和（1 2 2... -> 1 3 5 7 9... -> 1 4 9 16...）
- 对应位置分别这样加的话，可以作三次差分之后O(1)修改，例H题。
多项式：
最高n次的n阶多项式做 n + 1 阶差分后余项为常数。
举个例子就是，给出一个多项式
， 有个数组
。
对数组
不断作差分（最高次+1），最后总是前面一些余项后面全是0这样的：
多做几次差分似乎也没什么问题因为一直是常数了，例D题
高阶前缀和
对 一直作前缀和，找规律
1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 1 4 10 20 35 56 84 120 165 220 1 5 15 35 70 126 210 330 495 715 1 6 21 56 126 252 462 792 1287 2002
第 次前缀和的第
个数其实是
杨辉三角斜着看：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
这里的 求出的
次前缀和其实还可以表示原数组每个位置对最终答案的贡献。
比如数组 求两次前缀和之后第五个位置上的数字：
求两次前缀和后，原数组各位置对第五个数字的贡献分别是 （
两次前缀和是
）。
按贡献来算，答案应该是 ，事实确实如此。
更神奇地，刚才的前缀和在 的模系下，长为
的数组（模数大于数组长度）可以发现循环节：
1 0 0 0 0 1 1 1 1 1 1 2 3 4 5 1 3 6 3 1 1 4 3 6 0 1 5 1 0 0 1 6 0 0 0 1 0 0 0 0 1 1 1 1 1 1 2 3 4 5 1 3 6 3 1 1 4 3 6 0 1 5 1 0 0 1 6 0 0 0 1 0 0 0 0 1 1 1 1 1
再神奇一些，比如两次差分跟五次前缀和一样，也就是-2次前缀和，因为 ：
1 6 0 0 0 1 5 1 0 0 1 4 3 6 0 1 3 6 3 1 1 2 3 4 5 两次前缀和 1 1 1 1 1 一次前缀和 1 0 0 0 0 原数组 1 6 0 0 0 一次差分 1 5 1 0 0 两次差分 1 4 3 6 0 1 3 6 3 1 1 2 3 4 5 1 1 1 1 1 1 0 0 0 0
这些奇奇怪怪的规律或许有用，口胡一下，反正也不会算卷积qwq
高维前缀和
SOSDP: Sum Over Subsets（子集前缀和）
对于两个物品，开一个二维数组这样：
当然三个物品就开三维，例如： 表示只选第三个的权值，
表示三个都选的权值。
要查询某个选择方案的所有子集的权值和，对 作前缀和即可。
采用状压表示集合，降低维数，毕竟写十几个括号实在太傻*了，例B题。
题目
F
题意
初始有个0~9组成长度为10数组。给出一个长 的操作序列，每次给出
表示交换下标为
的两个元素。
给出一个长 的查询序列，每次给出
，使用初始的数组，依次执行从
到
的操作序列，输出操作后的结果。
思路
一个很神奇的前缀和，因为交换操作满足区间求和与区间作差（再换回去）的性质。
因为要操作的数组只有10个元素，直接O(n)
代码
#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 1e5 + 233;
int n, T;
int sum[MAXN][10]; //第i次操作后十个球的排列
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &T);
int a, b;
rep (i, 0, 9)
sum[0][i] = i;
rep (i, 1, n)
{
scanf("%d%d", &a, &b);
rep (j, 0, 9)
sum[i][j] = sum[i - 1][j];
swap(sum[i][a], sum[i][b]);
}
int l, r;
while (T--)
{
scanf("%d%d", &l, &r);
int tmpmap[10];
rep (i, 0, 9)
tmpmap[sum[l - 1][i]] = i; //交换可逆，tmpmap确定一个交换方案
rep (i, 0, 9)
printf("%d ", tmpmap[sum[r][i]]);
printf("\n");
}
return 0;
} E
题意
两座相同高 的塔，每座塔中，每层上下互通。除此之外，塔之间还有额外楼梯连接，更详细地，第
层和第
层之间的额外楼梯要么从左边塔连到右边，要么从右边塔连到左边。
如图：
有 次询问，每次询问从第
座塔的第
层到第
座塔的第
层的方案数（只能往上走）。
思路
先想从一楼往上爬的情况， 表示上到第
座塔（假设0左边1右边）的
层的方案数。
转移方程：
想办法搞成矩阵的形式：
$$
多层合起来，这些矩阵作链乘即可，这样前缀和也就体现出来了。
设矩阵 表示从第
层到第
层的矩阵链乘结果，每次询问
。
其中inv表示逆矩阵，记得链乘顺序不能交换。
代码
因为逆矩阵写得太丑所以直接省掉了qwq
#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 233;
const ll MOD = 1e9 + 7;
int n, T;
inline ll inv(ll num) {
ll ans = 1, b = MOD - 2;
num = (num % MOD + MOD) % MOD;
for (; b; b >>= 1ll) {
if (b & 1ll) ans = (num * ans) % MOD;
num = (num * num) % MOD;
}
return ans;
}
struct matrix
{
ll val[2][2];
matrix() = default;
matrix(int v00, int v01, int v10, int v11)
{
val[0][0] = v00;
val[0][1] = v01;
val[1][0] = v10;
val[1][1] = v11;
}
matrix operator * (matrix b)
{
return matrix(
(val[0][0] * b.val[0][0] % MOD + val[0][1] * b.val[1][0] % MOD) % MOD,
(val[0][0] * b.val[0][1] % MOD + val[0][1] * b.val[1][1] % MOD) % MOD,
(val[1][0] * b.val[0][0] % MOD + val[1][1] * b.val[1][0] % MOD) % MOD,
(val[1][0] * b.val[0][1] % MOD + val[1][1] * b.val[1][1] % MOD) % MOD
);
}
inline matrix inv(){} //省略了32行qwq
} f[MAXN];
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d ", &n, &T);
char ch;
f[1] = matrix(1, 0, 0, 1); //并没有斜着的楼梯从地面上到第一层
rep (i, 2, n)
{
scanf("%c", &ch);
f[i].val[0][0] = f[i].val[1][1] = 1;
if (ch == '/')
f[i].val[0][1] = 1;
else
f[i].val[1][0] = 1;
f[i] = f[i - 1] * f[i];
}
int l, r, s, t;
while (T--)
{
scanf("%d%d%d%d", &l, &r, &s, &t);
matrix invmat = f[l].inv(); //"上到"，所以这里写法是l不是l-1了问题不大qwq
matrix tmp = invmat * f[r];
printf("%d\n", tmp.val[s][t]);
}
return 0;
} G
题意
有一个长 的01序列，每对1都会产生
贡献，
表示两个点的距离，求总贡献。
思路
- 直接递推：用后面的1去计算前面的1的贡献，递推时记录当前已经走过的1距离现在位置的距离和即可。
- 前缀和：看前面1对后面的影响，做两次前缀和即可（一次求数量，一次求对后面的影响）。
H
题意
长的序列，
次询问，每次给出一个位置，从这个位置开始分别加 1 4 9 16... 输出最后序列。
思路
这样构造：对应位置分别加1 4 9 16... ： 1 1 0 0... 三次前缀和（1 2 2... -> 1 3 5 7 9... -> 1 4 9 16...）
也就是做三次差分之后可以O(1)修改，再前缀和还原回去。
D
题意
有一个长 的数组，先
次修改，再
次询问，
。
修改每次给出区间 和一个多项式：
对区间第一个数加上
，第二个数加
...第
个数加上
。
查询每次给出区间查询总和。
思路
见上面构造。
因为最高只有五次，所以这里作六次差分（多做不怕）。
代码
#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 233;
const ll MOD = 1e9 + 7;
int n, M, Q;
ll a[MAXN], c[11], add[11], sub[11]; //add和sub分别是修改值差分后的常数组，表示差分操作中的前加后减。
void dif(ll a[], int len, int tim) //差分
{
while (tim--)
per (i, len, 1)
a[i] = (a[i] - a[i - 1] + MOD) % MOD;
}
void pre(ll a[], int len, int tim) //前缀和
{
while (tim--)
rep (i, 1, len)
a[i] = (a[i - 1] + a[i]) % MOD;
}
ll f(ll x, ll c[], int k) //计算f(x)值
{
ll ans = 0, base = 1;
per (i, k, 0)
{
ans = (ans + c[i] * base % MOD) % MOD;
base = base * x % MOD;
}
return ans;
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d%d", &n, &M, &Q);
rep (i, 1, n)
scanf("%lld", &a[i]);
dif(a, n, 6); //原数组差分6次
while (M--)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
rep (i, 0, k)
scanf("%lld", &c[i]);
//6次差分之后肯定不超过10个常数，不知道为啥，zngg说的(
//k次多项式的k+1阶差分余项只有看k+1项，理论上讲7就够了
rep (i, 1, 10)
{
add[i] = f(i, c, k);
sub[i] = f(i + r - l + 1, c, k);
}
dif(add, 10, 6); //操作数组差分六次
dif(sub, 10, 6);
rep (i, 1, 10) //进行修改，跟普通差分的修改一样只不过改成了常数组
{
a[l + i - 1] = (a[l + i - 1] + add[i]) % MOD;
a[r + i] = (a[r + i] - sub[i] + MOD) % MOD;
}
}
pre(a, n, 7); //还原6次，用于区间查询1次
while (Q--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", (a[r] - a[l - 1] + MOD) % MOD);
}
return 0;
} B
题意
有20个物品，物品有权值。有 次询问，每次给出一个物品集合
，求
的所有子集价值和/超集价值和。
思路
正常来讲可以想到开个20维数组表示每个物品选择方案对应的权值，20维的前缀和即可统计子集和的答案（超集就是后缀和）。
，
然后用状压即可。
代码
#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
using ll = long long;
const int MAXN = 20;
int n, T, maxbit; //maxbit表示状压之后最大的数字
ll a[MAXN], pre[1 << MAXN], suf[1 << MAXN];
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &T);
maxbit = (1 << n) - 1; //n位全是1的情况就是maxbit
rep (i, 0, n - 1)
scanf("%lld", &a[i]);
rep (i, 0, maxbit) //这里计算每个集合的权值(按题目要求而已)
{
ll tmpsum = 0;
rep (j, 0, n - 1)
if (i & (1 << j))
tmpsum ^= a[j];
pre[i] = suf[i] = tmpsum;
}
rep (i, 0, n - 1) //这里对每一维(即每个物品)分别求前缀和和后缀和
rep (j, 0, maxbit)
if (j & (1 << i))
pre[j] += pre[j ^ (1 << i)];
else
suf[j] += suf[j ^ (1 << i)];
while (T--)
{
int k, u = 0, pi;
scanf("%d", &k);
rep (i, 1, k)
{
scanf("%d", &pi);
u ^= (1 << (pi - 1)); //计算要查询的状态
}
printf("%lld %lld\n", pre[u], suf[u]);
}
return 0;
} 
查看6道真题和解析
投递字节跳动等公司7个岗位 >