1 前缀和与差分

导图
在这里插入图片描述


题目链接

智乃酱的子集与超集（SOSdp）

题意描述
​​ (​)个物品做为一个全集，第​个物品价值​，一个集合的价值为集合物品价值的异或和。​次询问，询问选择其中一些物品 { ​ ​}，它的所有子集价值之和 与 所有全集价值之和。

分析
前置芝士：高维前缀和
以二维为例理解计算方法：
第一步：

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum[i][j] = a[i][j];


就是单个点，相当于是0维前缀和

第二步：

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum[i][j] += sum[i - 1][j]

在这里插入图片描述
​​此时存了当前列的前缀和，即计算了1维前缀和

第三步：

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum[i][j] += sum[i][j - 1];

在这里插入图片描述

此时已经完成了2维前缀和的计算

因此可以推广一下这个做法，**求​维前缀和**，则从0维开始，每次对一个维度做一次前缀和，相当于起到了一个降维的作用，做了 ​ 次就可以求解出 ​ 维前缀和了。时间复杂度 ​

代码:

for (i : 空间元素)
    sum[i] = a[i];
for (i = 1; i <= k; i++)
    for (j : 空间元素)
        sum[j] += sum[k] [k的第i维 + 1 = j]

下面就是这题的具体思路了

高维前缀和的一个应用就是 （​），常与 结合使用。

在这题中，可以构建一个维空间，每一维长度都是，取值和​。每个物品都是一个维度，不选取，选了取。

因此维空间中的某一个点都表示一种物品集合，它的维前缀和就是它所有子集的价值之和，它的​维后缀和就是它所有超集的价值之和。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 30, S = 1 << 20;

int n, m, k;
ll a[N], presum[S], sufsum[S];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for (int i = 0; i < 1 << n; i++)
    {
        ll sum = 0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum ^= a[j];
        presum[i] = sum;
        sufsum[i] = sum;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 1 << n; j++)
            if (j & (1 << i)) presum[j] += presum[j ^ (1 << i)];
            else sufsum[j] += sufsum[j ^ (1 << i)];
    while (m--)
    {
        scanf("%d", &k);
        int q = 0;
        for (int i = 1; i <= k; i++)
        {
            int x;
            scanf("%d", &x);
            q |= 1 << x - 1;
        }
        printf("%lld %lld\n", presum[q], sufsum[q]);
    }
    return 0;
}

智乃酱的前缀和与差分（高阶前缀和）

题意描述
给长度是 的序列 ，求其 次前缀和，前缀和对 取模。

分析
如果序列做前缀和取的模数大与序列的长度，那么前缀和序列会以长度为模数的循环节循环出现。
这里由于模数大于序列长度，可以对负数的 (差分) 取模后转化为前缀和。

NTT卷积​求解：

首先对于序列 [] 列出做前缀和后的表格：

序号 0 1 2 3 4
原序列
一次前缀和
二次前缀和
三次前缀和
…

只保留其中​的系数得到：

序号 0 1 2 3 4
原序列 1 0 0 0 0
一次前缀和 1 1 1 1 1
二次前缀和 1 2 3 4 5
三次前缀和 1 3 6 10 15
…

首先容易得到一个递推式，第​次前缀和序号​的系数 ​

这个递推式是有实际含义的：在网格中从（1，0）出发，每次只能向下或向右移动一格，求移动到（k，i）的方案数。

答案就是 ​​

因此可以通过组合数递推的方式 ​​ 得到做 ​​ 次前缀和后 ​​ 的系数序列 ​​​

如果把 ​ 都考虑进来，做 ​ 次前缀和的结果像下面这样计算（以序列长度为3，做3次前缀和为例）：

这时已经可以意识到 ​​​​​序列 ​​​​​ 次 前缀和的结果就是 ​​​​​序列 与做​​​​​次前缀和的 系数序列​​​​​​ 的卷积。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 100010;
const int G = 3;

int a[N << 2], b[N << 2], rev[N << 2];
int inv[N];

void getb(ll k, int n)
{
    k = (k % mod + mod) % mod;
    b[0] = 1;
    for (int i = 1; i < n; i++)
        b[i] = (ll)b[i - 1] * (i + k - 1) % mod * inv[i] % mod;
}

int qmi(int a, int b, int p)
{
    int ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1) ans = (ll)ans * a % p;
        a = (ll)a * a % p;
    }
    return ans;
}

void ntt(int a[], int tot, int sgn, int p)
{
    for (int i = 0; i < tot; i++)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    int g = sgn == 1 ? G : qmi(G, p - 2, p);
    for (int mid = 1, t = 1; mid < tot; mid <<= 1, t++)
    {
        int wn = qmi(g, (p - 1) >> t, p);
        for (int i = 0; i < tot; i += mid << 1)
        {
            int w = 1;
            for (int j = 0; j < mid; j++, w = (ll)w * wn % p)
            {
                int x = a[i + j], y = (ll)w * a[i + mid + j] % p;
                a[i + j] = (x + y) % p;
                a[i + mid + j] = ((x - y) % p + p) % p;
            }
        }
    }
    if (sgn == -1)
    {
        int invtot = qmi(tot, p - 2, p);
        for (int i = 0; i < tot; i++)
            a[i] = (ll)a[i] * invtot % p;
    }
}

int main()
{
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;

    int n; ll k;
    scanf("%d%lld", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    getb(k, n);

    n--;
    int tot = 1, bit = 0;
    while (tot < n + n + 1) tot <<= 1, ++bit;
    for (int i = 0; i < tot; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

    ntt(a, tot, 1, mod), ntt(b, tot, 1, mod);
    for (int i = 0; i < tot; i++) a[i] = (ll)a[i] * b[i] % mod;
    ntt(a, tot, -1, mod);
    n++;

    for (int i = 0; i < n; i++)
        printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    return 0;
}

智乃酱的静态数组维护问题多项式（多项式前缀和）

题意描述：
对于一个序列，每次选择 [l, r] 加上一个多项式
（即 ）
最后询问 [l, r] 的元素之和。

分析：
数学定理：最高次项为 n 次的 n 阶多项式做 n + 1 阶差分后余项为常数（常数0）。
可以将原数组做 次差分，然后对差分数组做有限次修改，最后前缀和求回来即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define Min(a,b,c)  min(a,min(b,c))
#define Max(a,b,c)  max(a,max(b,c))

typedef long long ll;
typedef unsigned long long ull;

const double pi = 3.141592653589793;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;

const int N = 100010;
const ll mod = 1000000007;

ll a[N], p[10], f1[10], f2[10];

void S(ll a[], int n, int t)
{
    while (t--)
    {
        for (int i = 1; i <= n; i++)
            a[i] = (a[i - 1] + a[i]) % mod;
    }
}

void D(ll a[], int n, int t)
{
    while (t--)
    {
        for (int i = n; i >= 1; i--)
            a[i] = (a[i] - a[i - 1]) % mod;
    }
}

ll f(ll x, ll p[], int k)
{
    ll base = 1, ans = 0;
    for (int i = 0; i <= k; i++)
    {
        ans = (ans + p[i] * base % mod) % mod;
        base = base * x % mod;
    }
    return ans;
}

int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    D(a, n, 6);
    while (m--)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        for (int i = k; i >= 0; i--) scanf("%lld", &p[i]);
        for (int i = 1; i <= 6; i++) 
        {
            f1[i] = f(i, p, k);
            f2[i] = (mod - f(i + r - l + 1, p, k)) % mod;
        } 
        D(f1, 6, 6);
        D(f2, 6, 6);
        for (int i = 1; i <= 6; i++)
        {
            a[l + i - 1] = (a[l + i - 1] + f1[i]) % mod;
            a[r + i] = (a[r + i] + f2[i]) % mod;
        }
    }
    S(a, n, 7);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", ((a[r] - a[l - 1]) % mod + mod) % mod);
    }
    return 0;
}

智乃酱的双塔问题（DP、前缀和、矩阵）

题意描述
左右有两个高度为n个塔，对于每个塔可以从下一层直接到上一层。对于每层(不包括顶层)额外有一个楼梯要么是从左塔上到右塔，要么是从右塔往上走一层到左塔。
每次询问从左边或右边塔的第 i 层走到左边或右边的第 j 层的方案数（i < j）。

分析
首先想到，表示左边的塔从第一层走到第层的方案数，表示右边的塔从第一层走到第层的方案数。那么就有转移方程：
$$
因此从某一层到某一层的方案数，就是这一段矩阵的连乘积。
因此可以预处理出矩阵的前缀和，因为两种可能出现的矩阵都是可逆矩阵，最后为了消除左半部分影响，乘一下左半部分矩阵的逆即可。（要注意是左乘）

代码

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define Min(a,b,c)  min(a,min(b,c))
#define Max(a,b,c)  max(a,max(b,c))

typedef long long ll;
typedef unsigned long long ull;

const double pi = 3.141592653589793;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;

const int N = 100010;
const ll mod = 1000000007;

struct mat
{
    ll a[2][2];
    mat() {memset(a, 0, sizeof(a));}
    mat(int a1, int a2, int a3, int a4)
    {
        a[0][0] = a1;
        a[0][1] = a2;
        a[1][0] = a3;
        a[1][1] = a4;
    }
};

int n, m;
char s[N];
mat sum[N], A(1, 1, 0, 1), B(1, 0, 1, 1);

ll qmi(ll a, ll b)
{
    ll ans = 1;
    for ( ; b; b >>= 1)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

ll inv(ll x)
{
    return qmi(x, mod - 2);
}

void mul(ll a[][2], ll b[][2])
{
    ll c[2][2];
    memset(c, 0, sizeof(c));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j] % mod) % mod;
    memcpy(a, c, sizeof(c));
}

void inv(ll a[][2])
{
    int n = 2, is[2], js[2];
    memset(is, 0, sizeof(is));
    memset(js, 0, sizeof(js));
    for (int k = 0; k < n; k++)
    {
        for (int i = k, j; i < n; i++)
        {
            for (j = k; j < n && !a[i][j]; j++);
            is[k] = i, js[k] = j;
        }
        for (int i = 0; i < n; i++)
            swap(a[k][i], a[is[k]][i]);
        for (int i = 0; i < n; i++)
            swap(a[i][k], a[i][js[k]]);
        if (!a[k][k])
        {
            puts("No Solution");
            exit(0);
        }
        a[k][k] = inv(a[k][k]);
        for (int j = 0; j < n; j++)
            if (j != k)
                (a[k][j] *= a[k][k]) %= mod; 
        for (int i = 0; i < n; i++) 
            if (i != k)
            {
                ll temp = a[i][k];
                a[i][k] = 0;
                for(int j = 0; j < n; ++j)
                    (a[i][j] += mod - a[k][j] * temp % mod) %= mod;
            }
    }
    for (int k = n - 1; k >= 0; k--)
    {
        for (int i = 0; i < n; i++)
            swap(a[js[k]][i], a[k][i]);
        for (int i = 0; i < n; i++)
            swap(a[i][is[k]],a[i][k]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    sum[0] = mat(1, 0, 0, 1);
    for (int i = 1; i < n; i++)
    {
        sum[i] = sum[i - 1];
        if (s[i] == '/') mul(sum[i].a, A.a);
        else mul(sum[i].a, B.a);
    }
    while (m--)
    {
        int l, r, pl, pr;
        scanf("%d%d%d%d", &l, &r, &pl, &pr);
        mat ans = sum[l - 1];
        inv(ans.a); mul(ans.a, sum[r - 1].a);
        printf("%d\n", ans.a[pl][pr]);
    }
    return 0;
}

牛牛的猜球游戏（置换前缀和）

题意描述
给定1~10的排列，有一个长度是的操作序列，序列中每个操作是交换排列中的两个元素。接下来有m次询问，每次询问，对于 ，运用 l ~ r 的操作序列，排列是什么样的。

分析
一系列操作，每次操作后会得到一个新的排列，维护前缀排列即可。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const double pi = 3.141592653589793;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;

const int N = 100010;

int a[N][10];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < 10; i++) a[0][i] = i;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        for (int j = 0; j < 10; j++)
            a[i][j] = a[i - 1][j];
        swap(a[i][x], a[i][y]);
    }
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int t[10];
        for (int i = 0; i < 10; i++)
            t[a[l - 1][i]] = i;
        for (int i = 0; i < 10; i++)
            printf("%d ", t[a[r][i]]);
        puts("");
    }
    return 0;
}

[NOIP2013]积木大赛（差分，经典题）

题意描述
给定长度是n的序列a，序列元素。还有一个同样长度全0的b序列，每次可以选择b序列一段区间 [l, r]，让区间中每个元素加1。问最少做多少次操作让b=a。

分析
考虑用差分数组实现区间修改，如果要让 [l, r] 加1，就是在差分数组中 d[l]+=1, d[r] -= 1。
那么对序列a做一次差分，序列中正数之和是等于负数之和的绝对值的。
例如：
a 3 5 2 1 4
d 3 2 -3 -1 3 -4
那么最后的答案就等于差分序列中正数之和或者负数之和的绝对值。

代码

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define Min(a,b,c)  min(a,min(b,c))
#define Max(a,b,c)  max(a,max(b,c))

typedef long long ll;
typedef unsigned long long ull;

const double pi = 3.141592653589793;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;

const int N = 100010;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = 0;
    for (int i = n; i >= 1; i--)
    {
        a[i] = a[i] - a[i - 1];
        ans += a[i] > 0 ? a[i] : 0;
    }
    printf("%d\n", ans);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-29 12:39
点赞 评论 收藏
分享
11-27 20:18
哈尔滨理工大学 算法工程师
点赞 评论 收藏
分享
10-22 09:27
莆田学院 软件测试
点赞 评论 收藏
分享
10-09 22:05
666 C++
我这能报啥
找到工作就狠狠玩CSGO：报联合国演讲，报电子烟设计与制造
点赞 评论 收藏
分享
11-24 17:16
已编辑
华中科技大学 C++
英伟达 C++开发 一面
聊天：你现在在实习，基于什么考虑要离职找新的实习？对这个职位有多少了解？面试官介绍岗位工作内容。C++:virtual关键字作用？构造函数可以是虚函数吗？析构函数可以是虚函数吗？virtual除了可以用于虚函数，还可以用于继承时放在基类前，了解吗？c++类，有些函数是默认生成的，比如构造函数，还有？new、delete构造和析构一个类，那么如果我要构造一组对象？stl，常用的有哪些？stack使用场景？深度还是广度搜索？static_cast和dynamic_cast区别？图形：OpenGL&nbsp;渲染管线？前向渲染和延迟渲染？多边形反走样？纹理，有哪些常见的采样或者说过滤方式？调用系统函数和调用自...
查看18道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
237504次浏览 2039人参与
# 机械求职避坑tips #
23679次浏览 249人参与
# 阿里云管培生offer #
62717次浏览 1761人参与
# 25届秋招总结 #
411759次浏览 4130人参与
# 25届机械人为了秋招做了哪些准备？ #
26312次浏览 363人参与
# 地方国企笔面经互助 #
6996次浏览 17人参与
# 北方华创开奖 #
67129次浏览 553人参与
# ai智能作图 #
29279次浏览 352人参与
# 虾皮求职进展汇总 #
91946次浏览 751人参与
# 实习，投递多份简历没人回复怎么办 #
2441220次浏览 34746人参与
# 软件开发投递记录 #
1481858次浏览 23947人参与
# 我的实习求职记录 #
6134632次浏览 84021人参与
# 我在牛爱网找对象 #
74905次浏览 555人参与
# 发工资后，你做的第一件事是什么 #
9211次浏览 43人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
83333次浏览 602人参与
# 机械人怎么评价今年的华为 #
157996次浏览 1352人参与
# 京东求职进展汇总 #
513185次浏览 4681人参与
# 如果可以，你希望哪个公司来捞你 #
34029次浏览 196人参与
# 你觉得通信/硬件有必要实习吗？ #
54806次浏览 698人参与
# 歌尔求职进展汇总 #
42919次浏览 294人参与
# 在职场上，你最讨厌什么样的同事 #
6111次浏览 91人参与
# 如果再来一次，你还会选择这个工作吗？ #
116048次浏览 1145人参与
牛客网
牛客企业服务