矩阵快速幂（快速幂）模板题目Decoding Genome

110 阅读 0 评论 73 点赞

我是靠谱客的博主不安钢笔，最近开发中收集的这篇文章主要介绍矩阵快速幂（快速幂）模板题目Decoding Genome，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这类题目的难点在于，数据量大，需要用到高精度，也就是快速幂

矩阵的乘法与快速幂模板一：

const int mod = 1e9+7;
struct Matrix
{
LL num[N][N];
};
Matrix mul(Matrix p,Matrix q) {
Matrix ret;
for(int i=0; i<m; i++) for(int j=0; j<m; j++) {
ret.num[i][j] = 0;
for(int k=0; k<m; k++) {
ret.num[i][j] = (ret.num[i][j] + p.num[i][k] * q.num[k][j]) % mod;
}
}
return ret;
}

矩阵乘法与快速幂模板二：

ll c[N][N];
void mul(ll a[][N], ll b[][N])
{
memset(c, 0, sizeof(c));
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
for(int k=0;k<m;k++)
c[i][j] = (c[i][j]+c[i][k]+c[i][k])%mod;
memcpy(a,c,sizeof(c));
}

例题：

https://codeforces.com/group/vFwRVj9WjO/contest/328371/problem/H

#include <bits/stdc++.h>
#define M 1000000007
using namespace std;
typedef long long LL;
struct Matrix
{
LL num[64][64];
};
LL n;
int m,K;
LL G[64][64];
Matrix mul(Matrix p,Matrix q) {
Matrix ret;
for(int i=0; i<m; i++) for(int j=0; j<m; j++) {
ret.num[i][j] = 0;
for(int k=0; k<m; k++) {
ret.num[i][j] += p.num[i][k] * q.num[k][j];
ret.num[i][j] %= M;
}
}
return ret;
}
Matrix f()
{
Matrix ret, p;
memset(ret.num, 0, sizeof(ret.num));
for(int i=0; i<m; i++) ret.num[i][i] = 1; // 单位矩阵
for(int i=0; i<m; i++) for(int j=0; j<m; j++) p.num[i][j] = G[i][j]; // 不可以相连的矩阵
n--; // 注意这里减一，答案才正确
while(n)
{
if(n&1)
ret = mul(ret,p);
p = mul(p,p);
n >>= 1;
}
return ret;
}
int main()
{
while(scanf("%I64d%d%d",&n,&m,&K) == 3)
{
int i,j;
for(i=0; i<m; i++) for(j=0; j<m; j++) G[i][j] = 1;
// 最开始，所有的i和j都是可以连在一起的
while(K--)
{
char c1,c2;
int x,y;
scanf("%c %c",&c1,&c2);
x = c1>='a'&&c1<='z'?c1-'a':c1-'A'+26;
y = c2>='a'&&c2<='z'?c2-'a':c2-'A'+26;
G[x][y] = 0; // 这两个不可以连在一起
}
Matrix ansM = f();
LL ans = 0;
for(i=0; i<m; i++)
{
for(j=0; j<m; j++)
{
ans += ansM.num[i][j];
ans %= M;
}
}
printf("%I64dn",ans);
}
return 0;
}

第二个模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,j,k;
using namespace std;
#define N 100
#define MOD 1000000007
long long n;
int m;
int k;
int indice(char x)
{
if(x>='a' && x<='z') return x-'a';
else return x-'A'+26;
}//预处理字符转数字
long long c[N][N];
void cheng(long long a[][N],long long b[][N])
{
memset(c,0,sizeof(c));
for(int i=0; i<m; i++)
for(int j=0; j<m; j++)
for(int k=0; k<m; k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
memcpy(a,c,sizeof(c)); // 这一步看似没太大必要
}
long long res[N][N];
long long odd[N][N];
void pow(long long p)
{
memset(odd,0,sizeof(odd));
for(int i=0; i<m; i++)
odd[i][i]=1;
if(p==0) // 如果是零次方，直接返回单位矩阵
{
memcpy(res,odd,sizeof(odd));
return;
}
while(p>1) // 开始计算
{
if(p&1)
cheng(odd,res);
cheng(res,res);
p/=2;
}
cheng(res,odd);
}
string s;
int main()
{
cin>>n>>m>>k;
for(int i=0; i<m; i++)
for(int j=0; j<m; j++)
res[i][j]=1;
for(int i=0; i<k; i++)
{
cin>>s;
res[indice(s[0])][indice(s[1])]=0;
}
n--;
pow(n);
long long cont=0;
for(int i=0; i<m; i++)
for(int j=0; j<m; j++)
cont=(cont+res[i][j])%MOD;
cout<<cont<<endl;
return 0;
}