长度为 n 有男有女的队伍里没有 fmf 和 fff 的序列有多少
判断最后一个人无法得出结论
于是判断最后两人的递推式:
fm(n) = mm(n-1) //最后两人为fm的长度为n的队伍 只能由 mm(n-1)得到
mf(n) = fm(n-1)+ ff(n-1)
ff(n) = fm(n-1)
mm(n) = mf(n-1)+ mm(n-1)
最后S(n)=fm(n)+mf(n)+ff(n)+mm(n)；
|1 1 1 1 1| | S(n-1) | | S(n) |
|0 0 0 0 1| | fm(n-1)| | fm(n)|
|0 1 0 1 0| * | mf(n-1)| = | mf(n)|
|0 1 0 0 0| | ff(n-1)| | ff(n)|
|0 0 1 0 1| | mm(n-1)| | mm(n)|
剩下的就是矩阵快速幂了。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
struct P{
int a[][];
};
int b[]={,,,,};
int ans,n,mod;
P s,c;
P mult(P a,P b)
{
P c;
memset(c.a,,sizeof(c.a));
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
for(int k=;k<=;k++)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j] )%mod;
}
}
return c;
}
void ini()
{
memset(s.a,,sizeof(s.a));
memset(c.a,,sizeof(c.a));
s.a[][]=;
s.a[][]=; s.a[][]=;
s.a[][]=;
s.a[][]=; s.a[][]=;
}
void fuc(int n)
{
for(int i=;i<=;i++) c.a[i][i]=;
while(n)
{
if(n&)
{
c=mult(c,s);
}
s=mult(s,s);
n>>=;
}
}
int main()
{
while(~scanf("%d%d",&n,&mod))
{
if(n==)
{
puts("");
continue;
}
ini();
fuc(n-);
ans=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
ans=(ans+c.a[i][j]*b[j])%mod;
}
}
printf("%d\n",ans);
}
}