HDU 2604 Queuing（矩阵高速幂）-白红宇

HDU 2604 Queuing（矩阵高速幂）

阅读量：5156 次

发布时间：2019-06-13

本文共 1524 字，大约阅读时间需要 5 分钟。

题目地址：

这题仅仅要推出公式来，构造矩阵就非常easy了。问题是推不出公式来。。TAT。。

从递推的思路考虑。用f(n)表示n个人满足条件的结果。假设最后一个是m则前n-1人能够随意排列，有f(n-1)种；假设是f，则考虑后两位mf和ff，没有一定满足或者一定不满足的状态，所以继续考虑一位，考虑后三位mmf, fmf, mff, fff，当中fmf和fff不符合条件。假设是mmf，则前n-3种能够随意排列，有f(n-3)种。假设是mff。则继续往前考虑一位。假设是fmff不符合条件，假设是mmff。前n-4能够随意排列。有f(n-4)种。

则推出递推公式：f(n)=f(n-1)+f(n-3)+f(n-4);

可是这样递推过去明显会超时，所以须要用矩阵来加速。

然后构造矩阵：

1,0,1,1

1,0,0,0

0,1,0,0

0,0,1,0

求矩阵的k-4次幂。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;int mod, a[6]={0,2,4,6,9};struct matrix{ int ma[5][5];}init, res;matrix Mult(matrix x, matrix y){ matrix tmp; int i, j, k; for(i=0;i<4;i++) { for(j=0;j<4;j++) { tmp.ma[i][j]=0; for(k=0;k<4;k++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp;}matrix Pow(matrix x, int k){ matrix tmp; int i, j; for(i=0;i<4;i++) for(j=0;j<4;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp;}int main(){ int i, j, k; while(scanf("%d%d",&k,&mod)!=EOF) { if(k<5) { printf("%d\n",a[k]%mod); continue ; } init.ma[0][0]=1; init.ma[0][1]=0; init.ma[0][2]=1; init.ma[0][3]=1; for(i=1;i<4;i++) { for(j=0;j<4;j++) { init.ma[i][j]=(i==j+1); } } res=Pow(init,k-4); int ans=0; for(i=0;i<4;i++) { ans=(ans+res.ma[0][i]*a[4-i])%mod; //printf("%d %d\n",ans,a[4-i]); } printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/cxchanpin/p/6795823.html

你可能感兴趣的文章

转：【Java并发编程】之十五：并发编程中实现内存可见的两种方法比较：加锁和volatile变量...