Covering HDU - 6185 （暴搜系数+矩阵快速幂）

先通过打表将前几项的结果得到，然后暴力搜索快速幂的系数，进行快速幂。（n是1e18，一开始竟然还在手推dp公式= =）

题意：

给你一个4 * n的地板，用1*2的砖头填，问填发数。

分析：

快速幂模板题

代码：

爆搜系数代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int v[8] = { 1, 5, 11, 36, 95, 281, 781, 2245 };

bool check(int x, int a, int b, int c, int d)
{
    return v[x] * a + v[x + 1] * b + v[x + 2] * c + v[x + 3] * d == v[x + 4];
}

int main()
{
    for (int a = -10; a <= 10; a++)
        for (int b = -10; b <= 10; b++)
            for (int c = -10; c <= 10; c++)
                for (int d = -10; d <= 10; d++)
                {
                    bool flag = true;
                    for (int t = 0; t <= 3; t++) if (!check(t, a, b, c, d)) flag = false;
                    if (flag) cout << a << " " << b << " " << c << " " << d << endl;
                }
    return 0;
}

题解代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
struct matrix
{
	ll v[4][4];
	void init()
	{
		memset(v, 0, sizeof(v));
		for(int i = 0; i < 4; i++)
			v[i][i] = 1;
	}
};
matrix operator *(const matrix& a, const matrix& b)
{
	matrix res; memset(res.v, 0, sizeof(res.v));
	for(int i = 0; i < 4; i++)
		for(int j = 0; j < 4; j++)
			for(int k = 0; k < 4; k++)
				res.v[i][j] = (res.v[i][j] + a.v[i][k] * b.v[k][j] + mod) % mod;
	return res;
}

matrix quick_pow(matrix a, ll n)
{
	matrix res; res.init();
	while(n)
	{
		if(n & 1) res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}
ll v[] = {0, 1, 5, 11, 36};

int main()
{
	ll n;
	matrix a; 
	memset(a.v, 0, sizeof(a.v));
	a.v[0][0] = 1, a.v[0][1] = 5, a.v[0][2] = 1, a.v[0][3] = -1;
	a.v[1][0] = a.v[2][1] = a.v[3][2] = 1;
	while(cin >> n)
	{
		if(n <= 4)
		{
			cout << v[n] << endl;
			continue;
		}
		matrix res = quick_pow(a, n - 4);
		ll sum = 0;
		for(int i = 0; i < 4; i++)
			sum = (sum + res.v[0][i] * v[4 - i] + mod) % mod;
		cout << sum << endl;
	}
}