HDU 2604 Queuing（矩阵快速幂）

题目链接：Queuing

题意：有一支$2^L$长度的队伍，队伍中有female和male，求$2^L$长度的队伍中除 fmf 和 fff 的队列有多少。

题解：先推导递推式：$f[i]=f[i-1]+f[i-3]+f[i-4]$

当前为f：

前一个为f（ff），那么再前一个只能为m（mff），再前一个也只能为m（mmff），即从$f[i-4]$转移过来；

前一个为m（mf），那么再前一个只能为m（mmf），即从$f[i-3]$转移过来。

当前为m：

前一个为m和f均可，即从$f[i-1]$转移过来。

推导出来啦。构造下矩阵就可以啦。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define N 4

 using namespace std;

 typedef long long ll;

 struct mat

 {

     ll m[N][N]=

     {

      {,,,},

      {,,,},

      {,,,},

      {,,,},

     };

 };

 mat mul(mat a,mat b,ll p)

 {

     mat ans;

     int i,j,k;

     for(i=;i<N;i++)

     for(j=;j<N;j++)

     ans.m[i][j]=;

     for(i=;i<N;i++)

     for(j=;j<N;j++)

     for(k=;k<N;k++)

     ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%p;

     return ans;

 }

 ll matpow(ll n,ll p)

 {

     mat ans,tmp;

     int i,j;

     for(int i=;i<N;i++)

     for(int j=;j<N;j++)

     ans.m[i][j]=;

     ans.m[][]=;ans.m[][]=;

     ans.m[][]=;ans.m[][]=;

     n-=;

     while(n)

     {

         if(n&) ans=mul(ans,tmp,p);

         tmp=mul(tmp,tmp,p);

         n=n>>;

     }

     return ans.m[][]%p;

 }

 int main(){

     ll L,M;

     while(scanf("%lld%lld",&L,&M)!=EOF){

         if(L==){

             printf("%lld\n",%M);

             continue;

         }

         else if(L==){

             printf("%lld\n",%M);

             continue;

         }

         else if(L==){

             printf("%lld\n",%M);

             continue;

         }

         else if(L==){

             printf("%lld\n",%M);

             continue;

         }

         printf("%lld\n",matpow(L,M));

     }

     return ;

 }

巴特西

HDU 2604 Queuing（矩阵快速幂）

最新文章

热门文章