当前位置: 首页 > news >正文

CF60E Mushroom Gnomes

CF60E Mushroom Gnomes

10月10日的茶

考虑蘑菇在一分钟后有什么变化

\[\begin{align} &S_0 = a_1 + a_2 + a_3 + a_4 ... + a_{n-1} + a_{n} \\ &S_1 = a_1 +(a_1 + a_2) + a_2 + (a_2 + a_3) + a_3 + ... + a_{n-1} + (a_{n-1} + a_{n}) + a_{n}\\ &S_1 = S_0 + a_1 + a_2 + a_2 + a_3 + a_3 + ... + a_{n-1} + a_{n-1} + a_{n} \\ &S_1 = S_0 + 2S_0 - (a_1 + a_n) \\ &S_1 = 3S_0 - (a_1 + a_n) \end{align} \]

\(C = -(a_1 + a_n)\) 可见可用矩阵描述转移

\[\begin{bmatrix} S_1\\ C \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} S_0\\ C \end{bmatrix} \]

第二次生长前还要进行一次排序,排序后 \(a_1\) 作为最小值不变,而最大值不再是 \(a_n\)

按照上面的变化,可以看出第一分钟后的最大值是 \(a_{n-1} + a_n\) 第二次是 \((a_{n-1} + a_n) + a_n\) ......

循环往复,变化如同斐波那契数列,同样可以用矩阵描述

\[\begin{bmatrix} a_1\\ b_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_0\\ b_0 \end{bmatrix} \]

因此,可以用矩阵快速幂计算出第一次变化后的 \(S\)\(C\) 然后据此再用矩阵快速幂求出答案

代码

注意:当 \(n\)\(1\) 的时候,蘑菇不会生长,直接输出 \(a_1\) 并注意取模

http://www.hskmm.com/?act=detail&tid=29028

相关文章:

  • CF691E Xor-sequences
  • LCPC12E - Johnnys Empire 题解
  • 中微笔记-cp.1 技术
  • P1896 [SCOI2005] 互不侵犯小总结
  • 美国能源部《生成式人工智能参考指南》解读
  • 分析InfluxDB中读取时CPU飙升
  • win10系统访问smb服务时提示密码错误
  • 《小说课》读书笔记
  • 2025-10-11?
  • 高二停课周记(信息学竞赛) Week1
  • AtCoder Beginner Contest 427 ABCDEF 题目解析
  • zju博士资格考试考前复习(微分方程方向)ode 部分
  • 测试一下博客功能
  • AI如何改变芯片设计
  • NOIP 2024
  • 2025/10/11
  • 好玩热门的switch游戏推荐【PC+安卓】塞尔达传说:王国之泪|v1.4.2整合版|官方中文| 附switch模拟器
  • 十年运维工程师总结
  • 运动控制教学——5分钟学会Dijkstra与A*搜索算法!(附仿真视频及代码) - 教程
  • ffplay数据结构解析
  • CNN 发展历程
  • FileX和ThreadX精简版
  • ue4素材场景 - MKT
  • 阅读《构建之法》的思考与问题
  • 实验报告5(链栈基本操作,数制转换,匹配算法,伴舞问题)
  • 阅读和提问作业1:《构建之法》提问
  • 企业推行OKR中层领导关注的10个关键问题及解决方案
  • 初四夜间/休息日安排
  • AWS自然语言处理技术实战指南
  • 多线程