2021-08-21 14:47 已编辑长江师范学院 C++

关注

专题一：前缀和与差分

A-智乃酱的区间乘积
直接求前缀乘积即可，计算区间 $[l,r]$ 的乘积直接拿区间 $[1,r]$ 的乘积乘以区间 $[1,l-1]$ 乘积的逆元即可
计算逆元有三种方式：快速幂、扩展欧几里德算法、线性递推，由于模数是质数所以我们直接求 $x^{mod-2}\%mod$ 即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int a[N];
ll s[N];
ll qmi(ll a, ll b, ll p){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    s[0] = 1;
    for(int i = 1, x; i <= n; ++ i) scanf("%d", &x), s[i] = s[i - 1] * x % mod;
    while(m --){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", s[r] * qmi(s[l - 1], mod - 2, mod) % mod);
    }
}

B-智乃酱的子集与超级

高维前缀和

怎么快速求出子集和超集呢？我们可以用状压dp中的二进制压缩来做；
比如： $11011101$ 这是一个二进制数，它的第0、2、3、4、6、7位都是1，则包含这些这些物品中的某一部分的东西都是他的子集，换做代码中就是if(i >> j & 1) a[i] += a[i ^ (1 << j)]，他的超集就是全部包含这些数并且包含一个或几个在它的二进制表示下为0的位也就是第2、5位的东西，换做代码就是if(!(i >> j & 1)) f[i] += f[i | (1 << j)]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 23;
int n, m, k;
ll a[1 << N], f[1 << N];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i) scanf("%d", &a[1 << i]), f[1 << i] = a[1 << i];
    for(int j = 0; j < n; ++ j)
        for(int i = 0; i < 1 << n; ++ i)
            if((i >> j & 1) && (i != (1 << j))) a[i] ^= a[1 << j], f[i] ^= f[1 << j];
    for(int j = 0; j < n; ++ j)
        for(int i = 0; i <= 1 << n;  ++ i)
            if(!(i >> j & 1)) f[i] += f[i | (1 << j)];
    for(int j = 0; j < n; ++ j)
        for(int i = 0; i < 1 << n; ++ i)
            if(i >> j & 1) a[i] += a[i ^ (1 << j)];

    while(m --){
        scanf("%d", &k);
        int ans = 0;
        while(k --){
            int x; scanf("%d", &x);
            ans += 1 << (x - 1);
        }
        printf("%lld %lld\n", a[ans], f[ans]);
    }
    return 0;
}

我的代码比较潦草还是znjj的好看呜呜呜，贴在下边

#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE = 1048576, MAXN = 25;
int n, m, maxbit, k, x;
long long pre_sum[MAXSIZE], suf_sum[MAXSIZE], a[MAXN];
int main()
{
    scanf("%d %d", &n, &m);
    maxbit = 1 << n;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < maxbit; ++i)
    {
        long long sum = 0;
        for (int j = 0; j < n; ++j)
        {
            if (i & (1 << j))sum ^= a[j];
        }
        pre_sum[i] = sum;
        suf_sum[i] = sum;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < maxbit; ++j)
        {
            if (j & (1 << i))pre_sum[j] += pre_sum[j ^ (1 << i)];
            else suf_sum[j] += suf_sum[j ^ (1 << i)];
        }
    }
    while (m--)
    {
        scanf("%d", &k);
        int q = 0;
        for (int i = 0; i < k; ++i)
        {
            scanf("%d", &x);
            q |= (1 << (x - 1));
        }
        printf("%lld %lld\n", pre_sum[q], suf_sum[q]);
    }
    return 0;
}

C-智乃酱的前缀和与差分

前置芝士： $NTT$

繁凡大佬博客
 Pecco知乎

结论：对 $1$ 进行 $k$ 次前缀和再对原数组求卷积就是原数组的 $k$ 阶前缀和

如何对1进行 $k$ 次前缀和？，先打个表如下图：
图片说明

其实就是组合数，第一行全为 $1$ ，第二行开始就是 $\textrm{C}_{k-1}^{0},\textrm{C}_{k}^{1},\textrm{C}_{k+1}^{2}...$ 这样我们就可以线性递推出 $1$ 的 $k$ 阶前缀和，然后直接套 $NTT$ 板子求卷积即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 300010, p = 998244353, G = 3;
int n;
ll k, a[N], inv[N], ki[N];
ll qmi(ll a, ll b, ll p = 998244353){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
void init(int n){
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; ++ i)
        inv[i] = ((ll)-p / i * inv[p % i] % p + p) % p;
}
void get_ki(){
    k = (k % p + p) % p;
    ki[0] = 1;
    for(int i = 1; i < n; ++ i) 
        ki[i] = ki[i - 1] * inv[i] % p *(k + i - 1) % p;
}
int rev[N], bit, tot;
void NTT(ll a[], int inv){
    for(int i = 0; i < tot; ++ i)
        if(i < rev[i])
            swap(a[i], a[rev[i]]);
    for(int mid = 1; mid < tot; mid <<= 1){
        ll w1 = qmi(G, (p - 1) / (mid * 2));
        if(inv == -1) w1 = qmi(w1, p - 2);
        for(int i = 0; i < tot; i += mid * 2){
            ll wk = 1;
            for(int j = 0; j < mid; ++ j, wk = wk * w1 % p){
                ll x = a[i + j], y = wk * a[i + mid + j] % p;
                a[i + j] = (x + y) % p;
                a[i + mid + j] = (x - y + p) % p;
            }
        }
    }
    if(inv == -1){
        ll invn = qmi(tot, p - 2);
        for(int i = 0; i < tot; ++ i) a[i] = a[i] * invn % p;
    }
}
int main(){
    init(100000);
    scanf("%d%lld", &n, &k);
    get_ki();
    for(int i = 0; i < n; ++ i) scanf("%lld", &a[i]);
    while((1 << bit) < n + n + 1) bit ++;
    tot = 1 << bit;
    for(int i = 0; i < tot; ++ i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    NTT(a, 1), NTT(ki, 1);
    for(int i = 0; i < tot; ++ i) a[i] = a[i] * ki[i] % p;
    NTT(a, -1);
    for(int i = 0; i < n; ++ i)
        printf("%lld ", a[i] % p);
    return 0;
}

/*
5 1
1 1 1 1 1
*/

D-智乃酱的静态数组维护问题多项式

定理：最高次项为 $n$ 的 $n$ 阶多项式做 $n+1$ 阶差分后余项为常数

所以我们对 $k$ 次多项式进行 $k+1$ 阶差分就会变成有限项数，多差分一次只会多一个数，因为 $k<=5$ 所以我们将多项式都差分6次即可，最后再做7次前缀和即可求得结果

因为是在区间 $[l,r]$ 加上一段多项式，而差分会一直加到最后，所以我们应该在 $r$ 后边的位置上减去 $f(x+r-l+1)$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010, mod = 1e9 + 7;
int n, m, q, k;
ll a[N], ki[15], d1[15], d2[15];
void S(ll a[], int n, int cnt){
    while(cnt --){
        for(int i = 1; i <= n; ++ i){
            a[i] = (a[i] + a[i - 1]) % mod;
        }
    }
}
void D(ll a[], int n, int cnt){
    while(cnt --){
        for(int i = n; i > 0; -- i)
            a[i] = (a[i] - a[i - 1] + mod) % mod;
    }
}
ll f(ll x, ll a[], int k){
    ll res = 0, base = 1;
    for(int i = k; i >= 0; -- i){
        res = (res + base * a[i]) % mod;
        base = base * x % mod;
    }
    return res;
}
ll g(ll x, ll a[], ll k, ll l, ll r){
    return (- f(x + r - l + 1, a, k) + mod) % mod;
}
int main(){
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);
    D(a, n, 6);
    while(m --){
        ll l, r;
        scanf("%lld%lld%lld", &l, &r, &k);
        for(int i = 0; i <= k; ++ i) scanf("%lld", &ki[i]);
        for(int i = 1; i <= 10; ++ i){
            d1[i] = f(i, ki, k);
            d2[i] = g(i, ki, k, l, r);
        }
        D(d1, 10, 6);
        D(d2, 10, 6);
        for(int i = 1; i <= 10; ++ i){
            a[l + i - 1] = (a[l + i - 1] + d1[i]) % mod;
            a[r + i] = (a[r + i] + d2[i]) % mod;
        }
    }
    S(a, n, 7);
    while(q --){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", (a[r] - a[l - 1] + mod) % mod);
    }
    return 0;
}

E-智乃酱的双塔问题

前置芝士：矩阵求逆

逆矩阵的定义：
假设 $A$ 是一个方阵，如果存在一个矩阵 $A^{-1}$ ，使得 $A^{-1}A=I$ 且 $AA^{-1}=I$ ，那么矩阵 $A$ 就是可逆的 $A^{-1}$ 称为 $A$ 的逆矩阵

如何求逆？——初等变换法（高斯——约旦消元）
高斯——约旦消元模板
求逆需要魔改一下

// a[N][N]是增广矩阵
int gauss(){

    int r, c;
    for(r = 0, c = 0; c < n; ++ c)
    {
        int t = r;
        for(int i = r + 1; i < n; ++ i)
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if(fabs(a[t][c]) < eps) continue;
        for(int i = c; i < n + 1; ++ i) swap(a[r][i], a[t][i]);
        for(int i = n; i >= c; -- i) a[r][i] /= a[r][c];

        for(int i = 0; i < n; ++ i)
            if(fabs(a[i][c]) > eps && i != r)
                for(int j = n; j >= c; -- j)
                    a[i][j] -= a[i][c] * a[r][j];
        r ++;
    }

    if(r < n)
    {
        for(int i = r; i < n; ++ i)
            if(fabs(a[i][n]) > eps) 
                return 2;
        return 1;
    }

    return 0;
}

方法：

把 $A$ 和单位矩阵放在一个矩阵里
对 $A$ 进行加减消元，使 $A$ 变成单位矩阵
此时单位矩阵就转化为逆矩阵

原理： $[AI]=[IA^{-1}]$

举例：如果我们要求矩阵

$\begin{bmatrix} 1 & 2\\ 3 & 4 \end{bmatrix}$
的逆矩阵，

首先

$\begin{bmatrix} 1 & 2 & 1 & 0\\ 3 & 4 & 0& 1 \end{bmatrix}$

然后对其进行消元得到：

$\begin{bmatrix} 1 & 0 & -2 & -1\\ 0 & 1 & \frac{3}{2}& -\frac{1}{2} \end{bmatrix}$

所以该矩阵的逆矩阵就是

$\begin{bmatrix} -2 & 1\\ \frac{3}{2} & -\frac{1}{2} \end{bmatrix}$

现在回归本题，考虑没有 $l$ 的限制，从 $1$ 到 $r$ ，显然是一个dp

dp[i][0] = dp[i - 1][0] + s[i] == '\' ? dp[i - 1][1] : 0;
dp[i][1] = dp[i - 1][1] + s[i] == '/' ? dp[i - 1][0] : 0;

然后我们将其转化为一个矩阵的形式

$\begin{bmatrix} 1 & ?\\ ? & 1 \end{bmatrix}$

第0行第0列为1，第1行第1列为1，表示我们走自己的塔有一种方案，两个问号要取决于这次楼梯的朝向是'/'还是'\'，这样我们构造出的两个矩阵分别为

$\begin{bmatrix} 1 & 1\\ 0 & 1 \end{bmatrix}$

和

$\begin{bmatrix} 1 & 0\\ 1 & 1 \end{bmatrix}$

直接将矩阵链乘即可，需要抵消掉前一段直接乘以前一段矩阵的逆即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010, mod = 1e9 + 7;
struct Mat{
    ll a[2][2];
    Mat(){
        for(int i = 0; i < 2; ++ i)
            for(int j = 0; j < 2; ++ j)
                a[i][j] = i == j;
    }
    Mat(ll a1, ll a2, ll a3, ll a4){
        a[0][0] = a1;
        a[0][1] = a2;
        a[1][0] = a3;
        a[1][1] = a4;
    }
    void init(){
        a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
    }
};
ll A[2][4];
ll qmi(ll a, ll b, ll p){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
ll get_inv(ll x){
    return qmi(x, mod - 2, mod);
}
void gauss(int n, int x){ //高斯——约旦消元求逆矩阵
    int r, c;
    for(c = 0, r = 0; c < n; ++ c){
        int t = r;
        for(int i = r + 1; i < n; ++ i)
            if(abs(A[r][c]) < abs(A[t][c]))
                t = i;
        if(!abs(A[t][c])) continue;
        if(r != t) swap(A[r], A[t]);
        ll ans = get_inv(A[r][c]);
        for(int i = x - 1; i >= c; -- i) A[r][i] = A[r][i] * ans % mod;
        for(int i = 0; i < n; ++ i)
            if(A[i][c] && i != r)
                for(int j = x - 1; j >= 0; -- j)
                    A[i][j] = (A[i][j] - A[i][c] * A[r][j]%mod + mod) % mod;
        r ++;
    }
}
Mat getinv(Mat x){
    memset(A, 0, sizeof A);
    for(int i = 0; i < 2; ++ i)
        for(int j = 0; j < 2; ++ j){
            A[i][j] = x.a[i][j];
            A[i][j + 2] = i == j;
        }
    gauss(2, 4);
    Mat res;
    for(int i = 0; i < 2; ++ i)
        for(int j = 0; j < 2; ++ j)
            res.a[i][j] = A[i][j + 2];
    return res;
}
const Mat tA = Mat(1, 1, 0, 1);
const Mat tB = Mat(1, 0, 1, 1);
Mat operator * (Mat x, Mat y){
    Mat c;
    c.init();
    for(int i = 0; i < 2; ++ i)
        for(int j = 0; j < 2; ++ j)
            for(int k = 0; k < 2; ++ k)
                c.a[i][j] = (c.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
    return c;
}
Mat s[N];
char str[N];
int main(){
    int n, m;
    scanf("%d%d%s", &n, &m, str + 1);
    s[0] = Mat(1, 0, 0, 1);
    for(int i = 1; i < n; ++ i)
        if(str[i] == '/') s[i] = s[i - 1] * tA;
        else s[i] = s[i - 1] * tB;

    while(m --){
        int hs, ht, ps, pt;
        scanf("%d%d%d%d", &hs, &ht, &ps, &pt);
        Mat ans = getinv(s[hs - 1]) * s[ht - 1];
        printf("%lld\n", ans.a[ps][pt] % mod);
    }
    return 0;
}

F-牛牛的猜球游戏
我们进行完所有的操作之后，想要撤销前一段操作所产生的影响，因为开始状态是要从0、1、2、3...的状态开始，假设只有三个球最开始的状态是0、1、2，进行一系列操作之后变成了2、0、1，我们想把这个状态变成和0、1、2开始是一样的效果，就要把球放成1、2、0，如图：
图片说明
撤销影响之后就等同于我们在开始从0、1、2操作啦，然后把预处理的内容代回去就求出了结果

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[10], f[N][10];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < 10; ++ i) f[0][i] = i;
    for(int i = 1, l, r; i <= n; ++ i){
        scanf("%d%d", &l, &r);
        for(int j = 0; j < 10; ++ j)
            f[i][j] = f[i - 1][j];
        swap(f[i][l], f[i][r]);
    }
    while(m --){
        int l, r; scanf("%d%d", &l, &r);
        for(int i = 0; i < 10; ++ i) a[f[l - 1][i]] = i;
        for(int i = 0; i < 10; ++ i) printf("%d ", a[f[r][i]]);
        puts("");
    }
    return 0;
}

G-牛牛的Link Power I
本题有很多做法，这里只讨论前缀和方式的做法
举个栗子：

/*
设字符串为                10010001
将字符1的下一位下赋值为1   01001000(1)
做一次前缀和              01112222
再做一次前缀和            012357911
答案就是0 + 3 + 11 = 14
*/

为什么会这样？我们可以看到第一个1的贡献是0第二个1的贡献是它到第一个1的距离，第三个1的贡献是它到第一个1的距离+它到第二个1的距离，...
这里要分开看，第二次前缀和之后123这段是第一个1对第二个1的影响后边的57911可以拆分成(4+1)(5+2)(6+3)是第一个1和第二个1对第三个1的贡献和每一个1对后边的数产生一个等差数列的影响，而形成等差数列需要做两次前缀和，即第一次是10000，第二次就会变成12345

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int n;
ll a[N];
char str[N];
void get_sum(){
    for(int i = 1; i <= n; ++ i) a[i] = (a[i] + a[i - 1]) % mod;
}
int main(){
    scanf("%d%s", &n, str + 1);
    for(int i = 1; i <= n; ++ i)
            if(str[i] == '1') a[i + 1] ++;
    get_sum();
    get_sum();
    ll res = 0;
    for(int i = 1; i <= n; ++ i)
            if(str[i] == '1')
                    res = (res + a[i]) % mod;
    printf("%lld\n", res);
    return 0;
}

H-小w的糖果
如何在一个区间加上一段等差数列？

/*
a  0 0 0 1 2 3 4 5
d  0 0 0 1 1 1 1 1
dd 0 0 0 1 0 0 0 0
做两次前缀和即可
*/

那么如何加上一段平方数列？

/*
a   0 0 0 1 4 9 16 25 36
d   0 0 0 1 3 5 7  9  11
dd  0 0 0 1 2 2 2  2  2
ddd 0 0 0 1 1 0 0  0  0
在第一个位置和下一个位置上加上一个1做3次前缀和即可
*/

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
ll a[N], b[N], c[N];
void add(int n, ll a[]){
    for(int i = 1; i <= n; ++ i) a[i] = (a[i] + a[i - 1]) % mod;
}
int main(){
    int _, n, m;
    scanf("%d", &_);
    while(_ --){
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        memset(c, 0, sizeof c);
        scanf("%d%d", &n, &m);
        while(m --){
            int t, x;
            scanf("%d%d", &t, &x);
            if(t == 1) a[x] ++;
            else if(t == 2) b[x] ++;
            else c[x] ++, c[x + 1] ++;
        }
        add(n, a);
        add(n, b);
        add(n, b);
        add(n, c);
        add(n, c);
        add(n, c);
        for(int i = 1; i < n; ++ i) printf("%lld ", (a[i] + b[i] + c[i]) % mod);
        printf("%lld\n",(a[n] + b[n] + c[n]) % mod);
    }
    return 0;
}

I [NOIP2013]积木大赛
每次可以修改一个区间，将第 $i$ 个位置上的数修改为 $h_i$

比如我们修改结束的结果为 2 3 4 1 2
他的差分数组就是 2 1 1 -3 1
在区间加1就等于在前边位置加1然后选择一个位置减1，因为差分数组做一遍前缀和是原数组而 $hi>=0$ ，所以差分数组中的每一个负数都可以被它前边的正数抵消掉，所以答案就是差分数组的正数的和

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
ll b[N];
int main(){
    int n, cnt = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &b[i]);
        if(b[i] > b[i - 1])
            cnt += b[i] - b[i - 1];
    }
    printf("%d\n", cnt);
}

J-[NOIP2018]道路铺设

这个题和上一题一模一样，甚至代码都一样...