华东交通大学2018年ACM“双基”程序设计竞赛 C. 公式题 (2) (矩阵快速幂)

题目链接：公式题 (2)

比赛链接：华东交通大学2018年ACM“双基”程序设计竞赛

题目描述

令f(n)=2f(n-1)+3f(n-2)+n,f(1)=1,f(2)=2

令g(n)=g(n-1)+f(n)+n*n,g(1)=2

告诉你n，输出g(n)的结果，结果对1e9+7取模

输入描述:

多组输入，每行一个整数n（1<=n<=1e9)，如果输入为0，停止程序。

输出描述:

在一行中输出对应g(n)的值，结果对1e9+7取模。

示例1

输入

输出

说明

多组输入，输入为0时，终止程序

备注:

项数极大，朴素算法无法在规定时间内得出结果

题解

矩阵快速幂

\[\left[
\begin{matrix}
g(n) \\
f(n) \\
f(n - 1) \\
n ^ 2 \\
n \\
1 \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
1 & 2 & 3 & 1 & 3 & 2 \\
0 & 2 & 3 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 2 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{matrix}
\right]
\left[
\begin{matrix}
g(n - 1) \\
f(n - 1) \\
f(n - 2) \\
(n - 1) ^ 2 \\
n - 1 \\
1 \\
\end{matrix}
\right]
\]

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 10 + 5;

const ll mod = 1e9 + 7;

struct Matrix {

    int n, m;

    ll a[maxn][maxn];

    Matrix(int n = 0, int m = 0) : n(n), m(m) {}

    void input() {

        for(int i = 1; i <= n; ++i) {

            for(int j = 1; j <= m; ++j) {

                scanf("%lld", &a[i][j]);

            }

        }

    }

    void output() {

        for(int i = 1; i <= n; ++i) {

            for(int j = 1; j <= m; ++j) {

                printf("%lld", a[i][j]);

                printf("%s", j == m? "\n": " ");

            }

        }

    }

    void init() {

        memset(a, 0, sizeof(a));

    }

    void unit() {

        if(n == m) {

            init();

            for(int i = 1; i <= n; ++i) {

                a[i][i] = 1;

            }

        }

    }

    Matrix operator *(const Matrix b) {

        Matrix c(n, b.m);

        c.init();

        for(int i = 1; i <= c.n; ++i) {

            for(int k = 1; k <= m; ++k) {

                for(int j = 1; j <= c.m; ++j) {

                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % mod;

                }

            }

        }

        return c;

    }

    Matrix qmod(ll b) {

        if(n == m) {

            Matrix a = *this;

            Matrix ans = Matrix(n, n);

            ans.unit();

            if(!b) return ans;

            while(b) {

                if(b & 1) ans = ans * a;

                a = a * a;

                b >>= 1;

            }

            return ans;

        }

    }

};

int main() {

    int n;

    while(~scanf("%d", &n) && n) {

        if(n == 1) printf("2\n");

        else if(n == 2) printf("8\n");

        else {

            Matrix m(6, 6);

            m.init();

            m.a[1][1] = 1; m.a[1][2] = 2; m.a[1][3] = 3; m.a[1][4] = 1; m.a[1][5] = 3; m.a[1][6] = 2;

            m.a[2][2] = 2; m.a[2][3] = 3; m.a[2][5] = 1; m.a[2][6] = 1;

            m.a[3][2] = 1;

            m.a[4][4] = 1; m.a[4][5] = 2; m.a[4][6] = 1;

            m.a[5][5] = 1; m.a[5][6] = 1;

            m.a[6][6] = 1;

            Matrix ans(6, 1);

            ans.a[1][1] = 8;

            ans.a[2][1] = 2;

            ans.a[3][1] = 1;

            ans.a[4][1] = 4;

            ans.a[5][1] = 2;

            ans.a[6][1] = 1;

            ans = (m.qmod(n - 2)) * ans;

            printf("%lld\n", ans.a[1][1]);

        }

    }

    return 0;

}

巴特西

华东交通大学2018年ACM“双基”程序设计竞赛 C. 公式题 (2) (矩阵快速幂)

题目描述

输入描述:

输出描述:

示例1

备注:

题解

代码

最新文章

热门文章