[原创]HDU 2604 Queuing [递推]【矩阵快速幂】

2016-08-11 17:19:07 Tabris_ 阅读数：317

博客爬取于2020-06-14 22:43:54
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52184669

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2604
--------------------.
Queuing

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4713 Accepted Submission(s): 2083

Problem Description
Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.
这里写图片描述

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 2L 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

Author
WhereIsHeroFrom

-----------------------------------.

题目大意 ：就是问子串中没有fmf fff的串有多少个

题解 ： 我是暴力打表找的规律

所以不解释

这是打表代码
-------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
typedef __int64 LL;
# define maxn 10
int sum=0;
char a[12];
void judge(int n,int mm)
{
	int m=n;
	memset(a,0,sizeof(a));
	int num=0;
	while(mm--)
	{
		if(n&1) a[num++]='1';
		else    a[num++]='0';
		n>>=1;
	}
	//printf("%.4d %s  ",m,a);
	if(strstr(a,"111")||strstr(a,"101"))
	{
//	printf("  ***");
	}else sum++;
	//puts("");
	return ;
}

 int M ;
void dfs(int n,int num)
{


	if(num == M-1)   {judge(n,M); return ;
	}
	n<<=1;
	dfs(n,num+1);
	dfs(n+1,num+1);


}
int main()
{
	for(int i=0;i<10;i++)
	{M = i;
	sum=0;
	dfs(0,-1);
	printf("%d  %d \n",i,sum);
	}
	return 0;
}

附本题AC代码
------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# include<bits/stdc++.h>
# include <stdio.h>   //为啥我先到的是数位DP 啊  0 1 两位 dp[1e6][0~1][pre]
# include <vector>     //打表找规律的题都是SB题目  上是打表代码
# include <iostream>
# include <stdlib.h>
using namespace std;
# define LL long long int
# define pb push_back

const int M = 4;
int MOD;

struct Matrix
{
    LL m[M][M];
    void clearO()
    {
        for(int i=0; i<M; i++) //初始化矩阵
            for(int j=0; j<M; j++)
                m[i][j]= 0;
    }
    void clearE()
    {
        for(int i=0; i<M; i++) //初始化矩阵
            for(int j=0; j<M; j++)
                m[i][j]= (i==j);
    }
    void display()
    {
        for(int i=0; i<M; i++)
            {
                for(int j=0; j<M; j++)
                printf("%d ",m[i][j]);
                puts("");
            }
    }
};

Matrix operator * (Matrix a,Matrix b)
{
    Matrix c;
    c.clearO();

    for(int k=0; k<M; k++)
        for(int i=0; i<M; i++) //实现矩阵乘法
        {
            if(a.m[i][k] <= 0)  continue;
            for(int j=0; j<M; j++)
            {
                if(b.m[k][j] <= 0)    continue;
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    return c;
}

Matrix operator ^ (Matrix a,LL b)
{
    Matrix c;
    c.clearE();
    while(b)
    {
        if(b&1) c= c * a ;
        b >>= 1;
        a = a * a ;
    }
    return c;
}

Matrix a,b;

void init()
{
    a.clearO();
    a.m[0][0]=9;
    a.m[1][0]=6;
    a.m[2][0]=4;
    a.m[3][0]=2;
    b.clearO();
    b.m[0][0]=1,b.m[0][2]=1,b.m[0][3]=1;
    b.m[1][0]=1,b.m[2][1]=1,b.m[3][2]=1;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        MOD = m;

        init();
        b=b^(n-1);
        a=b*a;
      //  a.display();
        printf("%I64d\n",a.m[3][0]);

    }
    return 0;
}