2021-08-18 18:45 已编辑深度学习

关注

1 前缀和与差分

导图
在这里插入图片描述

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

题意描述
$n$ ( $1\leq n\leq20$ )个物品做为一个全集，第 $i$ 个物品价值 $a_i$ ，一个集合的价值为集合物品价值的异或和。 $m$ 次询问，询问选择其中一些物品 { $a_{p1},a_{p2},...,a_{pk}$ }，它的所有子集价值之和与所有全集价值之和。

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

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

$sum[i][j]$ 就是单个点，相当于是0维前缀和

第二步：

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

在这里插入图片描述
$sum[i][j]$ 此时存了当前列的前缀和，即计算了1维前缀和

第三步：

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

在这里插入图片描述

$sum[i][j]$ 此时已经完成了2维前缀和的计算

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

代码:

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

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

高维前缀和的一个应用就是 $SOSdp$ （ $Sum\ Over\ Subsets\ dynamic\ programming$ ），常与 $FWT$ 结合使用。

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

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

代码：

#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;
}

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

题意描述
给长度是 $n(n\leq 10^5)$ 的序列 $a$ ，求其 $k(-10^{18}\leq k\leq10^{18})$ 次前缀和，前缀和对 $998244353$ 取模。

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

NTT卷积 $O(nlogn)$ 求解：

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

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

只保留其中 $a_0$ 的系数得到：

序号	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
…

首先容易得到一个递推式，第 $k$ 次前缀和序号 $i$ 的系数 $b[k][i]=b[k-1][i]+b[k][i-1]$

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

答案就是 $b[k][i]=$ $C_{i+k-1}^{k-1}$

因此可以通过组合数递推的方式 $O(n)$ 得到做 $k$ 次前缀和后 $a_0$ 的系数序列 $b_k$

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

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

代码

#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] 加上一个多项式 $f(x) = a_kx^k+a_{k-1}x^{k-1}+...+a_0$
（即 $a[l]+=f(1),\ \ a[l+1]+=f(2),...,a[r]+=f(r-l+1)$ ）
最后询问 [l, r] 的元素之和。

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

代码：

#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）。

分析
首先想到 $DP$ ， $dp[i][0]$ 表示左边的塔从第一层走到第 $i$ 层的方案数， $dp[i][1]$ 表示右边的塔从第一层走到第 $i$ 层的方案数。那么就有转移方程：
$ $dp[i][0]=dp[i-1][0]+dp[i-1][1]*[s_{i-1}\neq'/ \ ']\\ dp[i][1]=dp[i-1][1]+dp[i-1][0]*[s_{i-1}='/ \ ']$ $考虑用矩阵来表示这个转移方程：$ $\left[ \begin{matrix} dp[i][0] & dp[i][1]\end{matrix} \right]= \left[ \begin{matrix} dp[i-1][0] & dp[i-1][1]\end{matrix} \right]\times\left[ \begin{matrix} 1 & [s_{i-1}=\ '/ \ ' ]\ \\ [s_{i-1}\neq \ '/ \ '] & 1 \end{matrix} \right]$ $
因此从某一层到某一层的方案数，就是这一段矩阵的连乘积。
因此可以预处理出矩阵的前缀和，因为两种可能出现的矩阵都是可逆矩阵，最后为了消除左半部分影响，乘一下左半部分矩阵的逆即可。（要注意是左乘）

代码

#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的排列，有一个长度是 $n(n\leq 10^5)$ 的操作序列，序列中每个操作是交换排列中的两个元素。接下来有m次询问，每次询问，对于 $1,2,3,...,10$ ，运用 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，序列元素 $a_i\geq0$ 。还有一个同样长度全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;
}