查看状态 Show Status

状态题目:找规律

题目编号:253-找规律 查看该题

状态: Unaccepted

测评机： Xeost[5]

得分： 50分

提交日期： 2009-10-24 18:03:00

有效耗时： 280毫秒

测试结果1: 通过本测试点|有效耗时62ms

测试结果2: 通过本测试点|有效耗时46ms

测试结果3: 通过本测试点|有效耗时63ms

测试结果4: 通过本测试点|有效耗时62ms

测试结果5: 通过本测试点|有效耗时47ms

测试结果6: 选手程序运行超过时限

测试结果7: 测试结果错误.错误结果为:Yes

3498 7233 14160 26419 47256 81451 135873 220165 347612 536195 809881 1200168 1747930 2505606 3539766 4934106 6792928 9245153 12448924 16596869 21922083 28704904 37280554 48047733 61478239 78127712 98647589 123798378 154464346 191669735 236596619 290604527 355251950 432319874 523837461 632110047 759749581 909707675 1085311427 1290302188 1528877437 1805735966 2126126549 2495900300 2921566924 3410355067 3970276990 4610197798 5339909437 6170209737 7112986709 8181308398 9389518521 10753338188 12289973982 14018232691 15958642995 18133584411 20567423827 23286659939 26320075942 29698900810 33456979532 37630952659 42260445550 47388267690 53060622487 59327327948 66242048653 73862539446 82250901298 91473849766 101602996534 112715144479 124892596761 138223480427 152802085024 168729216745 186112568628 205067107356 225715477190 248188421622 272625223301 299174162830 327992997029 359249457275 393121768548 429799189817 469482576407 512384965029 558732182131 608763476271 662732175203 720906368408 783569615788 851021683266 923579306057 1001576980381 1085367784395 1175324229156

正确结果应为:Yes

1073 2476 6239 16108 40367 95749 213663 449634 897058 1706600 3112810 5469800 9298114 15345233 24662488 38701506 59433687 89496604 132371633 192597556 276025337 390119749 544314029 750424258 1023130704 1380533928 1844794036 2442862064 3207313108 4177291457 5399578654 6929796098 8833754509 11188963308 14086313715 17631950140 21949345235 27181594789 33493949483 41076601378 50147743886 60956924872 73788713454 88966702008 106857865846 127877304017 152493385684 181233327554 214689228883 253524591644 298481354533 350387470596 410165059389 478839165733 557547158297 647548802434 750237042908 867149533384 999980950808 1150596134080 1321044087720 1513572892545 1730645566714 1974956921858 2249451460393 2557342361516 2902131604807 3287631281804 3717986147383 4197697464261 4731648195447 5325129600994 5983869296954 6714060836008 7522394870834 8416091962888 9402937100906 10491315995089 11690253214608 13009452237762 14459337485839 16051098413468 17796735730009 19709109828308 21801991498945 24090115009925 26589233633605 29316177704514 32288915293608 35526615586408 39049715054396 42879986510992 47040611145404 51556253629633 56453140395926 61759141184002 67503853959429 73718693306604 80436982401883 87694048674524

测试结果8: 选手程序运行超过时限

测试结果9: 输出过长|用户输出数据超过标准输出两倍[标准输出294位|选手输出592位]

测试结果10: 选手程序运行超过时限

提交代码： /*

查看题目 Show Problem

题目:找规律

问题编号:253 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]

My Flag:Unsubmited

题目类型

数论 / 数值

描述

题目背景

到暑假了，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”。

样例输入

[第一组]

1 10

3

[第二组]

6 3

1 2 3 4 5 6

[第三组]

8 2

1 2 4 7 11 16 22 29

[第四组]

4 2

1 2 4 8

样例输出

[第一组]

Yes

3 3 3 3 3 3 3 3 3 3

[第二组]

Yes

7 8 9

[第三组]

Yes

37 46

[第四组]

Yes

15 26

*/

#include<iostream>

#include<iomanip>

using namespace std；

class Poly{

private:

double *coeff；

public:

int degree；

Poly(int MSize):degree(MSize){

coeff=new double[degree+1]；

for (int i=0；i<=degree；++i) coeff[i]=0.0；

}

inline bool SetCoeff(int exp,double value){

if (exp>degree) return false；

coeff[exp]=value；

return true；

}

inline double GetCoeff(int exp){

if (exp>degree) return 0；

else return coeff[exp]；

}

Poly operator * (Poly b){

Poly c(degree+b.degree)；

for (int i=0；i<=degree；++i)

for (int j=0；j<=b.degree；++j)

c.SetCoeff(i+j,c.GetCoeff(i+j)+GetCoeff(i)*b.GetCoeff(j))；

return c；

}

Poly operator + (Poly b){

Poly c(max(b.degree,degree))；

for (int i=0；i<=c.degree；++i)

c.SetCoeff(i,GetCoeff(i)+b.GetCoeff(i))；

return c；

}

}；

double Horner(Poly A,double v){

double s=A.GetCoeff(A.degree)；

for (int i=A.degree-1；i>=0；--i) s=s*v+A.GetCoeff(i)；

return s；

}

Poly Interpolate(double x[],double y[],int n){

Poly D(n-1),U(n-1),G(n-1)；

double denom,num；

G.SetCoeff(0,y[1])；

D.SetCoeff(0,-x[1])；

D.SetCoeff(1,1)；

for (int j=2；j<=n；++j){

denom=Horner(D,x[j])；

num=Horner(G,x[j])；

if (denom==0){

cout<<"No"；

exit(0)；

}

for (int i=0；i<=n-1；++i) U.SetCoeff(i,D.GetCoeff(i)*(y[j]-num)/denom)；

G=G+U；

U.SetCoeff(0,-x[j])；

U.SetCoeff(1,1)；

D=D*U；

}

return G；

}

int main (void){

int n,k；

cin>>n>>k；

double *y,*x；

x=new double[n+1]；

y=new double[n+1]；

for (int i=1；i<=n；++i){

x[i]=(double)i；

cin>>y[i]；

}

Poly Poly=Interpolate(x,y,n)；

// for (int i=0；i<=Poly.degree；++i) cout<<" + ( "<<Poly.GetCoeff(i)<<" * n ^ "<<i<<" ) "<<endl；

// for (int i=1；i<=n；++i) cout<<Horner(Poly,i)<<"::"<<y[i]<<" "；

// cout<<endl；

cout<<"Yes"<<endl；

for (int i=n+1；i<=n+k；++i){

if (i!=n+1) cout<<" "；

cout<<setiosflags(ios::fixed)<<setprecision(0)<<Horner(Poly,i)；

}

return 0；

}