RQNOJ系统遇到了一个程序错误。

您可以通过邮件support (at) rqnoj.cn与我们进行联系。请附错误参考编号:273303

找规律 - 题库 - RQNOJ
PID253 / 找规律
题目描述

题目背景

到暑假了,woody 终于找到了可以有所放松休闲的时光。邻居的小孩 ivan 也放假了。一天,两人玩起了找规律填数字游戏……

两个人玩的填数字游戏和通常有所不同,规则是由出题者给出一个数列的前几项,由解题者找出符合所有这些项

的一个通项公式(必须是一个多项式,不然 ivan 看不懂……),再由通项公式确定出后几项。

起初,这个游戏充满了数学与童趣,但当两人出的数列越来越古怪时,小学文化的 ivan 放声大叫:怎么可能存在合理的通项公式!

但是已经读了一年高中的 woody 总是能写出某一个比较诡异的多项式来满足所有给出的数字。

经过了几次这样的游戏之后,ivan 不干了,因为他发现,最后多项式的次数都是成百上千次,他算不出来~

他对 woody 说道:“这样不公平,你学的比我多,欺~负~人~!我们要改规则。你必须找出满足条件的次数最少的公式,并要能跟我说清楚为什么它的次数不能再少了!”

这下 woody 可傻眼了——不是他不会做,而是给这样一个小学文凭兼不讲理的小小孩解释他能听懂吗?于是他找到了 wish 帮忙。

wish 看完题目之后发现——。。。——。。。——。。。——不会做。。。汗 - -||

wish 不想因为这件事情搞丢了面子,所以他就找到你了,希望你一定一定要帮助他哦!

题目描述

给出一个数列的前 n 项,求一个满足这 n 项的次数最小的通项公式,通过这个通项公式计算这个数列接下来的 k 项并输出。

数据范围

测试一共10组数据。

对于 30% 的数据,n=3, k <= 100

对于 60% 的数据,n <= 10, k <= 100

对于 80% 的数据,n, k <= 100, n + k <= 100

对于 100% 的数据,n, k <= 3000, n + k <= 3000

算法及优化正确的前提下,所有中间结果和输出不会超过64位无符号整数(qword、unsigned long long)的范围,也不会出现负数。请尽量不要使用浮点数,以免误差带来错误。

注意将会有各种极端/诡异/猥琐数据,提交前请仔细考虑并做好充分优化和心理准备。

样例解释

[第一组] an=1

[第二组] an=n

[第三组] an=n^2/2-n/2+1

[第四组] an=n^3/6-n^2/2+4n/3

题目来源

SPOJ Problem CMPLS: Complete the Sequence!

数据加强&翻译&改编 by wish

输入格式

第一行两个整数:n, k,题目描述已经说明。

第二行 n 个整数,表示给出的前 n 项。

输出格式

如果存在符合要求的通项公式,第一行输出“Yes”,第二行输出 k 个数,求得的这个数列接下来的 k 项,两个数之间用一个空格隔开。

如果不存在任何符合要求的通项公式,输出一行“No”。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论