P1707 刷题比赛

    • 41通过
    • 104提交
  • 题目提供者 nodgd
  • 评测方式 云端评测
  • 标签 倍增 矩阵乘法 矩阵运算 线性递推,递推式 递推 洛谷原创
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    nodgd是一个喜欢写程序的同学,前不久洛谷OJ横空出世,nodgd同学当然第一时间来到洛谷OJ刷题。于是发生了一系列有趣的事情,他就打算用这些事情来出题恶心大家……

    题目描述

    洛谷OJ当然算是好地方,nodgd同学打算和朋友分享一下。于是他就拉上了他的朋友Ciocio和Nicole两位同学一起刷题。喜欢比赛的他们当然不放过这样一次刷题比赛的机会!

    在第1天nodgd,Coicoi,Nicole都只做了1道题。

    在第2天nodgd,Coicoi,Nicole都只做了3道题。

    他们都有着严格的刷题规则,并且会在每一天都很遵守规则的刷一定量的题。

    (1)nodgd同学第k+2天刷题数量a[k+2]=p*a[k+1]+q*a[k]+b[k+1]+c[k+1]+r*k^2+t*k+1;

    (2)Ciocio同学第k+2天刷题数量b[k+2]=u*b[k+1]+v*b[k]+a[k+1]+c[k+1]+w^k;

    (3)Nicole同学第k+2天刷题数量c[k+2]=x*c[k+1]+y*c[k]+a[k+1]+b[k+1]+z^k+k+2;

    (以上的字母p,q,r,t,u,v,w,x,y,z都是给定的常数,并保证是正整数)

    于是他们开始了长时间的刷题比赛!一共进行了N天(4<=N<=10^16)

    但是时间是可贵的,nodgd想快速知道第N天每个人的刷题数量。不过nodgd同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题……要做,就拜托你来帮他算算了。

    由于结果很大,输出结果mod K的值即可。

    输入输出格式

    输入格式:

    第一行两个正整数N,K。(4<=N<=10^16,2<=K<=10^16)

    第二行四个正整数p,q,r,t。

    第三行三个正整数u,v,w。

    第四行三个正整数x,y,z。

    (保证p,q,r,t,u,v,w,x,y,z都是不超过100的正整数)

    输出格式:

    共三行,每行一个名字+一个空格+一个整数。依次是nodgd,Ciocio,Nicole和他们在第N天刷题数量mod K的值。

    输入输出样例

    输入样例#1: 复制
    4 10007
    2 1 1 1
    2 2 3
    1 1 2
    输出样例#1: 复制
    nodgd 74
    Ciocio 80
    Nicole 59

    说明

    矩阵乘法。

    注意,中间相乘过程可能会比64位长整型的数据范围还要大。

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