本文共 798 字，大约阅读时间需要 2 分钟。

一、原题

1788:Pell数列

总时间限制: 3000ms 内存限制: 65536kB

给出一个正整数k，要求Pell数列的第k项模上32767是多少。

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。

n行，每行输出对应一个输入。输出应是一个非负整数。

218

1408

二、分析

本题中的Pell数列其实很简单，只要反复的调用递归就行了，根据Pell数列的公式a1=1,a2=2,...,an=2*an−1+an-2(n>2)，设置好边界，就可以反复调用了，我为了速度，就用了记忆化递归调用。

三、源代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;long long b[1000010];long long zjf(int n){	if(n<3)			     //设置边界		return n;	if(b[n]==0)					//记忆化递归调用		b[n]=(2*zjf(n-1)+zjf(n-2))%100000;	//取mod，不让long long数组爆掉，但是为了避免统计错误，就取100000的mod	return (b[n]%32767);}int main(){	int n,x;	cin>>n;	for(int i=1;i<=n;i++){		cin>>x;		cout<
        
         <
        
       
      
     
    
   

转载地址：http://oaftb.baihongyu.com/