JZTXT

差分&快速幂

发布时间 2023-07-05 11:12:53作者: Codehyx

差分&快速幂

差分

给定长度为\(n\)的序列\(a_{1},a_{2},\dots a_{n}\)，它的差分序列定义为相邻两项之差，即\(a_{1},a_{2}-a_{1},a_{3}-a_{2}\dots a_{n}-a_{n-1}\)

差分序列的第\(i\)项为\(d_{i}=a_{i}-a_{i-1}\)，其中\(a_{0}=0\)

可以发现，对差分序列做前缀和，可以还原出原数列。

一维差分 区间修改

如果对原序列区间\([l,r]\)的元素加上\(v\)，实际上对应了差分序列两个元素的修改。

也就是说，区间内的每个元素的加法操作，可以直接变成差分序列上两个元素的修改

所有操作做完后，对差分序列做前缀和即可还原原序列。

例题：区间修改

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n,m,l,r,c,a[MAXN],d[MAXN];

int main(){
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++){
		
		cin >> a[i];
	}
	
	for (int i = 1; i <= n; i++){
		
		d[i] = a[i] - a[i - 1];
	}
	
	while (m--){
		
		cin >> l >> r >> c;
		
		d[l] += c;
		
		d[r + 1] -= c;
	}
	
	for (int i = 1; i <= n; i++){
		
		d[i] = d[i - 1] + d[i];
	}
	
	for (int i = 1; i <= n; i++){
		
		cout << d[i] << ' ';
	}
	
	return 0;
}

先直接做差分，然后输入\(l,r,c\)，修改之后，就直接做前缀和输出了。

二维差分 矩阵修改

暴力修改：\(O(n_{} ^ {2})\)

对列差分后的矩阵做修改：\(O(n)\)

逐维差分，对先列差分后行差分的矩阵做修改：\(O(1)\)

还原原数组

做二维前缀和即可，\(O(n_{} ^ {2})\)

示例二位数组

原图（表1）：

0 0 0 0 0 0
0 1 1 1 0 0
0 1 1 1 0 0
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
列差分后（表2）：
0 0 0 0 0 0
0 1 0 0 -1 0
0 1 0 0 -1 0
0 1 0 0 -1 0
0 0 0 0 0 0
0 0 0 0 0 0
做列前缀和还原

再行差分（表3）：

0 0 0 0 0 0
0 1 0 0 -1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 -1 0
0 0 0 0 0 0
做行前缀和，再做列前缀和还原

原数组直接做行差分（表4）：

0 0 0 0 0 0
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 -1 -1 -1 0 0
0 0 0 0 0 0

做行前缀和还原

上4个表的顺序：

表1\(\to\)表2\(\to\)表3

表1\(\to\)表4

例题：矩阵修改

方法1：原图直接做列差分，还原做列差分

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n,d[1010][1010],cnt[MAXN];

int main(){
	
	cin >> n;
	
	for (int i = 1; i <= n; i++){
		
		int x1,y1,x2,y2;
		
		cin >> x1 >> y1 >> x2 >> y2;
		
		for (int j = y1; j <= y2; j++){ //列差分
			 
			d[x1][j]++;
			
			d[x2 + 1][j]--;
		}
	}
	
	for (int i = 1; i < 1010; i++){ //列前缀和
		
		for (int j = 1; j < 1010; j++){
			
			d[i][j] = d[i][j] + d[i - 1][j];
			
			cnt[d[i][j]]++;//统计数
		}
	}
	
	for (int i = 1; i <= n; i++){
		
		cout << cnt[i] << ' ';
	}
	
	return 0;
}

方法2：原图直接做行差分，还原做行差分和列差分，可以交换顺序

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n,d[1010][1010],cnt[MAXN];

int main(){
	
	cin >> n;
	
	for (int i = 1,x1,y1,x2,y2; i <= n; i++){
		
		cin >> x1 >> y1 >> x2 >> y2;
		
		d[x1][y1]++,d[x2 + 1][y2 + 1]++;
		
		d[x2 + 1][y1]--,d[x1][y2 + 1]--;
        
        //行差分
	}
	
	for (int i = 1; i < 1010; i++){ //行前缀和
		
		for (int j = 1; j < 1010; j++){
			
			d[i][j] = d[i][j] + d[i - 1][j];
		}
	}
	
	for (int i = 1; i < 1010; i++){ //列前缀和
		
		for (int j = 1; j < 1010; j++){
			
			d[i][j] = d[i][j] + d[i][j - 1];
			
			cnt[d[i][j]]++;//统计数
		}
	}
	
	for (int i = 1; i <= n; i++){
		
		cout << cnt[i] << ' ';
	}
	
	return 0;
}

方法3，原图直接做行差分，做行前缀和还原

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n,d[1010][1010],cnt[MAXN];

int main(){
	
	cin >> n;
	
	for (int i = 1; i <= n; i++){
		
		int x1,y1,x2,y2;
		
		cin >> x1 >> y1 >> x2 >> y2;
		
		for (int j = y1; j <= y2; j++){
			 
			d[x1][j]++;
			
			d[x2 + 1][j]--;
		}
	}
	
	for (int i = 1; i < 1010; i++){
		
		for (int j = 1; j < 1010; j++){
			
			d[i][j] = d[i][j] + d[i - 1][j];
			
			cnt[d[i][j]]++;
		}
	}
	
	for (int i = 1; i <= n; i++){
		
		cout << cnt[i] << ' ';
	}
	
	return 0;
}

快速幂

折半分解

令\(F(a,b)=a_{} ^ {b},a \ne 0\)

若\(b=0,F(a,b)=1\)

若\(b\)为偶数，\(F(a,b)=(F(a,b / 2))_ {} ^ {2}\)

若\(b\)为奇数，\(F(a,b)=(F(a,\lfloor\frac {b}{2}\rfloor))_ {}^{2}\)

例题：快速幂

#include<bits/stdc++.h>

using namespace std;

int Pow(int a, int b, int p){
	
	if (b == 0) return 1 % p;
	
	if (b % 2 == 0){
	
		int ret = Pow(a, b / 2, p);
		
		return 1ll * ret * ret % p;
	}
	else {
	
		int ret = Pow(a, b / 2, p);
		
		return 1ll * ret * ret % p * a % p;
	}
}

int main(){
	
	int a, b, p, t;
	
	cin >> t;
	
	while (t--){
		
		cin >> a >> b >> p;
		
		cout << Pow(a, b, p) << "\n";
	}
	
	return 0;
}

这题很简单，只要知道折半分解定理即可

费马小定理

给定质数\(p\)和整数\(a\)，且\(p\not \mid a\)，则\(a_{} ^ {p-1} \equiv 1 \pmod p\)

乘法逆元

给定质数\(p\)和整数\(a\)，则\(a\)在\(\bmod p\)意义下的惩罚逆元为\(a_{} ^ {p-2}\)

\(\frac{x}{a} \equiv \frac{x}{a}·1\equiv \frac{x}{a}·a_{} ^ {p-1}\equiv x·a_{} ^ {p-2} \pmod p\)

例题：乘法逆元

#include<bits/stdc++.h>

using namespace std;

long long Pow(int n,int p,int p2){
	
	if (p == 0) return 1;
	
	long long ret = Pow(n,p / 2,p2);
	
	ret = ret * ret % p2;
	
	if (p % 2 != 0) ret = ret * n % p2;
	
	return ret;
}

int main(){
	
	int n,p;
	
	cin >> n >> p;
	
	if (n % p == 0){
		
		cout << -1;
		
		return 0;
	}
	
	cout << Pow(n,p - 2,p);
	
	return 0;
}

这个就是结合了快速幂和费马小定理的玩意，也简单

完结撒花！