文理学院程序设计在线练习


k阶裴波那契序列

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 35   Accepted Submission(s): 22
Problem Description

已知k阶裴波那契序列的定义为:

f0=0, f1=0, ..., fk-2=0, fk-1=1;
fn = fn-1 + fn-2 + ... + fn-k, n=k,k+1,...

试编写程序,求k阶裴波那契序列的第n项的值。

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据(1<=T<=30)。
每组测试包括2个整数,一个是k,另一个是n。(其中n<=20,k<=20)

Output

对于每组测试数据,输出k阶裴波那契序列的第n项值,每行一个结果。若k<2或者n<0,则输出-1。

Sample Input
3
2 10
2 2
2 -3
Sample Output
55
1
-1
Author

xsh

Source

数理信息学院首届程序设计竞赛2011/06/11