当前位置:首页 > 开发 > 移动开发 > 正文

HDU5015 233 Matrix(矩阵高速幂)

发表于: 2015-11-13   作者:互联网   来源:转载   浏览次数:
摘要: HDU5015 233 Matrix(矩阵高速幂) 题目链接 题目大意: 给出n∗m矩阵,给出第一行a01, a02, a03 ...a0m (各自是233, 2333, 23333...), 再给定第一列a10, a10, a10, a10,...an0.矩阵中的每一个元素等于左边的加上上面的,求出anm. 解题思路: 先要依据矩阵元素的特征得出相乘的矩阵T, 然后就是求这个

HDU5015 233 Matrix(矩阵高速幂)

题目链接

题目大意:
给出nm矩阵,给出第一行a01, a02, a03 ...a0m (各自是233, 2333, 23333...), 再给定第一列a10, a10, a10, a10,...an0.矩阵中的每一个元素等于左边的加上上面的,求出anm.

解题思路:
先要依据矩阵元素的特征得出相乘的矩阵T, 然后就是求这个矩阵T的m次幂(这里就能够用矩阵高速幂),最后再和给定的第一列所形成的矩阵相乘,就能得到anm。
求矩阵T请參考

代码:

#include <cstdio>
#include <cstring>

typedef long long ll;

const int N = 15;
const ll MOD = 10000007;

ll A[N][N];
int B[N];
int n;
ll m;

struct Rec {

    ll v[N][N];

    Rec () { memset (v, 0, sizeof (v));}
    void init () {

        for (int i = 0; i < n + 2; i++)
            for (int j = 0; j < n + 2; j++)
                v[i][j] = A[i][j];
    }

    Rec operator * (const Rec &a) {

        Rec tmp;
        for (int i = 0; i < n + 2; i++)
            for (int j = 0; j < n + 2; j++) 
                for (int k = 0; k < n + 2; k++)
                    tmp.v[i][j] = (tmp.v[i][j] + (v[i][k] * a.v[k][j]) % MOD) % MOD;
        return tmp;
    }

    Rec operator *= (const Rec &a) {

        return *this = *this * a;
    }
}num;

void init () {

    memset (A, 0, sizeof (A));
    for (int i = 0; i < n + 1; i++) {
        A[i][0] = 10LL;
        A[i][n + 1] = 1LL;
    }

    A[n + 1][n + 1] = 1LL;
    for (int i = 1; i < n + 1; i++) 
        for (int j = 1; j <= i; j++) 
            A[i][j] = 1LL;
    B[0] = 23;
}

Rec f(ll m) {

    if (m == 1)
        return num;
    Rec tmp;
    tmp = f(m / 2);
    tmp *= tmp;
    if (m % 2)
        tmp *= num; 
    return tmp;
}

int main () {


    while (scanf ("%d%lld", &n, &m) != EOF) {

        for (int i = 1; i <= n; i++)
            scanf ("%d", &B[i]);

        init();
        B[n + 1] = 3;
        num.init ();

        num = f(m);

/* for (int i = 0; i <= n + 1; i++) { for (int j = 0; j <= n + 1; j++) printf ("%lld ", num.v[i][j]); printf ("\n"); }*/

        ll ans = 0;
        for (int i = 0; i <= n + 1; i++) 
            ans = (ans + (num.v[n][i] * B[i]) % MOD) % MOD;
        printf ("%lld\n", ans);
    }
    return 0;
}

HDU5015 233 Matrix(矩阵高速幂)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
233 Matrix Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
233 Matrix Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Uva 11149 - Power of Matrix ( 矩阵快速幂 ) #include <cstdio> #include <cstring> #
HDU 4965 Fast Matrix Calculation ( 矩阵乘法 + 矩阵快速幂 + 矩阵乘法的结合律 ) #include <cs
POJ 3233 - Matrix Power Series ( 矩阵快速幂 + 二分 ) #include <cstdio> #include <cst
Queuing Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Tot
A. Plant time limit per test 2 seconds memory limit per test 256 megabytes input standard inp
题目信息: 1471: Jiulianhuan 时间限制: 1 Sec 内存限制: 128 MB 提交: 95 解决: 22 题目描述   
二阶偏导数矩阵也就所谓的赫氏矩阵(Hessian matrix). 一元函数就是二阶导,多元函数就是二阶偏导组
Matrix,中文里叫矩阵,高等数学里有介绍,在图像处理方面,主要是用于平面的缩放、平移、旋转等操
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号