首页

只要是可逆的操作都有可能用到前缀和 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 阶差分后余项为常数。

      举个例子就是，给出一个多项式 f(x)=a0+a1x+a2x2+...+anxnf(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n， 有个数组 b[i]=f(i)b[i] = f(i)。

      对数组 bb​​ 不断作差分（最高次 + 1），最后总是前面一些余项后面全是 0 这样的：b1,b2,...,bi,0,0,...b_1, b_2, ..., b_i, 0, 0, ...​

    • 多做几次差分似乎也没什么问题因为一直是常数了，例 D 题

# 高阶前缀和

对 1,0,0...1, 0, 0... 一直作前缀和，找规律

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

第 kk 次前缀和的第 ii 个数其实是 C_{k + i}^

杨辉三角斜着看：

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...1, 0, 0... 求出的 kk 次前缀和其实还可以表示原数组每个位置对最终答案的贡献。

比如数组 1,2,3,4,61, 2, 3, 4, 6 求两次前缀和之后第五个位置上的数字：

​ 求两次前缀和后，原数组各位置对第五个数字的贡献分别是 5,4,3,2,15, 4, 3, 2, 1（1,0,0,0,01, 0, 0, 0, 0 两次前缀和是1,2,3,4,51, 2, 3, 4, 5）。

​ 按贡献来算，答案应该是 presum[2][6]=5∗1+4∗2+3∗3+2∗4+1∗6=36pre_sum[2][6] = 5 * 1 + 4 * 2 + 3 * 3 + 2 * 4 + 1 * 6 = 36，事实确实如此。

更神奇地，刚才的前缀和在 MOD=7MOD = 7 的模系下，长为 55 的数组（模数大于数组长度）可以发现循环节：

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 次前缀和，因为 (−2)mod7=5(-2)\space mod\space 7 = 5：

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（子集前缀和）

对于两个物品，开一个二维数组这样：\begin{bmatrix} 都不选 & 选1 \\ 选2 & 都选 \end

当然三个物品就开三维，例如： f[0][0][1]f[0][0][1] 表示只选第三个的权值，f[1][1][1]f[1][1][1] 表示三个都选的权值。

要查询某个选择方案的所有子集的权值和，对 ff 作前缀和即可。

采用状压表示集合，降低维数，毕竟写十几个括号实在太傻 * 了，例 B 题。

# 题目

比赛传送门

# F 前缀和思想

# 题意

初始有个 0~9 组成长度为 10 数组。给出一个长 nn​​ 的操作序列，每次给出 ai,bia_i, b_i​​ 表示交换下标为 ai,bia_i, b_i​​​​​ 的两个元素。

给出一个长 mm 的查询序列，每次给出 li,ril_i, r_i ，使用初始的数组，依次执行从 lil_i 到 rir_i​​​ 的操作序列，输出操作后的结果。

n,m≤1e5n, m \leq 1e5

# 思路

一个很神奇的前缀和，因为交换操作满足区间求和与区间作差（再换回去）的性质。

因为要操作的数组只有 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 矩阵表示

# 题意

两座相同高 N≤1e5N \leq 1e5 的塔，每座塔中，每层上下互通。除此之外，塔之间还有额外楼梯连接，更详细地，第 ii 层和第 i+1i + 1​​ 层之间的额外楼梯要么从左边塔连到右边，要么从右边塔连到左边。

如图：<img src="https://uploadfiles.nowcoder.com/images/20210810/310003_1628609130181/4A47A0DB6E60853DEDFCFDF08A5CA249"width="200px">（图炸了的话一定是牛客炸了（逃））

有 M≤1e5M \leq 1e5 次询问，每次询问从第 psps 座塔的第 ll 层到第 ptpt 座塔的第 rr​ 层的方案数（只能往上走）。

# 思路

先想从一楼往上爬的情况，dp[i][j]dp[i][j]​ 表示上到第 jj 座塔（假设 0 左边 1 右边）的 ii 层的方案数。

转移方程： dp[i][0]=dp[i−1][0]+dp[i−1][1]∗(ch[i]==′∖′)dp[i][0] = dp[i - 1][0] + dp[i - 1][1] * (ch[i] == '\setminus')​

想办法搞成矩阵的形式：

[从左边上到左边的方案数从左边上到右边的方案数从右边上到左边的方案数从右边上到右边的方案数]\begin{bmatrix} 从左边上到左边的方案数 & 从左边上到右边的方案数 \\ 从右边上到左边的方案数 & 从右边上到右边的方案数\end{bmatrix} \quad

比如这样的两种楼梯：

/:[1101]∖:[1011]/: \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \quad \setminus: \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \quad

多层合起来，这些矩阵作链乘即可，这样前缀和也就体现出来了。

设矩阵 f[i]f[i]​ 表示从第 11​ 层到第 ii​​​ 层的矩阵链乘结果，每次询问ans=inv(f[l])∗f[r]ans = inv(f[l]) * f[r] 。

其中 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 高阶前缀和

# 题意

有一个长 1e51e5 的 01 序列，每对 1 都会产生 dis(u,v)dis(u, v) 贡献，dis(u,v)dis(u, v) 表示两个点的距离，求总贡献。

# 思路

  • 直接递推：用后面的 1 去计算前面的 1 的贡献，递推时记录当前已经走过的 1 距离现在位置的距离和即可。
  • 前缀和：看前面 1 对后面的影响，做两次前缀和即可（一次求数量，一次求对后面的影响）。

# H 高阶前缀和

# 题意

1e51e5 长的序列，1e51e5 次询问，每次给出一个位置，从这个位置开始分别加 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 多项式

# 题意

有一个长 NN 的数组，先 MM 次修改，再 QQ 次询问，N,M,Q≤1e5N, M, Q \leq 1e5。

修改每次给出区间 [l,r][l, r] 和一个多项式：

f(x)=c0xk+c1xk−1+...+ck−1x1+ckf(x) = c_0x^k + c_1x^{k - 1} + ... + c_{k - 1}x^1 + c_k 对区间第一个数加上 f(1)f(1)，第二个数加 f(2)f(2) ... 第 ii 个数加上 f(i)f(i)。

查询每次给出区间查询总和。

# 思路

见上面构造。

因为最高只有五次，所以这里作六次差分（多做不怕）。

# 代码

#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 个物品，物品有权值。有 M≤1e5M \leq 1e5 次询问，每次给出一个物品集合 UU，求 UU 的所有子集价值和 / 超集价值和。

# 思路

正常来讲可以想到开个 20 维数组表示每个物品选择方案对应的权值，20 维的前缀和即可统计子集和的答案（超集就是后缀和）。

pre[x][x][1][x]...+=pre[x][x][0][x]...pre[x][x][1][x]... += pre[x][x][0][x]...， suf[x][x][0][x]...+=suf[x][x][1][x]...suf[x][x][0][x]... += suf[x][x][1][x]...

然后用状压即可。

# 代码

#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;
}
更新于