Question

矩阵乘法的经典题目

Answer 1

VOJ1067
我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。
给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。 #include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#define N 10using namespace std;const int mod = 7777777;typedef long long LL;struct matrix{  LL a[10][10];}origin;int n,m;matrix multiply(matrix x,matrix y){   matrix temp;  memset(temp.a,0,sizeof(temp.a));   for(int i=0;i<n;i++){      for(int j=0;j<n;j++){         for(int k=0;k<n;k++){            temp.a[i][j]+=x.a[i][k]*y.a[k][j];            temp.a[i][j]=(temp.a[i][j])%mod;         }      }   }   return temp;}matrix matmod(matrix A,int k){   matrix res;   memset(res.a,0,sizeof res.a); for(int i=0;i<n;i++) res.a[i][i]=1; while(k){    if(k&1) res=multiply(res,A);    k>>=1;    A=multiply(A,A); } return res;}void print(matrix x){   for(int i=0;i<n;i++){      for(int j=0;j<n;j++)      cout<< <<x.a[i][j];puts();   }   printf(---------------\n);}int main(){  int k;  while(cin>>n>>k){    memset(origin.a,0,sizeof origin.a);    origin.a[0][0]=1;    for(int i=1;i<=n;i++){      origin.a[i][0]=1;      for(int j=0;j<i;j++){        origin.a[i][0]+=origin.a[j][0];      }    }     // print(origin);    matrix res;    memset(res.a,0,sizeof res.a);    for(int i=0;i<n-1;i++){      res.a[i][i+1]=1;   }    for(int i=0;i<n;i++) res.a[n-1][i]=1;    //print(res);    res=matmod(res,k-1);    LL fans=0;    for(int i=0;i<n;i++){      fans+=res.a[0][i]*origin.a[i][0];      fans%=mod;    }    cout<<fans<<endl;  }  return 0;}经典题目9
用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果
我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。
经典题目10
POJ2778
题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。
下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。
最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
Matrix67原创，转贴请注明出处。 #include <cstdio>#define SIZE (1<<m)#define MAX_SIZE 32using namespace std;class CMatrix{public:long element[MAX_SIZE][MAX_SIZE];void setSize(int);void setModulo(int);CMatrix operator* (CMatrix);CMatrix power(int);private:int size;long modulo;};void CMatrix::setSize(int a){for (int i=0; i<a; i++)for (int j=0; j<a; j++)element[i][j]=0;size = a;}void CMatrix::setModulo(int a){modulo = a;}CMatrix CMatrix::operator* (CMatrix param){CMatrix product;product.setSize(size);product.setModulo(modulo);for (int i=0; i<size; i++)for (int j=0; j<size; j++)for (int k=0; k<size; k++){product.element[i][j]+=element[i][k]*param.element[k][j];product.element[i][j]%=modulo;}return product;}CMatrix CMatrix::power(int exp){CMatrix tmp = (*this) * (*this);if (exp==1) return *this;else if (exp & 1) return tmp.power(exp/2) * (*this);else return tmp.power(exp/2);}int main(){const int validSet[]={0,3,6,12,15,24,27,30};long n, m, p;CMatrix unit;scanf(%d%d%d, &n, &m, &p);unit.setSize(SIZE);for(int i=0; i<SIZE; i++)for(int j=0; j<SIZE; j++)if( ((~i)&j) == ((~i)&(SIZE-1)) ){bool isValid=false;for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];unit.element[i][j]=isValid;}unit.setModulo(p);printf(%d, unit.power(n).element[SIZE-1][SIZE-1] );return 0;}