前缀和
void Prefix_sum(const int a[], const int n) {//获得前缀和数组
for (int i = 1;i <= n;++i) {
Prefix__sum[i] = a[i] + Prefix__sum[i - 1];
}
}
差分
void Difference(const int a[], const int n) {//获得差分数组
for (int i = 1;i <= n;++i) {
Difference_[i] = a[i] - a[i - 1];
}
return;
}
区间更新
void Interval_Maintenance(int l, int r, int k,int Difference_[]) {//对差分数组区间[l,r]上的所有数进行更新操作(k可能为负数)
Difference_[l] += k;
Difference_[r + 1] -= k;
return;
/*要想获得经过区间更新之后的数组中的第n个元素的值
int sum =0;
for (int i = 1;i <= n;++i) {
sum += Difference_[i];
}*/
}
快速幂取模
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll Quick_Pow_Mod(ll a, ll b, ll mod) {//求a的b次方
ll ans = 1;
while (b) {
if (b & 1) {
ans = (ans % mod * a % mod) % mod;
}
a = (a % mod * a % mod) % mod;
b >>= 1;
}
return ans;
}
int main() {
ll a, b, p;cin >> a >> b >> p;//求a的b次方模p
cout << Quick_Pow_Mod(a, b,p) << endl;
}
矩阵乘法
左边的数组的列数==右边数组的行数
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, m, p;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int main()
{
cin >> n >> m >> p;//第一个矩阵为n行m列 第二个矩阵为m行p列 最终结果为n行p列的矩阵
for (int i = 1;i <= n;++i) {
for (int k = 1;k <= m;++k) {
for (int j = 1;j <= p;++j) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return 0;
}
```cpp
举例(矩阵加速求斐波那契数列的第n项)
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll n;
struct Matrix
{
ll matrix[15][15];
Matrix() {
memset(matrix, 0, sizeof(matrix));//构造函数 创建Matrix类型变量时 自动调用
}
};
Matrix mul(Matrix x, Matrix y)//矩阵乘法核心代码
{
Matrix res;
for (int i = 0;i < 2;i++)
for (int k = 0;k < 2;k++)
for (int j = 0;j < 2;j++)
res.matrix[i][j] = (res.matrix[i][j] % mod + x.matrix[i][k] % mod * y.matrix[k][j] % mod) % mod;
return res;
}
ll Quick_Matrix_Pow(ll p)
{
Matrix base;
Matrix ans;
for (int i = 0;i < 2;i++)
ans.matrix[i][i] = 1;//初始化答案矩阵(对角线上为1 ,其余为0)
base.matrix[0][0] = base.matrix[0][1] = base.matrix[1][0] = 1;
base.matrix[1][1] = 0;//初始化base矩阵
while (p)//类似快速幂
{
if (1 & p) ans = mul(ans, base);//调用矩阵乘法
base = mul(base, base);
p >>= 1;
}
return ans.matrix[0][1];//ans.matrix = {f(n+1),f(n),f(n),f(n-1)}
//答案为ans.matrix[0][1]或ans.matrix[1][0]
}
int main()
{
cin >> n;
cout << Quick_Matrix_Pow(n) << endl;
return 0;
}
原文链接: https://www.cnblogs.com/zzqwtc/p/14127384.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/334333
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!