矩阵乘法板子题

链接：https://ac.nowcoder.com/acm/problem/14607
来源：牛客网

题目描述
JYM和XJ转眼就从小学上了高中。在学习递推的时候，JYM在纸上随手写了一个递推关系式：an=2an-1，a0=0。写完这个递推式，JYM拿给XJ看，XJ觉得太过简单，于是大笔一挥，在等式右边又加了一个式子，变成了这样：an=2an-1+n2。JYM看到这个式子，想要算几个项来看看，可是一算就发现这个数据量太大了，你能帮他解决这个问题吗？
输入描述:

输入数据有多组（不超过100组数据），每组数据包含一个整数N<=1018

输出描述:

一个整数X，表示递推式第n项的值。由于数字太大，因此结果对于1000000009取模后输出。

示例1
输入
复制

0
1
2
3

输出
复制

0
1
6
21

题目分析：直接矩阵快速幂
解析：去构造一个中转矩阵即可，利用凑配，添加两个元素，n,和1，使得n^2 和 (n+1)^2 能够顺利递推

下面是代码：

#include<queue>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<memory.h>
using namespace  std;
typedef long long ll;
const ll N = 100;
const ll Mod = 1000000009;
ll F[N][N], zz[N][N] = {};
void multi(ll a[][N], ll b[][N], int n1, int n2, int kn)// n1是前行 n2是后列 kn是中间相同的
{
    ll temp[N][N];
    for (int i = 1; i <= n1; i++)
    {
        for (int j = 1; j <= n2; j++)
        {
            ll sum = 0;
            for (int k = 1; k <= kn; k++)
            {
                sum =sum%Mod+(a[i][k] % Mod * b[k][j] % Mod) % Mod;
            }
            temp[i][j] = sum % Mod;
        }
    }

    for (int i = 1; i <= n1; i++)
    {
        for (int j = 1; j <= n2; j++)
        {
            a[i][j] = temp[i][j];
        }
    }
}
ll ans[N][N];
void matrixFasePower(ll a[N][N], ll power, int n)
{
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i <= n; i++)//自定义单位矩阵
        ans[i][i] = 1;
    while (power > 0)
    {
        if (power & 1)
        {
            multi(ans, a, n, n, n);//n1 n2 k 
        }
        power >>= 1;
        multi(a, a, n, n, n);
    }
}
void init()
{
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            zz[i][j] = 0;
    zz[1][3] = zz[3][3] = zz[4][4] = zz[5][5]= zz[4][5] = 1;
    zz[1][1] = zz[2][1] = zz[3][4]=zz[1][4] = 2;
    zz[3][5]=zz[1][5] =  -1;

    F[1][1] = 1;
    F[2][1] = 0;
    F[3][1] = 1;
    F[4][1] = 2;
    F[5][1] = 1;

}
int main()
{
    ll power;

    while (cin >> power)
    {
        init();
        if (power == 0)//矩阵快速幂要记得特判
        {
            cout << 0 << endl;
            continue;
        }
        matrixFasePower(zz, power - 1, 5);//把转移矩阵^power 变成ans矩阵  最后乘一下 选第一个出结果
        //幂处理完 两个相*
        multi(ans, F, 5, 1, 5);
        cout << ans[1][1] % Mod << endl;
    }

}