首页 > 其他分享 >递推 Pell数列

递推 Pell数列

时间:2023-02-07 13:04:36浏览次数:63  
标签:... 数列 int a1 Pell a2 递推


Pell数列


时间限制: 1000 ms         内存限制: 65536 KB

提交数: 1013     通过数: 528 


【题目描述】

Pell数列a1,a2,a3,...a1,a2,a3,...的定义是这样的,a1=1,a2=2,...,an=2an−1+an−2(n>2)a1=1,a2=2,...,an=2an−1+an−2(n>2)。

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


【输入】

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

【输出】

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

【输入样例】



218


【输出样例】



1408


【来源】


​No​

#include<bits/stdc++.h>
using namespace std;
long long int f[1000002];
int main()
{
f[1]=1,f[2]=2;
for(int i=3;i<=1000001;i++)
f[i]=(2*f[i-1]+f[i-2])%32767;//模1000在这里,在结果就不对了
int n,T;
cin>>T;
while(T--)
{
scanf("%d",&n);
printf("%d\n",f[n]);
}
return 0;
}



标签:...,数列,int,a1,Pell,a2,递推
From: https://blog.51cto.com/u_14932227/6041993

相关文章

  • 递推 上台阶
    上台阶时间限制:1000ms      内存限制:65536KB提交数:2025   通过数:347 【题目描述】楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶......
  • 一步一步地完成题目——费解的开关(C/C++语言)递推、递归、顺序思维
    前言本文中博主将一步一步地、以正常人的顺序思维完成题目——费解的开关,使用的核心方法是递推与递归。题目参考题目:费解的开关详细的题目信息相信大家都已经知道了,因......
  • 递归法求解数列组合的各种情况
    C#代码:staticvoidMain(string[]args){int[]items=newint[]{0,1,2,3,4};intm=3;List<int[]>allC......
  • 费解的开关(位运算+递推)
    题目描述:你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产......
  • 常系数齐次线性递推
    现在终于把线性递推常数减小了许多。(实际上我原先写的多项式取模才这么慢)Fiduccia算法一个方法是求\(x^n\)对递推数列的特征多项式\[p(x)=x^k-p_1x^{k-1}-p_2x^{k-2}......
  • 万字详解递归与递推
    前言相信这个故事,朋友们应该都不陌生,从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?「从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事......
  • Java斐波那契数列实例
      在斐波那契数列中,下一个数字是前两个数字的总和,例如:0,1,1,2,3,5,8,13,21,34,55等。斐波那契数列的前两个数字是0和1,第三个数字是前两个数字的和,也就是0+1=1,所以这......
  • Fibonacci数列,从递归,O(N)迭代,动态规划,O(logN)矩阵快速幂到O(1)通项公式
    题目链接:剑指Offer10-I.斐波那契数列-力扣(LeetCode)朴素递归做法核心是一个递归边界和递归体,复杂度分析可画递归树可得,时间复杂度是O(2N),这是一个估算的上界,递归树......
  • 【闲话】1.27 斐波那契数列一个性质及推广
    众所周知众所周知,斐波那契数列有一个性质:\[\gcd(f_{n},f_{m})=f_{\gcd(n,m)}\]在证明他之前,先来看个引理:\(\text{Lemma}\1\)\[f_{n+m}=f_{n}\timesf_{m-1}+f_{n+1......
  • 浅谈线性递推
    线性递推相关常系数齐次线性递推对于一般的递归式,我们有\(\sum\limits_{j=0}^{k}A_{i-j}R_j=0,i\gek\)定义\(S=AR\),则\(S\)的最高次为\(k-1\),小于\(R\)的最高次项\(......