矩阵优化

数论

题面链接：HDU 6185:Covering

题意

求用 $1*2$ 的格子去填满 $4*n$ 的矩阵一共有多少种方法$（1 ≤ n ≤ 10 ^ {18}）$

分析

通过模板找出他们之间的关系式，然后对于该模板进行小细节的改动就OK（我这写的啥阿）

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
typedef long long LL;
const int M = 4;
const int base[M][M] =
{
    { 1, 5, 1, -1 },
    { 1, 0, 0, 0 },
    { 0, 1, 0, 0 },
    { 0, 0, 1, 0 },
};  //需要进行k次方的矩阵，通过关系式推出的矩阵方程
const int source[M][M] =
{
    { 36, 0, 0, 0 },
    { 11, 0, 0, 0 },
    { 5, 0, 0, 0 },
    { 1, 0, 0, 0 },
};  //用于存答案的矩阵
struct Mat  //矩阵
{
    int a[M][M];  //矩阵数据
    Mat()   //矩阵默认构造函数，初始化数据全0
    {
        memset(a, 0, sizeof(a));
    }
    Mat(const int g[M][M])  //有参构造函数，拷贝给定数组的元素作为矩阵数据
    {
        memcpy(a, g, sizeof(a));
    }
    void E()    //构造单位矩阵，这个如果要用，应该位于默认构造之后
    {
        for (int i = 0; i < M; i++)
            a[i][i] = 1;
    }
    Mat operator * (const Mat &b) const //重载矩阵乘法
    {
        Mat ret;
        for (int i = 0; i < M; i++)//此处要改M代表与M项相关
            for (int k = 0; k < M; k++)
            {
                if (a[i][k] == 0)
                    continue;
                for (int j = 0; j < M; j++)
                {
                    ret.a[i][j] += (LL)a[i][k] * b.a[k][j] % mod;
                    if (ret.a[i][j] >= mod)
                        ret.a[i][j] -= mod;
                    if (ret.a[i][j] < 0)
                        ret.a[i][j] += mod; //矩阵中用负数，取模要注意
                }
            }
        return ret;
    }
};
Mat bin(const Mat &a, LL k)
{
    Mat ret;
    ret.E();
    Mat res;
    res = a;
    while (k)
    {
        if (k & 1)
            ret = ret * res;
        res = res * res;
        k >>= 1;
    }
    return ret;
}
int main()
{
    LL n;
    while (~scanf("%lld", &n))
    {
        Mat ret = bin(Mat(base), n - 1);
        ret = ret * Mat(source);
        printf("%d\n", ret.a[3][0]);
    }
    return 0;
}