本文主要是介绍HDU-2604（递推+矩阵快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 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.
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.
3 8 4 7 4 8
6 2 1
/*
题意：
输入一个L和M表示有2^L个人在排队，
队列有male和famale分别用f和m替换
当队列出现fff或fmf此时这个队列就是一个O-queue
其他情况就是E-queue，列如当L=2时，有4种排列，
分别为ff，fm，mf，mm不存在O-queue，所以
E-queue的数量就是4种，你的任务是求：
E-queue的数量%M题解：递推+矩阵快速幂
根据题目的意思，我们可以求出F[0] = 0 , F[1] = 2 , F[2] = 4 , F[3] = 6 , F[4] = 9 , F[5] = 152 那么根据上面前5项我们可以求出n >= 5的时候 F[n] = F[n-1]+F[n-3]+F[n-4]那么我们就可以构造出矩阵| 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] |*/
#include <stdio.h>
#include <string.h>
#include<iostream>
#include <algorithm>
#include<math.h>
#include<map>
using namespace std;struct node
{long long int maxtri[6][6];
};
node res, roi;
int l, kk;node operator * (node &a, node &b)
{node ans;memset(ans.maxtri, 0, sizeof(ans.maxtri));for (int k = 0; k < 4; k++){for (int i = 0; i < 4; i++){for (int j = 0; j < 4; j++){ans.maxtri[i][j] += a.maxtri[i][k] * (b.maxtri[k][j] % kk) % kk;}}}return ans;
}void quickmuti(int nn)
{node temp;for (int i = 0; i < 4; i++){for (int j = 0; j < 4; j++){temp.maxtri[i][j] = (i == j);}}while (nn){if (nn & 1){temp = temp*roi;}nn >>= 1;roi = roi*roi;}res = res*temp;
}void init()
{memset(roi.maxtri, 0, sizeof(roi.maxtri));memset(res.maxtri, 0, sizeof(res.maxtri));roi.maxtri[0][0] = roi.maxtri[0][1]= roi.maxtri[1][2] = roi.maxtri[2][0]= roi.maxtri[2][3] = roi.maxtri[3][0]= 1;res.maxtri[0][0] = 9;res.maxtri[0][1] = 6;res.maxtri[0][2] = 4;res.maxtri[0][3] = 2;
}int main()
{while (cin >> l >> kk){init();if (l == 0){cout << '0' << endl;continue;}else if (l <= 4){cout << res.maxtri[0][(4 - l)] % kk << endl;continue;}quickmuti(l - 4);cout << res.maxtri[0][0] % kk << endl;}return 0;
}
这篇关于HDU-2604（递推+矩阵快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
