HDU - 4965 Fast Matrix Calculation 【矩阵快速幂】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4965

题意

给出两个矩阵一个A: n * k 一个B: k * n

C = A * B

M = (A * B) ^ (n * n)

然后将M中所有的元素对6取余后求和

思路

矩阵结合律。。

M = (A * B) * (A * B) * (A * B) * (A * B) * (A * B) * (A * B) * (A * B) * (A * B) ……

其实也等价于

M = A * (B * A) * (B * A) * (B * A) * (B * A) * (B * A) * (B * A) * B

因为 n 比较大 k 比较小

如果用 (A * B) 做矩阵快速幂的话，会T

所有用 B * A 做矩阵快速幂最后左乘A 再右乘B 就可以了

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <list>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

#define bug puts("***bug***");

#define fi first

#define se second

//#define bug

//#define gets gets_s

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair <string, int> psi;

typedef pair <string, string> pss;

typedef pair <double, int> pdi;

const double PI = acos(-1.0);

const double EI = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + 10;

const int MOD = 6;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

struct Matrix

{

    int a[10][10];

    int n;

    Matrix() {}

    Matrix operator * (Matrix const &b)const

    {

        Matrix res;

        res.n = n;

        CLR(res.a, 0);

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                for (int k = 0; k < n; k++)

                    res.a[i][j] = (res.a[i][j] + this->a[i][k] * b.a[k][j]) % MOD;

        return res;

    }

};

Matrix pow_mod(Matrix base, int a, int n)

{

    Matrix ans;

    CLR(ans.a, 0);

    for (int i = 0; i < n; i++)

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

    ans.n = n;

    while (a > 0)

    {

        if (a & 1)

            ans = ans * base;

        base = base * base;

        a >>= 1;

    }

    return ans;

}

int A[maxn][maxn], B[maxn][maxn], ans[maxn][maxn];

int main()

{

    int n, k;

    while (scanf("%d%d", &n, &k) && (n || k))

    {

        for (int i = 0; i < n; i++)

            for (int j = 0; j < k; j++)

                scanf("%d", &A[i][j]);

        for (int i = 0; i < k; i++)

            for (int j = 0; j < n; j++)

                scanf("%d", &B[i][j]);

        Matrix base;

        base.n = k;

        CLR(base.a, 0);

        for (int i = 0; i < k; i++)

            for (int j = 0; j < k; j++)

                for (int l = 0; l < n; l++)

                    base.a[i][j] = (base.a[i][j] + B[i][l] * A[l][j]) % MOD;

        base = pow_mod(base, n * n - 1, k);

        CLR(ans, 0);

        for (int i = 0; i < k; i++)

            for (int j = 0; j < n; j++)

                for (int l = 0; l < k; l++)

                    ans[i][j] = (ans[i][j] + base.a[i][l] * B[l][j]) % MOD;

        CLR(B, 0);

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                for (int l = 0; l < k; l++)

                    B[i][j] = (B[i][j] + A[i][l] * ans[l][j]) % MOD;

        int tot = 0;

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                tot += B[i][j];

        cout << tot << endl;

    }

}

巴特西

HDU - 4965 Fast Matrix Calculation 【矩阵快速幂】

最新文章

热门文章