欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

poj 3233 Matrix Power Series

程序员文章站 2022-07-03 21:30:32
Matrix Power Series思路题意比较简单,就是要求S(n)=∑i=1nAiS(n) = \sum _{i = 1} ^{n} A^ {i}S(n)=∑i=1n​Ai,显然有S(n)=S(n−1)∗A+AS(n) = S(n - 1) * A + AS(n)=S(n−1)∗A+A,看到这里,那就简单了,递推式,加矩阵,矩阵快速幂无疑了嘛,所以我们开始构造矩阵。显然有如下矩阵,EEE是单位矩阵,AAA是输入矩阵,OOO是零矩阵。[EEOA]∗[OOAO]\begin{bmatrix} E...

Matrix Power Series

思路

题意比较简单,就是要求S(n)=i=1nAiS(n) = \sum _{i = 1} ^{n} A^ {i},显然有S(n)=S(n1)A+AS(n) = S(n - 1) * A + A,看到这里,那就简单了,递推式,加矩阵,矩阵快速幂无疑了嘛,所以我们开始构造矩阵。

显然有如下矩阵,EE是单位矩阵,AA是输入矩阵,OO是零矩阵。

[EEOA][OOAO]\begin{bmatrix} E & E \\ O & A\end{bmatrix} * \begin{bmatrix} O & O\\ A & O \end{bmatrix}

通过这个矩阵的递推,我们就可以通过快速幂,达到快速求解的目的。

我严重怀疑这道题目数据有问题,long longlong\ longwawa,然后intint就过了???

AC代码

/*
  Author : lifehappy
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #include <bits/stdc++.h>

#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cmath>


#define mp make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')    f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

void print(ll x) {
    if(x < 10) {
        putchar(x + 48);
        return ;
    }
    print(x / 10);
    putchar(x % 10 + 48);
}

const int N = 70;

int n, k, mod;

struct matrix {
    int a[N][N];
    matrix operator * (const matrix & t) const {
        matrix temp;
        for(int i = 1; i <= 2 * n; i++) {
            for(int j = 1; j <= 2 * n; j++) {
                temp.a[i][j] = 0;
                for(int k = 1; k <= 2 * n; k++) {
                    temp.a[i][j] = (temp.a[i][j] + a[i][k] * t.a[k][j]) % mod;
                }
            }
        }
        return temp;
    }
}E, A, O;

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    n = read(), k = read(), mod = read();
    matrix fat, ans;
    for(int i = 1; i <= 2 * n; i++) {//先置零,
        for(int j = 1; j <= 2 * n; j++) {
            fat.a[i][j] = ans.a[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {//读入的时候置A加上置E矩阵。
        for(int j = 1; j <= n; j++) {
            fat.a[i + n][j + n] = ans.a[i + n][j] = read();
        }
        fat.a[i][i] = fat.a[i][i + n] = 1;
    }
    while(k) {
        if(k & 1) ans = fat * ans;
        fat = fat * fat;
        k >>= 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            printf("%d%c", ans.a[i][j], j == n ? '\n' : ' ');
        }
    }
	return 0;
}

调不出来的代码

写了一手逼格高一点的举证套矩阵的重载操作符的写法,可是太菜了,调不出来

/*
  Author : lifehappy
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #include <bits/stdc++.h>

#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cmath>


#define mp make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')    f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

void print(ll x) {
    if(x < 10) {
        putchar(x + 48);
        return ;
    }
    print(x / 10);
    putchar(x % 10 + 48);
}

const int N = 70;

int n, k, mod;

struct matrix {
    int a[N][N];
    matrix operator * (const matrix & t) const {
        matrix temp;
        for(int i = 1; i <= 2 * n; i++) {
            for(int j = 1; j <= 2 * n; j++) {
                temp.a[i][j] = 0;
                for(int k = 1; k <= 2 * n; k++) {
                    temp.a[i][j] = (temp.a[i][j] + a[i][k] * t.a[k][j]) % mod;
                }
            }
        }
        return temp;
    }

    matrix operator + (const matrix & t) const {
        matrix temp;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                temp.a[i][j] = (a[i][j] + t.a[i][j]) % mod;
            }
        }
        return temp;
    }
}E, A, O;

struct Matrix {
    matrix a[3][3];
    Matrix operator * (const Matrix & t) const {
        Matrix temp;
        for(int i = 1; i <= 2; i++) {
            for(int j = 1; j <= 2; j++) {
                temp.a[i][j] = O;
                for(int k = 1; k <= 2; k++) {
                    temp.a[i][j] = (a[i][k] * t.a[k][j]) + temp.a[i][j];
                }
            }
        }
    }
};

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    n = read(), k = read(), mod = read();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            A.a[i][j] = read();
            E.a[i][j] = O.a[i][j] = 0;
        }
        E.a[i][i] = 1;
    }
    Matrix fat, ans;
    fat.a[1][1] = E, fat.a[1][2] = E, fat.a[2][1] = O, fat.a[2][2] = A;
    ans.a[1][1] = O, ans.a[1][2] = O, ans.a[2][1] = A, ans.a[2][2] = O;
    while(k) {
        if(k & 1) ans = ans * fat;
        fat = fat * fat;
        k >>= 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            printf("%d%c", ans.a[1][1].a[i][j], j == n ? '\n' : ' ');
        }
    }
	return 0;
}

本文地址:https://blog.csdn.net/weixin_45483201/article/details/107555663

相关标签: 刷题