快速幂:可参考该链接百科快速幂也可以参考这个博客快速幂博客
给出快速幂的题目和代码:快速幂||取余计算
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
ll b, p, k;
int main(){
cin>>b>>p>>k;
ll c = b, d = p, m = k;
ll x = 1;
while(p){
if(p&1) x = x*b%k;
b = (b * b)%k;
p>>=1;
}
cout<<c<<"^"<<d<<" mod "<<m<<"="<<x%k<<endl;
return 0;
}
在有些题目中,当数据很大时,使用递归和递推复杂度很高,这时,使用矩阵快速幂就是一个很好的方法了。这里附上其他博主写的矩阵快速幂的知识矩阵快速幂
还有一题洛谷的矩阵快速幂题目:矩阵快速幂以及ac代码矩阵快速幂模板:
#include<iostream>
#include<string.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
const ll maxn = 110;
ll n, k;
struct mat{
ll m[maxn][maxn];
};
mat operator * (mat a, mat b){
mat ret;
memset(ret.m, 0, sizeof(ret.m));
for(int i = 0; i < maxn; i++){
for(int j = 0; j < maxn; j++){
for(int k = 0; k < maxn; k++){
ret.m[i][j] +=(a.m[i][k]%MOD)*(b.m[k][j]%MOD);
ret.m[i][j]%= MOD;
}
}
}
return ret;
}
mat init_unit(){//构造单位矩阵
mat u;
for(int i = 0; i < maxn; i++){
u.m[i][i] = 1;
}
return u;
}
mat pow_mat(mat a, ll n){
mat ret = init_unit();
while(n){
if(n&1) ret = ret*a;//n&1是判断n的二进制最后一位是不是1,是1返回1,不是则返回0
a = a*a;
n>>=1;
}
return ret;
}
int main(){
cin>>n>>k;
mat a;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin>>a.m[i][j];
}
}
mat res = pow_mat(a, k);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout<<res.m[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
在矩阵快速幂有些题目中,最关键的是构造矩阵,构造矩阵先找到题目中的关系式,然后根据关系式右边的已知去构造矩阵,找到对应的关系
1.这里可以去参考每个小项的构造,找出规律,然后构造。这里想获得的是a[n], a[n-1],a[n-2]的矩阵,所以通过以下方式去构造,也可以通过关系式直接构造
2.还有一种矩阵构造的方法就是上面说的直接通过关系式去构造,附上其他博主的链接:矩阵构造方法
总之,在矩阵快速幂中,构造矩阵是很重要的。
以上博客参考了其他资料。
例如洛谷的一题:矩阵加速
这题中的等式右边只用到了a[x-3]和a[x-1],而没有用到a[x-2]; 通过做的几题可知,一般跳跃的使用,都会将被跳跃的信息补齐,(这里要将a[x-2]补齐)再去推出。这里已知a[1],a[2],a[3]所以可通过这三项去构造(a[x],a[x-1],a[x-2])(当然,不是每题所有的已知都要用上),通过a[x]=1a[x-1]+0a[x-2]+1a[x-3](这里将被跳跃的信息补齐了)可得a[x+1]=1a[x]+0a[x-1]+1a[x-2];
通过(a[x-1], a[x-2], a[x-3])为了得到 (a[x], a[x-1], a[x-2]) ,可求出一个矩阵,这个矩阵就是我们要的矩阵
#include<iostream>
#include<string.h>
#define Mod 1000000007
using namespace std;
typedef long long ll;
struct mat{
ll m[5][5];
};
mat init(){
mat res;
memset(res.m, 0, sizeof(res.m));
for(int i = 0; i < 5; i++){
res.m[i][i] = 1;//这里是构造单位矩阵,即对角线是1,其他地方都是0
}
return res;
}
mat operator * (mat a, mat b){
mat ret;
memset(ret.m, 0, sizeof(ret.m));
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
for(int k = 0; k < 5; k++){
ret.m[i][j] += (a.m[i][k]%Mod)*(b.m[k][j]%Mod);
ret.m[i][j] %= Mod;
}
}
}
return ret;
}
mat mul_total(mat x, ll n){
mat a = init();
while(n){
if(n & 1) a = a*x;
x = x * x;
n >>= 1;
}
return a;
}
mat base, ss;
int main(){
ll t, n;
cin>>t;
while(t--){
cin>>n;
memset(base.m, 0, sizeof(base.m));
memset(ss.m, 0, sizeof(ss.m));
base.m[0][0] = base.m[0][1] = base.m[1][2] = base.m[2][0] = 1;//这里是所求得的矩阵
ss.m[0][0] = ss.m[0][1] = ss.m[0][2] = 1;//这里是a[3], a[2], a[1]的初始矩阵
if(n <= 3) cout<<1<<endl;
else{
mat s = mul_total(base, n-3);//减多少是根据初始矩阵中最大的下标是多少
ss = ss * s;
cout<<ss.m[0][0]<<endl;
}
}
return 0;
}
这里加入fibonacci的题目:斐波那契数列以及ac代码
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
#define Mod 10000
typedef long long ll;
struct mat{
ll m[5][5];
};
mat init(){
mat a;
memset(a.m, 0, sizeof(a.m));
for(int i = 0; i < 5; i++){
a.m[i][i] = 1;
}
return a;
}
mat operator * (mat a, mat b){
mat c;
memset(c.m, 0, sizeof(c.m));
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
for(int k = 0; k < 5; k++){//因为输出后四位数,则每次计算后四位就可以了
c.m[i][j] += (a.m[i][k]%Mod)*(b.m[k][j] % Mod);
c.m[i][j] %= Mod;
}
}
}
return c;
}
mat mul(mat x, ll n){
mat y = init();
while(n){
if(n&1) y = y*x;
x = x*x;
n>>=1;
}
return y;
}
mat a, b;
int main(){
ll n;
while((cin>>n) && (n != -1)){
memset(a.m, 0, sizeof(a.m));
memset(b.m, 0, sizeof(b.m));
a.m[0][0] = a.m[0][1] = a.m[1][0] = 1;
a.m[1][1] = 0;
b.m[0][0] = 1;
b.m[0][1] = 0;
if(n == 0){
cout<<0<<endl;
}else if(n == 1){
cout<<1<<endl;
}else{
mat c = mul(a, n-1);
b = b*c;
cout<<b.m[0][0]<<endl;
}
}
return 0;
}
矩阵快速幂中还会涉及二分求和,以下是二分求和的题目以及参考博客:矩阵快速幂及二分求和题目和二分幂求和参考博客、题解、题解博客
这里也有涉及^和&符号的二进制运算符的题目HDU 2276:这里参考了其他的博主的博客
博客一、参考代码博客
以下为题意:方法为:以及我的ac代码:
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
struct mat{
int m[110][110];
};
mat ss, b;
int m, len;
mat init(){
mat res;
memset(res.m, 0, sizeof(res.m));
for(int i = 0; i < len; i++){
res.m[i][i] = 1;
}
return res;
}
mat mul(mat a, mat b){
mat res;
for(int i = 0; i < len; i++){
for(int j = 0; j < len; j++){
res.m[i][j] = 0;
for(int k = 0; k < len; k++){
res.m[i][j] ^= (a.m[i][k] & b.m[k][j]);
}
}
}
return res;
}
mat pow(mat a, int n){
mat res = init();
while(n){
if(n&1) res = mul(res, a);
a = mul(a, a);
n >>= 1;
}
return res;
}
int main(){
string s;
while(cin>>m>>s){
len = s.length();
memset(ss.m, 0, sizeof(ss.m));
for(int i = 0; i < len; i++){//灯的矩阵,以列来储存
ss.m[i][0] = s[i] - '0';
}
memset(b.m, 0, sizeof(b.m));
b.m[0][0] = b.m[0][len-1] = 1;//这里开始构造需要的矩阵
for(int i = 1; i < len; i++){//注意这里是行为单位
b.m[i][i-1] = b.m[i][i] = 1;
}
mat c = pow(b, m);
c = mul(c, ss);//因为行为单位,所以这里是c在前,ss在后,遵从矩阵的乘法
for(int i = 0; i < len; i++){
cout<<c.m[i][0];//最后这里输出的是列,最后的结果是列
}
cout<<endl;
}
return 0;
}
如果有错误,欢迎指出
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)