中国(北方)大学生程序设计训练赛(第一周)E. water problem

本文主要是介绍中国(北方)大学生程序设计训练赛(第一周)E. water problem,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

函数 f:Z+Zf:Z+→Z。已知 f(1)f(2)f(1),f(2) 的值,且对于任意 x>1x>1,有 f(x+1)=f(x)+f(x1)+sin(πx2)f(x+1)=f(x)+f(x−1)+sin⁡(πx2)

求 f(n)f(n的值

多组数据。(数据组数 T100T≤100

每组数据包含 33 个不超过 109109 的正整数,分别代表 f(1)f(2)f(1),f(2) 和 nn 的值。

输出  f(n)mod(109+7)f(n)mod(109+7) 。每组输出末尾有换行符。


题意:

题目类似斐波那契数列,但比斐波那契数列多了一项。

思路:

首先回忆斐波那契数列的计算方法:

一、递归

直接按照递推公式递归运算,此方法有大量重复计算,导致n趋近不足100就无法在有限时间内计算出来,通常作为递归讲解的例子。

二、动态规划(dp)

为了避免重复计算,我们通常用一个数组记录已经计算的值,采用记忆化搜索的动态规划,就可以减少重复计算。

根据dp[n] = dp[n-1] + dp[n-2] 从第三项开始迭代即可。

此方法的时间复杂度为O(n),线性时间复杂度,考虑在1s内,无法计算大于1e8的数据范围。

三、矩阵快速幂

数列的递推公式为:f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)(n>=3)

   用矩阵表示为:

  进一步,可以得出直接推导公式:

所以,对矩阵[1,1,1,0]进行n-2次幂运算,就可以计算出f(n)的值,此时由于幂运算可以使用快速幂运算,可以用矩阵快速幂来进行计算。

此时的时间复杂度为O(logN)

对比斐波那契数列,将其推广

由于本题中的递推关系非线性,即有sin项的约束,f(x+1)=f(x)+f(x1)+sin(πx2)f(x+1)=f(x)+f(x−1)+sin⁡(πx2)。我们展开两项,得到f(x) = f(x-1) + f(x-3) + f(x-4),通过sin的周期性,消去了常数项。

得到了一个四阶线性递推公式。

类比斐波那契数列的方法,我们需要找一个转移矩阵,满足上述矩阵运算。

由于斐波那契数列是二阶递推数列,所以存在一个2*2的矩阵A,使得:

[Fn Fn-1] = [Fn-1 Fn-2] * A      

所以以上的四阶递推公式也一定存在一个4*4的矩阵A,满足

[Fn Fn-1 Fn-2 … Fn-k+1] = A*[Fn-1 Fn-2 Fn-3 … Fn-k]

                                          = …

                                          = An-k+1 *[Fk-1 Fk-2 Fk-3 … F0   

这里的k=5;

根据以上地推关系,拼凑出矩阵A(转移矩阵) 为[1 0 1 1,1 0 0 0,0 1 0 0,0 0 1 0]

在计算矩阵的幂时,首先我们定义矩阵乘法的运算法则(矩阵乘法公式),然后对指数进行快速幂处理,通过减少乘法次数,化时间为对数量级。


这篇关于中国(北方)大学生程序设计训练赛(第一周)E. water problem的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881620

相关文章

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展

【科技明说 | 科技热点关注】 2024戴尔科技峰会在8月如期举行,虽然因事未能抵达现场参加,我只是观看了网上在线直播,也未能采访到DTF现场重要与会者,但是通过数十年对戴尔的跟踪与观察,我觉得2024戴尔科技峰会给业界传递了6大重要信号。不妨简单聊聊:从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展? 1)退出中国的谣言不攻自破。 之前有不良媒体宣扬戴尔将退出中国的谣言,随着2

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①<(小于) ②<=(小于或等于) ③>(大于) ④>=(大于或等于 ) ⑤==(等于) ⑥!=(不等于) 说明: 前4个优先级相同,后2个优先级相同,关系运算符的优先级低于算术运算符,关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式(可以是算术表达式或关系表达式,逻辑表达式,赋值表达式,字符

如何打造个性化大学生线上聊天交友系统?Java SpringBoot Vue教程,2025最新设计思路

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录

智能工厂程序设计 之1 智能工厂都本俱的方面(Facet,Aspect和Respect)即智能依赖的基底Substrate 之1

Q1、昨天分别给出了三个智能工厂的 “面face”(里面inter-face,外面outer-face和表面surface) 以及每个“面face” 各自使用的“方”(StringProcessor,CaseFilter和ModeAdapter)  。今天我们将继续说说三个智能工厂的“方面” 。在展开之前先看一下三个单词:面向facing,取向oriented,朝向toword。理解这三个词 和

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及, 以及人们活动范围的不断扩大,城市道 路交通拥堵问题日渐严重,即使在一些非中心城市,道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”,是相关部门的棘手难题之一。 考虑一个拥有知名景区

2024 年高教社杯全国大学生数学建模竞赛 C 题 农作物的种植策略 参考论文 无水印

持续更新中,2024年数学建模比赛思路代码论文都会发布到专栏内,只需订阅一次!  完整论文+代码+数据结果链接在文末!  订阅后可查看参考论文文件 第一问 1.1 问题重述 这个问题围绕的是华北山区的某乡村,在有限的耕地条件下,如何制定最优的农作物种植策略。乡村有 34 块露天耕地和 20 个大棚,种植条件包括粮食作物、蔬菜、水稻和食用菌。除了要考虑地块的面积、种植季节等,还要确保