[数据结构与算法]牛客 前缀和专题 简要题解

链接：

前缀和专题

A：

做前缀乘即可，每次计算即
$sum[r]?逆元$$su{m}_{l?1}^{mo?2}$

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mo = 1000000007;
int a[100005], n, m;
ll sum[100005];

ll mul(ll x,ll y) {
    return (x*y-(ll)((long double)x/mo*y)*mo+mo)%mo;     
}

ll power(ll x, ll y) {
   if (x == 1) return 1;
   ll rp = 1;
   for (; y; y >>= 1) {
   	    if (y & 1) rp = mul(rp, x);
   	    x = mul(x, x);
   }	
   return rp;
}

int main() {
	scanf("%d%d", &n, &m);
	sum[0] = 1;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = 1ll*sum[i-1]*a[i]%mo;
    int l, r; 
	for (int i = 1; i <= m; i++) {
    	scanf("%d%d", &l, &r);
    	ll ans = mul(sum[r], power(sum[l-1],mo-2));
    	printf("%lld\n", ans);
	}	
}

B：

考虑二进制下每一位的贡献，即计算二进制下某一位$1$的个数，
对于第$i$位而言，
考虑集合$S$中$n$个数$a_1,...,a_n$
二进制下有$1$的为$a_{p1},a_{p2},...,a_{px}$
剩下 $n?x$该位置为$0$，
发现$S$的一个子集$T$第$i$位的异或和
只与$a_{p1},.,a_{px}$选择放在$T$中的个数有关，奇数为$1$，偶数为$0$
所以该集合的子集能在该位产生贡献，显然要在$x$个中选奇数个
$\sum C_x^i$ $(i<=x，且i为奇数)$
根据二项式定理该式$=2^{x?1}$
其他$n?x$个$a_{?}$可任选
则$S$能在第$i$位产生的贡献可计算为
$2^i?2^{x?1}?2^{n?x}$
同理可算完$S$的所有子集贡献
对于 $S$的超集的贡献，
因为相当于$S$必选，在除$S$的总集合中再任选
我们把$S$中所有数都选上，得到一个总异或结果，记为$y$
然后将
该结果$y$与不包含$S$的总集合做上述计算，得到贡献$nu{m}_1$
再将不包含$S$的总集合做上述计算，得到贡献$nu{m}_2$
$nu{m}_1?nu{m}_2$即$S$的超集的总贡献

代码：

#include<bits/stdc++.h>

#define N 25

using namespace std;

typedef long long ll;

int num[N], a[N], b[N], c[N], n, m, tot;
bool orz[21];
ll mi[21];

int main() {
	mi[0] = 1; for (int i = 1; i <= 63; i++) mi[i] = mi[i-1]*2ll;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int x, cnt;
	ll ans1, ans2;
	while (m--) {
		scanf("%d", &cnt);
		memset(orz, 0, sizeof(orz));
		for (int i = 1; i <= cnt; i++) scanf("%d", &x), b[i] = a[x], orz[x] = 1;
		//
		ans1 = 0;
		for (int i = 0; i < 20; i++) {
			x = 0;
			for (int j = 1; j <= cnt; j++) x += ((b[j] >> i) & 1);
		    if (x) ans1 += mi[i+(x-1)+(cnt-x)];
		    num[i] = x%2;
		}
		//
		ans2 = 0;
		tot = 0; for (int i = 1; i <= n; i++) if (!orz[i]) c[++tot] = a[i];
		for (int i = 0; i < 20; i++) {
			x = num[i];
			for (int j = 1; j <= tot; j++) x += ((c[j] >> i) & 1);
			if (x) ans2 += mi[i+(x-1)+((tot+1)-x)]; 
		}
		for (int i = 0; i < 20; i++) {
			x = 0;
			for (int j = 1; j <= tot; j++) x += ((c[j] >> i) & 1);
			if (x) ans2 -= mi[i+(x-1)+(tot-x)];
		}
		//
		printf("%lld %lld\n", ans1, ans2);
		
	}		
}

C：

多项式求高维前缀和差分，好像是板子题，先埋坑

D：

每次将插入的多项式丢到线段树对应区间，
线段树一个节点表示一个区间，且对应一个多项式，若多个多项式则合并
合并时候暴力将幂次相同的合并即可，因为多项式间可能开始的$f()$不同，合并多项式时以某个$f()$为标准，用二项式拆解另一个即可
所有插入完了以后将整颗线段树跑一遍，求出新的前缀和，然后$O(1)$回答询问即可

代码：

#include<bits/stdc++.h>

#define N 100005

using namespace std;

typedef long long ll;

const ll mo = 1000000007;
struct Node {
	ll d[6]; int frt;
}T[N*5];
ll c[N][6], facinv[6], fac[6], inv[6], sum[N], a[N], b[6];
int cnt[N], n, m, q;

void read(ll &x) {
	ll f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = (ll)x*10+(s-'0'); s = getchar(); } 
	x = x*f;
}

void read1(int &x) {
	int f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x*10+(s-'0'); s = getchar(); }
	x = x*f;
}

void pre_work() {
	inv[1] = 1; 
	for (int i = 2; i <= 5; i++) inv[i] = 1ll*(mo-mo/i)*inv[mo%i]%mo; 
	fac[0] = 1;
	for (int i = 1; i <= 5; i++) fac[i] = 1ll*fac[i-1]*i%mo;
	facinv[0] = 1; facinv[1] = 1;
	for (int i = 2; i <= 5; i++) facinv[i] = facinv[i-1]*inv[i]%mo;
}

ll Cnum(int x, int y) {
	if (!x || !y) return 1;
	return fac[x]*facinv[y]%mo*facinv[x-y]%mo;
}

void merge(int x, int num1, int num2) {
	if (!T[x].frt) {
		T[x].frt = num2; 
		for (int i = 0; i <= 5; i++) T[x].d[i] = c[num1][i];
	    return;
	}  
	int l = num2-T[x].frt;
	for (int i = 0; i <= 5; i++) {
		//c[num1][i]*num2^i
		//c[num1][i]*(T[x].frt+l)^i
		ll now = 1;
		for (int j = 0; j <= i; j++) {
			(T[x].d[i-j] += c[num1][i]*Cnum(i, j)%mo*now%mo) %= mo;
		    now = 1ll*now*l%mo;
		}
	}
}

void putdown(int x, int L, int R) {
	if (!T[x].frt) return;
	for (int i = 0; i <= 5; i++) c[m+1][i] = T[x].d[i];
	merge(x*2, m+1, T[x].frt); 
	int mid = (L+R)>>1;
	merge(x*2+1, m+1, T[x].frt+(mid-L+1));
	T[x].frt = 0;
}


void Insert(int now, int L, int R, int liml, int limr, int num1, int num2) {
	if (L == liml && R == limr) {
       merge(now, num1, num2); return;
	}
	putdown(now, L, R);
	int mid = (L+R)>>1;
	if (liml > mid) Insert(now*2+1, mid+1, R, liml, limr, num1, num2);
	   else if (limr <= mid) Insert(now*2, L, mid, liml, limr, num1, num2);
	        else Insert(now*2, L, mid, liml, mid, num1, num2), 
			     Insert(now*2+1, mid+1, R, mid+1, limr, num1, num2+(mid-liml+1));
}

void wycnzds(int now, int L, int R) {
	if (L == R) {
		if (T[now].frt) {
			ll per = 1;
		    for (int i = 0; i <= 5; i++) 
		        (a[L] += T[now].d[i]*per%mo) %= mo, per = 1ll*per*T[now].frt%mo;
	        (a[L] += mo) %= mo; 
		}
		return;
	} 
	putdown(now, L, R);
	int mid = (L+R)>>1;
	wycnzds(now*2, L, mid); wycnzds(now*2+1, mid+1, R);
}

void write(ll x) {
	if (x < 10) { putchar(x%10+'0'); return; }
	write(x/10); putchar(x%10+'0');
}
int main() {
	pre_work();
	read1(n); read1(m); read1(q);
	for (int i = 1; i <= n; i++) read(a[i]);
	int l, r;
	for (int i = 1; i <= m; i++) {
		read1(l); read1(r); read1(cnt[i]); 
		for (int j = 0; j <= cnt[i]; j++) read(c[i][cnt[i]-j]); 
		Insert(1, 1, n, l, r, i, 1);
	}
	wycnzds(1, 1, n);
	for (int i = 1; i <= n; i++) sum[i] = ((sum[i-1]+a[i])%mo+mo)%mo;
	ll ans;
	// 592 409 135 154 486
	for (int i = 1; i <= q; i++) {
		read1(l); read1(r);
		ans = (sum[r]-sum[l-1])%mo;
		(ans += mo) %= mo;
		write(ans); printf("\n");
	}
	return 0;
}

E：

设$f_{i,0},f_{i,0}$表示到第$i$层左，右的方案数
对于$f_{i,0}f$${}_{i,1}?>f_{i+1,0},f_{i+1,1}$，
发现无非就是2种转移矩阵，
$1$ $0$
$1$ $1$
或者
$1$ $1$
$0$ $1$

直接根据楼梯处理出每个点对应的矩阵
对于一个询问$(hs,ps)?>(ht,pt)$，
用线段树求出区间$[hs,ht]$的矩阵乘积即可
因为线段树先序遍历的原因，不会对矩阵用到交换律，只会用到结合律，所以结果是正确的
求出矩阵区间乘积$y=$
$a$ $b$
$c$ $d$
以后，考虑初态
$根据ps$，选择矩阵$0,1$或者$1,0$，
作为$f_{hs,0},f_{hs,1}$初态
乘上矩阵$y$即可得到$f_{ht,0},f_{ht,1}$

代码：

#include<bits/stdc++.h>

#define N 100005

using namespace std;

typedef long long ll;

const int mo = 1000000007;

struct Matrix{
	ll a[3][3];
};
int n, m, hs, ht, ps, pt;
char s[N];
Matrix T[N*5], c[2], num;

void Pre_Work() {
	c[0].a[1][1] = 1; c[0].a[2][1] = 1; c[0].a[1][2] = 0; c[0].a[2][2] = 1;
	c[1].a[1][1] = 1; c[1].a[2][1] = 0; c[1].a[1][2] = 1; c[1].a[2][2] = 1;  
}

Matrix mul(Matrix aa, Matrix bb) {
	Matrix cc; memset(cc.a, 0, sizeof(cc.a)); 
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= 2; j++)
		    for (int k = 1; k <= 2; k++) 
		        (cc.a[i][j] += aa.a[i][k]*bb.a[k][j]%mo) %= mo;
	return cc;
}

void Build(int now, int L, int R) {
    if (L == R) {
    	int opt = (s[L] == '/');
    	memcpy(T[now].a, c[opt].a, sizeof(c[opt].a));
		return;
	}	
	int mid = (L+R)>>1;
	Build(now*2, L, mid); 
	Build(now*2+1, mid+1, R);
	T[now] = mul(T[now*2], T[now*2+1]);
}

void Getmulsum(int now, int L, int R, int liml, int limr) {
	if (L == liml && R == limr) {
		if (num.a[1][1] == -1) memcpy(num.a, T[now].a, sizeof(T[now].a)); 
	       else num = mul(num, T[now]);
	    return;
	}
	int mid = (L+R)>>1;
	if (liml > mid) Getmulsum(now*2+1, mid+1, R, liml, limr);
	   else if (limr <= mid) Getmulsum(now*2, L, mid, liml, limr);
	        else Getmulsum(now*2, L, mid, liml, mid), Getmulsum(now*2+1, mid+1, R, mid+1, limr);
}

void Calc() {
	ll frt[3], ans[3];
	memset(num.a, 255, sizeof(num.a));
	Getmulsum(1, 1, n-1, hs, ht-1);
    if (!ps) frt[1] = 1, frt[2] = 0; else frt[1] = 0, frt[2] = 1;
    memset(ans, 0, sizeof(ans));
	for (int i = 1; i <= 2; i++) 
        for (int j = 1; j <= 2; j++)
		    (ans[i] += frt[j]*num.a[j][i]%mo) %= mo;
	for (int i = 1; i <= 2; i++) (ans[i] += mo) %= mo;
	printf("%lld\n", ans[pt+1]);
	
}

int main() {
	Pre_Work();
	scanf("%d%d", &n, &m);
	scanf("%s", s+1);
	Build(1, 1, n-1);
	for (int i = 1; i <= m; i++) 
		scanf("%d%d%d%d", &hs, &ht, &ps, &pt), Calc();
	return 0;
} 

F：

考虑经过前$a_1$次操作，$b_1$位置是小球$k$
经过前$a_2$次操作，小球$k$的位置是$b_2$
那么我如果从初始状态，只经过操作$(a_1+1)$到操作$a_2$，
就相当于$b_1$位置的$k$变成了$b_1$（初始状态位置i对应小球i），最后$b_1$在$a_2$对应的位置肯定就是原先$k$对应的位置$b_2$
那么一开始先预处理做一遍，
记录每次操作过后，位置$i$是什么小球，小球$i$在什么位置
每次询问直接回答即可

代码：

#include<bits/stdc++.h>

#define N 500005

using namespace std;

int a[N][10], b[N][10], n, m;
int ans[10];

int main() {
    scanf("%d%d", &n, &m);
	for (int i = 0; i < 10; i++) a[0][i] = i, b[0][i] = i;
	int x, y;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &x, &y);
		for (int j = 0; j < 10; j++) b[i][j] = b[i-1][j];
		swap(b[i][x], b[i][y]);
		for (int j = 0; j < 10; j++) a[i][b[i][j]] = j; 
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		for (int j = 0; j < 10; j++) ans[a[y][b[x-1][j]]] = j;
		for (int j = 0; j < 9; j++) printf("%d ", ans[j]); printf("%d\n", ans[9]);
	}
//0 7 6 3 4 5 2 1 8 9

} 

G：

考虑从左向右扫遍，每个右移会使左边的所有$link$点对接下来的$link$点的相对位置+1，
记录$link$点数目，以及相对距离和
每次到$link$点直接统计即可

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mo = 1000000007;

ll dis, ans;
int siz, n;
char s[100005];

int main() {
//	freopen("data.in", "r", stdin);
	scanf("%d", &n);
	scanf("%s", s+1);
	for (int i = 1; i <= n; i++) {
		if (s[i] == '1') (ans += dis) %= mo, ++siz;
		(dis += 1ll*siz)  %= mo;
	}
	printf("%lld\n", ans);
	return 0;
}

H:

代码：

#include<bits/stdc++.h>

#define N 100005

using namespace std;

typedef long long ll;

const int mo = 1000000007;

int a[4][N], sum[N], n, m, T;
ll now1;
ll now2, siz2;
ll now3, siz3, now33;
ll ans;

void pre_work() {
	now1 = 0; 
	now2 = 0; siz2 = 0;
	now3 = 0; siz3 = 0; now33 = 0;
    for (int i = 1; i <= 3; i++) 
        for (int j = 1; j <= n; j++) a[i][j] = 0;
}

int main() {
//	freopen("data.in", "r", stdin);
	scanf("%d", &T);
	int type, pos;
	while (T--) {
        scanf("%d%d", &n, &m);
    	pre_work();	
		for (int i = 1; i <= m; i++) scanf("%d%d", &type, &pos), ++a[type][pos];
		for (int i = 1; i <= n; i++) {
			if (a[1][i]) (now1 += a[1][i]) %= mo;
			//
			if (a[2][i]) (siz2 += a[2][i]) %= mo; 
			(now2 += siz2) %= mo;
			// 
			(now33 += 2ll*now3%mo+siz3%mo) %= mo;
			(now3 += siz3) %= mo;
			if (a[3][i]) 
			   (siz3 += a[3][i]) %= mo, 
			   (now3 += a[3][i]) %= mo,
			   (now33 += a[3][i]) %= mo;  
			//
			ans = ((now1+now2)%mo+now33)%mo;
			(ans += mo) %= mo;
			if (i < n) printf("%lld ", ans); 
		}
		printf("%lld\n", ans);
    }
	return 0;
}

I:

显然做差，大于$0$的差值的计入答案即可

代码：

#include<bits/stdc++.h>

#define N 100005

using namespace std;

int h[N], c[N], n, ans;

int main() {
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	for (int i = 1; i <= n; i++) c[i] = h[i]-h[i-1];
	for (int i = 1; i <= n; i++) 
	    if (c[i] > 0) ans += c[i];
	printf("%d\n", ans);
	return 0;
}

J:

也是做差，然后直接计算正的差值

代码：

在这里插入代码片#pragma GCC optimize(3)
#include <iostream>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define rep(i, st, ed) for (int i = st; i <= ed; i++)
#define rwp(i, ed, st) for (int i = ed; i >= st; i--)
#define mt(x) memset(x, 0, sizeof(x))
#define mp(x, y) memcpy(x, y, sizeof(y))
#define lson(x) x * 2 
#define rson(x) x * 2 + 1

#define N 100005
 
using namespace std;

typedef long long ll;

int a[N], n;
ll ans;

int read(int &x) {
	int f = 1; x = 0; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + (s - '0'); s = getchar(); }
	return x * f;
}

int main() {
//	frepen("data.in", "r", stdin);
	read(n);
	rep(i, 1, n) read(a[i]);
	rep(i, 1, n) if (a[i] > a[i - 1]) ans = ans + (ll)(a[i] - a[i - 1]);
	printf("%lld\n", ans); 
	return 0;
}