LOJ538 「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;
}