[HDU - 1575] Tr A

发表于 | 分类于 ，
本文字数： 17k

链接

\(\text{SPOJ - NO GCD}\)

题意

  A是一个方阵，\(Tr\space A\)表示\(A\)的迹(即是主对角线上的和)，现在要求\(Tr(A^k)\%9973\)

  输入格式：第一行为\(t\)，共\(t\)组测试样例，每组数据的一行两个数字\(n,k\)，接下来\(n\)行\(n\)列，表示方阵\(A\)

  输出格式：每组测试样例一行输出，输出\(Tr(A^k)\%9973\)

  数据范围：\(2\leq n\leq 10,2\leq k\leq 10^9\)

分析

  这是一个矩阵快速幂的模板题；

  对于\(\text{Successione di Fibonacci}\)，有：

  • \(f_{0}=0\)
  • \(f_{1}=1\)
  • \(f_{n}=f_{n-1}+f_{n-2}（n≧2）\)

  如果需要我们求出\(f_{1e9}\%(1e9+7)\)的结果，那么我们直接利用递推公式进行求解，显然是不可行的。

  定义\(F(n)=\begin{bmatrix} f_{n} & f_{n+1} \end{bmatrix}\)，且\(f_0=0,f_1=1,f_{n}=f_{n-1}+f_{n-2}（n≧2）\)，我们有：

\[ F(n)=\begin{bmatrix} f_{n} & f_{n+1}\end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n}\end{bmatrix}* \begin{bmatrix}0&1\\ 1 & 1\end{bmatrix}=\vdots=\begin{bmatrix} f_{0} & f_{1}\end{bmatrix}*\begin{bmatrix}0&1\\ 1 & 1\end{bmatrix}^{n}\]

  令\(A=\begin{bmatrix}0&1\\ 1 & 1\end{bmatrix}\)，则有\(F(n)=F(0)*A^{n}\)，实际上我们只要考虑求解\(A^n\)即可，如果这里的\(A\)是一个整数，那么我们直接快速幂即可，但是这里是一个矩阵。

  这里有涉及到广义快速幂的概念；

  \((G,*)\)是一个群（\(1.*\)在\(G\)上的运算是封闭的；\(2.\)满足交换律；\(3.\)对\(G\)中的任意元素含有唯一的单位元；\(4.\)除零元外均有逆元），\(*\)是一种二元运算（泛指），\(e\)为\(*\)在\(G\)上的单位元，\(a\in G\)，\(e*a=a*e=a\)，\((a^{-1})^{-1}=a\)，规定\(a^{0}=1,a^{-n}=(a^{n})^{-1}\)，可以证明\(a^{m}\cdot a^{n}=a^{m+n}\)，\((a^{m})^{n}=a^{mn}\)，那么关于它的快速幂可以这样写：

1
2
3
4
5
6
7
8
9
10
typename pow(typename a, int n) {
	//ans初始化为单位元
	typename ans = e;
	while (n) {
		if (n & 1) ans = ans * a;
		a = a * a;
		n >>= 1;
	}
	return ans;
}

  对于上面的\(A^n\)，那么\((G,*)\)是一个群，\(*\)为矩阵乘法，\(G\)元素为\(e、A、A^{2}、A^{3}\dots A^{\infty}\)，并且\(A\)是一个方阵，那么广义快速幂对于它来说也是成立的，注意\(A\)的单位元是单位矩阵。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 1000005
#define N 200005
#define MOD 9973
#define P 2


typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

const int maxn = 12;

int n, k;

struct Matrix {
    ll M[maxn][maxn];
    Matrix(const int I = 0){
        memset(M, 0, sizeof(M));
        if (I)
            for (int i = 1; i <= n; i++)
                M[i][i] = 1;
    }
    Matrix operator * (const Matrix & a) {
        Matrix t;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                    t.M[i][j] = (t.M[i][j] + M[i][k] * a.M[k][j]) % MOD;
        return t;
    }
};

Matrix pow(Matrix a, int b) {
    Matrix c(1);
    while (b) {
        if (b & 1) c = c * a;
        a = a * a;
        b >>= 1;
    }
    return c;
}
int t;
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> t;
    while (t--) {
        Matrix a;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> a.M[i][j];
        Matrix ans = pow(a, k);
        ll res = 0;
        for (int i = 1; i <= n; i++)
            res = (res + ans.M[i][i]) % MOD;
        cout << res << endl;
    }
}