P1397 [NOI2013]矩阵游戏

    • 139通过
    • 474提交
  • 题目提供者
  • 标签 矩阵乘法 线性递推,递推式 递推 NOI系列 2013 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:

    F[1][1]=1

    F[i,j]=a*F[i][j-1]+b (j!=1)

    F[i,1]=c*F[i-1][m]+d (i!=1)

    递推式中a,b,c,d都是给定的常数。

    现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大,你只需要输出F[n][m]除以1,000,000,007的余数。

    输入输出格式

    输入格式:

    输入文件matrix.in包含一行有六个整数n,m,a,b,c,d。意义如题所述。

    输出格式:

    输出文件matrix.out包含一个整数,表示F[n][m]除以1,000,000,007的余数。

    输入输出样例

    输入样例#1: 复制
    3 4 1 3 2 6
    
    输出样例#1: 复制
    85
    

    说明

    【样例1说明】

    样例中的矩阵为:

    1 4 7 10

    26 29 32 35

    76 79 82 85

    数据范围

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。