题目背景
到暑假了,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”。