模板
//用二维vector来表示矩阵
typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
const int M=10000;
//计算A*B
mat mul(mat &A, mat &B){
//根据线代相乘后的矩阵的行数=A的行数，列数=B的列数
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
for(int j;j<B[0].size();j++) {
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
}
return C;
}
//计算A^n
mat pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
//一看就是单位阵
for(int i=0;i<A.size();i++)
B[i][i]=1;
while(n){
if(n&1)
B=mul(B,A);
A=mul(A,A);
n>>=1;
}
return B;
}
//输入
ll n;
void solve(){
mat A(2,vec(2));
//初始化A
A=pow(A,n);
printf("");
}
例题
1.Blocks
其实刚开始看这道题的时候有点懵逼，看了白书的题解更加懵逼，不过看多了貌似就有点懂了
我们从左边第一个开始按顺序染色，设染到第i个方块为止，红绿都是偶数的方案数为ai，红绿恰有一个是偶数的方案数为bi，红绿都是奇数的方案数为ci。这样，染到第i+1个方块为止，红绿都是偶数的方案数有以下两种可能：a(i+1)=2*ai+bi
1.到第i个方块为止红绿都是偶数，并且第i+1个方块染成了蓝色或黄色//ai+ai（前面偶数+蓝色或前面偶数+黄色）
2.到第i个方块为止红绿恰有一个是奇数，并且第i+1个方块染成了奇数个对应的那种颜色//bi（已经固定了）b(i+1)=2ai+2bi+2*ci
1.到第i个方块为止红绿都是偶数，并且第i+1个方块染成了红色或绿色//ai+ai（前面偶数+蓝色或前面偶数+黄色）
2.到第i个方块为止红绿恰有一个是奇数，并且第i+1个方块染成了黄色或蓝色//bi+bi
3.到第i个方块为止红绿都是奇数，并且第i+1个方块染成了红色或绿色//ci+cic(i+1)=bi+2*ci
1.到第i个方块为止红绿恰有一个是奇数，并且第i+1个方块染成了偶数个对应的那种颜色//bi（已经固定了）
2.到第i个方块为止红绿都是奇数，并且第i+1个方块染成了黄色或蓝色//ci+ci
构建矩阵
因为刚开始为0，此时绿色和红色均为偶数，所以初始矩阵如图；
代码
#include <iostream>
#include <cstdio>
//用二维vector来表示矩阵
#include <vector>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
const int M=10007;
//计算A*B
mat mul(mat &A, mat &B){
//根据线代相乘后的矩阵的行数=A的行数，列数=B的列数
mat C(A.size(),vec(B[0].size()));
for(int i=0;i<A.size();i++)
for(int k=0;k<B.size();k++)
for(int j=0;j<B[0].size();j++) {
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M;
}
return C;
}
//计算A^n
mat pow(mat A,ll n){
mat B(A.size(),vec(A.size()));
//一看就是单位阵
for(int i=0;i<A.size();i++)
B[i][i]=1;
while(n){
if(n&1)
B=mul(B,A);
A=mul(A,A);
n>>=1;
}
return B;
}
//输入
ll n;
int a[3][3]={
2,1,0,
2,2,2,
0,1,2
};
int main(){
int T;
mat A(3,vec(3));
mat E(3,vec(1));
scanf("%d",&T);
while(T--){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
A[i][j]=a[i][j];
// E[0][0]=1;E[1][0]=0;E[2][0]=0;
scanf("%lld",&n);
A=pow(A,n);
// A=mul(A,E);
cout<<A[0][0]<<endl;
}
return 0;
}
有一点搞不懂的就是为什么不能加一个A=mul(A,E)!!我打算zuo一回，debug一下！
这里有一个比较隐蔽的错误。
你再while(T--)的外面定义了 mat A(3, vec(3))，即A是一个33的矩阵。但是当你在whilie(T--)里，A=mul(A,E)的时候， mul()返回的是一个新的矩阵，比如这道题里，返回的是一个31的矩阵，即，A的size已经变了，当你再度for:for:A[i][j]=a[i][j]的时候，已然越界，而且其实已经无法再pow(A,n)了（因为不再是n*n的方阵），后面当然也都就错误了。
2.图中长度为k的路径的计数
Problem Desciption
题目给出一个有n个节点的有向图，求该有向图中长度为k的路径条数。方便起见，节点编号为1,2,…,n，用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500.Input
每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n和Ｋ。接下来n行n列为该图的邻接矩阵。Output
输出一个整数，即为图中长度为k的路径的条数。样例输入
4 2
0 1 1 0
0 0 1 0
0 0 0 1
1 0 0 0样例输出
6Explain
假设从Ｕ出发到Ｖ的长度为Ｋ的路径总数为Ｇｋ［Ｕ］［Ｖ］，那么ｋ＝１时和边值相同，因此Ｇ１就等于图的邻接矩阵．
假设已经得到Ｇｋ１和Ｇｋ２，那么Ｇ（ｋ１＋ｋ２） ＝ Ｇｋ１＊Ｇｋ２．
Ｇｋ ＝ （Ｇ１）＾ｋ．
最终的结果就是G k里面所有数之和
3.Matrix Power Series
题解参考
白书解释
代码
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
ll n,m;
//input
mat multi(mat A,mat B){
mat e(2*n,vec(2*n));
for(int i=0;i<2*n;i++)
for(int j=0;j<2*n;j++)
for(int k=0;k<2*n;k++)
e[i][j]=(e[i][j]+A[i][k]*B[k][j])%m;
return e;
}
mat pow(mat A,ll q){
mat E(2*n,vec(2*n));
for(int i=0;i<2*n;i++)
E[i][i]=1;
while(q){
if(q&1){
E=multi(E,A);
}
A=multi(A,A);
q>>=1;
}
return E;
}
int main(){
ll k;
//freopen("data","r",stdin);
scanf("%lld%lld%lld",&n,&k,&m);
mat A(2*n,vec(2*n));
mat B(n,vec(n));
for(int i=0;i<n;i++)
B[i][i]=1;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&A[i][j]);
A[i+n][j]=A[i+n][j+n]=B[i][j];
//B[i][j]=1;
}
A=pow(A,k+1);
for(int i=0;i<2*n;i++)
{
for(int j=0;j<n;j++)
cout<<A[i][j]<<" ";
cout<<endl;
}
//整个过程是对左下方的数做计算
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
int a=A[n+i][j]%m;
if(i==j)
a=(a+m-1)%m;//就相当于-1啦
printf("%d%c",a,j+1==n?'\n':' ');
}
return 0;
}
网友评论