LOJ538 「LibreOJ NOIP Round #1」数列递推 题解

题目链接：#538. 「LibreOJ NOIP Round #1」数列递推

题意：cxy 虐爆 OI 之后成为了一名文化课选手。一天，她做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：

给定一个下标从 $0$ 开始，无限长的整数列 $\{a_i\},\ i\in \mathbb{N}$，已知 $a_0,a_1$ 的值，以及递推式 $a_{i+2}=k a_{i+1}+a_i,\ i\in\mathbb{N},k\in {\mathbb{N}_+}$。

cxy 研究了这些数列，发现它们十分优美充满人类智慧，于是决定出一道 OI 题。

cxy 给了你一个集合 $S\subset \mathbb{N}$，他想问你对于 $S$ 中的每个数 $s_i$，使得 $a_{s_i}$ 最大的 $s_i$ 和使得 $a_{s_i}$ 最小的 $s_i$ 分别是多少。如果这样的 $s_i$ 有多个，请你回答最小的一个。

另外，cxy 准备对她作业中碰到的每个数列都让你回答一次，不过每次的集合 $S$ 是一样的。

输入格式：

输入第一行一个整数 $m$ 表示 $S$ 中元素个数。

第二行 $m$ 个整数 $s_1,s_2,\cdots ,s_m$ 表示 $S$ 中的元素。保证它们是非负整数且严格递增（即 $s_i<s_{i+1}$ ）。

第三行一个整数 $n$ 表示询问的数列个数。

接下来 $n$ 行每行三个整数 $a_0, a_1, k$ 描述一个数列。

输出格式：

输出共 $n$ 行，每行依次输出两个整数 $\mathrm{maxsi},\mathrm{minsi}$ ，依次表示 $S$ 的元素 s_i 中，使得 $a_{s_i}$ 最大的 $s_i$ 和使得 $a_{s_i}$ 最小的 $s_i$ 的值。如果这样的 $s_i$ 有多个，请你回答最小的一个。

看看样例就会发现这个数列在若干项之后会有单调性

考虑打表找规律，然后发现确实是这样。

接下来我们来证明一下这个结论¹

• 如果 $a_0a_1 > 0$ ，则 $a_0,a_1$ 同号

  由递推式 $a_{i+2} = ka_{i+1} + a_i$ 知 $a_2$ 与 $a_1,a_0$ 同号，且 $|a_2| > |a_1|$

  由数归易得结论成立。

• 如果 $a_0a_1 < 0$ ，不妨假设 $a_0 > 0,a_1<0$ ，否则设 $a_i^{\prime} = a_i$ 即可

  记 $b_i = (-1)^i a_i$ ，则有 $b_{i+2} =b_i -kb_{i+1}$

  一旦 $b_i$ 有负项，设 $b_j$ 为 $\{b_i\}$ 的第一个负项，又 $b_{j-1}$ 为正项，故 $a_{j-1},a_j$ 同号，转化为第一种情况。

  因此只需要考虑 $b_i$ 中单调递减的正项会持续几项的问题

  由于

  $$b_i = kb_{i+1} + b_{i+2} > kb_{i+2} + b_{i+2} = (k+1) b_{i+2}$$

  因此有 $b_{i+2} < \dfrac{1}{k+1} b_i$

  于是这样的项最多有 $M \sim 2\log b_0 = 2\log a_0$ 项

  约为 $40$ 项（其实看数据范围可以猜出来的），就会出现 $\{a_i\}$ 中相邻两项同号的情况，从而结论成立。

• $a_0a_1=0$ ，则 $a_0=0$ 或 $a_1=0$ ，好像有点问题？

  那！么！就！特判！即！可！！！！

这里比较大的数可以用double来算，防止溢出

时间复杂度 $O(nM)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

const int bd=40;
int n,m,h=-1,Q,mx,mn,s[N];
double a[55];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> s[i];
    for(int i=1; i<=n; i++) if(s[i] >= bd) {h=s[n],n=i-1; break;}
    cin >> Q;
    for(int u,v,k; Q--;)
    {
        cin >> u >> v >> k;
        if(!u && !v) {cout << s[1] << " " << s[1] << '\n'; continue;}
        a[0]=u; a[1]=v;
        for(int i=2; i<=bd; i++) a[i]=(double)k*a[i-1]+a[i-2];
        mx=mn=s[1];
        for(int i=2; i<=n; i++)
        {
            a[s[i]] > a[mx] ? mx=s[i] : 0;
            a[s[i]] < a[mn] ? mn=s[i] : 0;
        }
        if(~h) (a[bd] > 0.0 ? mx : mn) = h;
        cout << mx << " " << mn << '\n';
    }
    return 0;
}

参考文献：

¹. https://yhx-12243.github.io/OI-transit/records/loj538.html ↩