hdu2604（矩阵快速幂） - c++编程基础

题意：字符串只能由f和m两种字符构成，问长度为L且不出现子串fmf，fff的字符串有多少种.

解法：初始的矩阵应该是 mm 1 0 0 1 mm 。但是因为不能出现fmf，fff子串，所以fm和ff后面不能跟f
ff 0 1 1 0 ff
mf 1 0 0 1 mf
fm 0 1 1 0 fm

所以矩阵变化为：mm 1 0 0 1 mm

ff 0 1 1 0 ff
mf 1 0 0 1 mf
fm 0 1 1 0 fm

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=5; const int INF=1000000007; int M; struct Matrix { int num[Max][Max]; Matrix() { memset(num,0,sizeof num); } }; Matrix operator*(Matrix& a,Matrix& b) { Matrix ans; for(int k=0; k<4; k++) for(int i=0; i<4; i++) for(int j=0; j<4; j++) ans.num[i][j]=(ans.num[i][j]+a.num[i][k]*b.num[k][j])%M; return ans; } Matrix pow(Matrix a,int p) { Matrix ans; for(int i=0; i<4; i++) ans.num[i][i]=1; while(p) { if(p&1) ans=ans*a; a=a*a; p>>=1; } return ans; } int L; int main() { while(cin>>L>>M) { if(L<=2) { int tool=1; for(int i=0; i