HDU 2604 Queuing （矩陣快速冪）

HDU 2604 Queuing （矩陣快速冪）

ACM

題目地址：HDU 2604 Queuing

題意：
n個人排隊，f表示女，m表示男，包含子串‘fmf’和‘fff’的序列為O隊列，否則為E隊列，有多少個序列為E隊列。

分析：
矩陣快速冪入門題。
下面引用巨巨解釋：

用f(n)表示n個人滿足條件的結果，那麼如果最後一個人是m的話，那麼前n-1個滿足條件即可，就是f(n-1)；
如果最後一個是f那麼這個還無法推出結果，那麼往前再考慮一位：那麼後三位可能是：mmf, fmf, mff, fff，其中fff和fmf不滿足題意所以我們不考慮，但是如果是
mmf的話那麼前n-3可以找滿足條件的即：f(n-3)；如果是mff的話，再往前考慮一位的話只有mmff滿足條件即：f(n-4)
所以f(n)=f(n-1)+f(n-3)+f(n-4)，遞推會跪，可用矩陣快速冪
構造一個矩陣：

矩陣快速冪和普通的快速冪原理是一樣的，如果不懂可以先去補補快速冪。

代碼：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2604.cpp
*  Create Date: 2014-08-02 21:20:18
*  Descripton:  matrix 
*/

#include 
#include 
#include 
#include 
using namespace std;
#include 
#include 
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long ll;

const int N = 0;
const int SIZE = 4;

int l, MOD;

struct Mat{
	ll v[SIZE][SIZE];	// value of matrix

	Mat() {
		memset(v, 0, sizeof(v));
	}

	void init(ll _v) {
		repf (i, 0, SIZE)
			v[i][i] = _v;
	}
};

Mat operator * (Mat a, Mat b) {
	Mat c;
	repf (i, 0, SIZE - 1) {
		repf (j, 0, SIZE - 1) {
			c.v[i][j] = 0;
			repf (k, 0, SIZE - 1) {
				c.v[i][j] += (a.v[i][k] * b.v[k][j]) % MOD;
				c.v[i][j] %= MOD;
			}
		}
	}
	return c;
}

Mat operator ^ (Mat a, ll k) {
	Mat c;
	c.init(1);
	while (k) {
		if (k&1) c = a * c;
		a = a * a;
		k >>= 1;
	}
	return c;
}

int main() {
	Mat a, b, c;
	// a
	a.v[0][0] = 9;
	a.v[1][0] = 6;
	a.v[2][0] = 4;
	a.v[3][0] = 2;
	
	// b
	b.v[0][0] = b.v[0][2] = b.v[0][3] = b.v[1][0] = b.v[2][1] = b.v[3][2] = 1;

	while (~scanf("%d%d", &l, &MOD)) {
		if (l == 0) {
			puts("0");
		} else if (l <= 4) {
			printf("%lld\n", a.v[4 - l][0] % MOD);
		} else {
			c = b ^ (l - 4);
			c = c * a;
			printf("%lld\n", c.v[0][0] % MOD);
		}
	}

	return 0;
}