专栏首页算法修养POJ 3233 Matrix Power Series(矩阵快速幂)

POJ 3233 Matrix Power Series(矩阵快速幂)

Matrix Power Series Time Limit: 3000MS Memory Limit: 131072K Total Submissions: 19338 Accepted: 8161 Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

2 2 4 0 1 1 1 Sample Output

1 2 2 3

可以找到递推关系 : s[k]=s[k-1]+A^k; 然后构造矩阵,利用矩阵快速幂

具体见代码

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
int n,k;
int m;
struct Node
{
    int a[65][65];

};
Node multiply(Node a,Node b)
{
    Node c;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            c.a[i][j]=0;
            for(int k=1;k<=n;k++)
            {
                (c.a[i][j]+=(a.a[i][k]*b.a[k][j])%m)%=m;
             }
        }
    } 
    return c;
}
Node quick(Node a,int x)
{
    Node c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        c.a[i][j]=(i==j?1:0);
    for(x;x>0;x>>=1)
    {
        if(x&1) 
            c=multiply(c,a);
        a=multiply(a,a);
     }
    return c;
}
int main()
{
   while( scanf("%d%d%d",&n,&k,&m)!=EOF)
   {
    Node a;Node b;Node c;
    memset(a.a,0,sizeof(a.a));
    memset(b.a,0,sizeof(b.a));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a.a[i][j+n]);
            b.a[i+n][j+n]=a.a[i][j+n];
        }
    for(int i=1;i<=n;i++)
    {
        b.a[i][i]=1;
        b.a[i+n][i]=1;
    }
    n=n*2;
    c=multiply(a,quick(b,k));
    for(int i=1;i<=n/2;i++)
        for(int j=1;j<=n/2;j++)
           if(j==n/2)printf("%d\n",c.a[i][j]);
           else printf("%d ",c.a[i][j]);
   }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1575 Tr A(矩阵快速幂)

    Tr A Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java...

    ShenduCC
  • POJ 3070 Fibonacci(矩阵快速幂)

    Fibonacci Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 12...

    ShenduCC
  • POJ-2081 Terrible Sets(暴力,单调栈)

    Terrible Sets Time Limit: 1000MS Memory Limit: 30000K Total Submissions...

    ShenduCC
  • HDU 1575 Tr A(矩阵快速幂)

    Tr A Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java...

    ShenduCC
  • Contest100000577 – 《算法笔记》3.3小节——入门模拟->图形输出

    http://codeup.cn/contest.php?cid=100000577

    lollipop72
  • 桶排序(Bucket Sort)的数组实现

    桶排序Bucket Sort从1956年就开始被使用,该算法的基本思想是由E. J. Issac R. C. Singleton提出来。

    Enjoy233
  • BZOJ1898: [Zjoi2005]Swamp 沼泽鳄鱼(矩阵快速幂)

    attack
  • 所谓学习技巧无非就是善于发现规律

    很明显不同物种就是2个字符的简称即可,这个对应表格很明显是物种的拉丁名。但是在使用一个需要TxDb的R包时候,自己的物种是斑马鱼org.Dr.eg.db,请问对...

    生信技能树
  • SPOJ4580 ABCDEF(meet in the middle)

    attack
  • P1576 最小花费

    题目背景 题目描述 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问...

    attack

扫码关注云+社区

领取腾讯云代金券