Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2 L numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.
Input
Input a length L (0 <= L <= 10 6) and M.
Output
Output K mod M(1 <= M <= 30) where K is the number of E-queues with length L.
Sample Input
3 8
4 7
4 8
Sample Output
6
2
1 题意：就是给你这个字符串的长度L，这个字符串只能由f和m组成，让你用这两个字母来构造各种字符串，但是里面不能出现fmf或fff，求这个L长度里面不出现fmf和fff的字符串个数，最后在取余m 我感觉这个题拿到的时候不知道怎么去下手，不像之前的快速幂，那些递推公式题目相当于直接告诉你了，但是这个还要推出来 既然是快速幂做的，那么肯定是后项是由前项有某种关系组成的 例如已知长度为7的串的答案，那么8怎么推出来 8就比7多出来一个字母，我们那么8可以看作在7后面加了一个字符 当在7后面加一个m的话，那么就不会影响原串 但是如果加一个f，那么8这个串后面三个之能是mmf、mff 当为mmf的话，相当于这三个不会受到前面字符的影响，相应的它也不会影响前面的字符 当为mff倒数第四个只能是m，二且这样的话也不会影响前面 所以这样递推公式就出来了 | 1 0 1 1 | * | F(n-1) | = | F(n) | | 1 0 0 0 | | F(n-2) | | F(n-1) | | 0 1 0 0 | | F(n-3) | | F(n-2) | | 0 0 1 0 | | F(n-4) | | F(n-3) | 上代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=15;
7 typedef long long ll;
8 ll n=7,mod;
9 ll e[maxn][maxn],v[maxn][maxn],w[maxn][maxn];
10 void mul(ll a[maxn][maxn],ll b[maxn][maxn])
11 {
12
13 memset(e,0,sizeof(e));
14 for(ll i=1;i<=n;++i)
15 {
16 for(ll j=1;j<=n;++j)
17 {
18 ll sum=0;
19 for(ll k=1;k<=n;++k)
20 {
21 sum=(sum%mod+(a[i][k]*b[k][j])%mod)%mod;
22 }
23 e[i][j]=sum;
24 }
25 }
26 for(ll i=1;i<=n;++i)
27 {
28 for(ll j=1;j<=n;++j)
29 {
30 a[i][j]=e[i][j];
31 }
32 }
33 }
34 void pow(ll b)
35 {
36 for(ll i=1;i<=n;++i)
37 {
38 w[i][i]=1;
39 }
40 while(b)
41 {
42 if(b&1)
43 {
44 mul(w,v);
45 }
46 mul(v,v);
47 b>>=1;
48 }
49 }
50 int main()
51 {
52 ll a,b;
53 while(~scanf("%lld%lld",&a,&b))
54 {
55 mod = b;
56 memset(w,0,sizeof(w));
57 memset(v,0,sizeof(v));
58 if(a==1)
59 {
60 int c=2%mod;
61 printf("%d\n",c);
62 continue;
63 }
64 else if(a==2)
65 {
66 int c=4%mod;
67 printf("%d\n",c);
68 continue;
69 }
70 else if(a==3)
71 {
72 int c=6%mod;
73 printf("%d\n",c);
74 continue;
75 }
76 else if(a==4)
77 {
78 int c=9%mod;
79 printf("%d\n",c);
80 continue;
81 }
82 else if(a==0)
83 {
84 printf("0\n");
85 continue;
86 }
87 //0 2 4 6 9
88 v[1][1]=1;v[1][2]=0;v[1][3]=1;v[1][4]=1;
89 v[2][1]=1;v[2][2]=0;v[2][3]=0;v[2][4]=0;
90 v[3][1]=0;v[3][2]=1;v[3][3]=0;v[3][4]=0;
91 v[4][1]=0;v[4][2]=0;v[4][3]=1;v[4][4]=0;
92 pow(a-4);
93 ll sum=(w[1][1]*9+w[1][2]*6+w[1][3]*4+w[1][4]*2)%mod;
94 printf("%lld\n",sum);
95 }
96 return 0;
97 }
View Code