HDU 2604 Queuing(矩阵快速幂)

时间:2023-03-09 17:34:26
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 ;
}