P8956题解

· · 题解

前言：本题解 \LaTeX 使用较多，如果渲染失败请移步与此。

题意

非常喜欢这道题，考察到了多方面的知识以及非常坑的取模，下面简述一下：

给定 5 个整数 n,A,B,X,Y，求对于两串串数列：

\begin{aligned} F_{A,B}(1)=A,F_{A,B}(2)=B,F_{A,B}(x)=\lfloor \sqrt{F_{A,B}(x-2)F_{A,B}(x-1)}\rfloor+1\;(x \ge 3)\\ F_{X,Y}(1)=X,F_{X,Y}(2)=Y,F_{X,Y}(x)=\lfloor \sqrt{F_{X,Y}(x-2)F_{X,Y}(x-1)}\rfloor+1\;(x \ge 3) \end{aligned} \right.

的：

\prod_{i=1}^nF_{X,Y}(i)-F_{A,B}(i)

思路

首先，意识到 \sqrt{F(x-2)F(x-1)}+1 就是 F(x-2),F(x-1) 的几何平均值加上一，且由均值不等式得到

\sqrt{F(x-2)F(x-1)}+1\leq \frac{F(x-2)+F(x-1)}{2}+1

所以得出，数列 F 一定有 F(x)=F(x+1) 且满足 x\leq\log{(F(1)\times F(2))}+1（记 x_{F_{A,B}},x_{F_{X,Y}} 分别为 F_{x,y},F_{A,B} 的第一项满足 F(x)=F(x+1) 的下标）。

那么就不难得到，在 F(x+1) 之后数列形状：

F(x+2)=F(x)+1,F(x+3)=F(x)+1,F(x+4)=F(x)+2,F(x+5)=F(x)+2\ldots

即：

F(x+n)=F(x)+\lfloor\frac{n}{2}\rfloor

那么实际上我们已经可以用 \mathcal{O}(\log{(X\times Y)}) 的时间复杂度求出 F_{X,Y}，用 \mathcal{O}(\log {A\times B}) 的时间复杂度求出 F_{A,B} 了。下面分析 \prod_{i=1}^nF_{X,Y}(i)-F_{A,B}(i)：

此式子若 n\leq \min(x_{F_{A,B}},x_{F_{X,Y}}) 还可以暴力计算，时间复杂度 \mathcal{O}(\min(\log{(A\times B)},\log{(X\times Y)}))，但是若 n 已经取到 10^9 级别，就需要考虑更快的方法了，我们推导在 \max(x_{F_{A,B}},x_{F_{X,Y}}) 以后的乘积形式：

(F_{A,B}(x)-F_{X,Y}(x))\times(F_{A,B}(x+1)-F_{X,Y}(x+1))\times\ldots

考虑 F_{A,B}(n)=F_{A,B}(x)+\lfloor\frac{n-x}{2}\rfloor，简化成为：

(F_{A,B}(x_{F_{A,B}})+\lfloor\frac{x-x_{F_{A,B}}}{2}\rfloor-F_{X,Y}(x_{F_{X,Y}})+\lfloor\frac{x-x_{F_{X,Y}}}{2}\rfloor)\times(F_{A,B}(x_{F_{A,B}})+\lfloor\frac{x+1-x_{F_{A,B}}}{2}\rfloor-F_{X,Y}(x_{F_{X,Y}})+\lfloor\frac{x+1-x_{F_{X,Y}}}{2}\rfloor)\times\ldots

易得第 x 项：

F_{A,B}(x_{F_{A,B}})+\lfloor\frac{x-x_{F_{A,B}}}{2}\rfloor-F_{X,Y}(x_{F_{X,Y}})+\lfloor\frac{x-x_{F_{X,Y}}}{2}\rfloor

不难发现，当 x_{F_{A,B}}\mod 2\equiv x_{F_{X,Y}}\mod 2 时：

F_{A,B}(x_{F_{A,B}})+\lfloor\frac{x-x_{F_{A,B}}}{2}\rfloor-F_{X,Y}(x_{F_{X,Y}})+\lfloor\frac{x-x_{F_{X,Y}}}{2}\rfloor= F_{A,B}(x_{F_{A,B}})-F_{X,Y}(x_{F_{X,Y}})

那么原式实际上就成为了：

(F_{A,B}(x_{F_{A,B}})-F_{X,Y}(x_{F_{X,Y}}))^{n-\max(x_{F_{A,B}},x_{F_{X,Y}})+1}

肉眼可见可以使用快速幂解决。

那么当 x_{F_{A,B}}\mod 2\not\equiv x_{F_{X,Y}}\mod 2 时：

(F_{A,B}(x_{F_{A,B}})+\lfloor\frac{x-x_{F_{A,B}}}{2}\rfloor-F_{X,Y}(x_{F_{X,Y}})+\lfloor\frac{x-x_{F_{X,Y}}}{2}\rfloor)\times(F_{A,B}(x_{F_{A,B}})+\lfloor\frac{x+1-x_{F_{A,B}}}{2}\rfloor-F_{X,Y}(x_{F_{X,Y}})+\lfloor\frac{x+1-x_{F_{X,Y}}}{2}\rfloor)=(F_{A,B}(x_{F_{A,B}})-F_{X,Y}(x_{F_{X,Y}}))\times(F_{A,B}(x_{F_{A,B}}+1)-F_{X,Y}(x_{F_{X,Y}}+1))

原式实际上成为：

(F_{A,B}(x_{F_{A,B}})-F_{X,Y}(x_{F_{X,Y}}))\times(F_{A,B}(x_{F_{A,B}}+1)-F_{X,Y}(x_{F_{X,Y}}+1))^{\lfloor\frac{n-\max(x_{F_{A,B}},x_{F_{X,Y}})+1}{2}\rfloor}\times (F_{A,B}(x_{F_{A,B}})-F_{X,Y}(x_{F_{X,Y}}))^{(n-\max(x_{F_{A,B}},x_{F_{X,Y}})+1)\mod 2}

同样可以使用快速幂解决。

那么这样，实际上整个程序的时间复杂度就是 \mathcal{O}(t\log n) 级别的了，完结撒代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD = 998244353;
ll t , n , a , b , x , y , cmp1 , cmp2;
long double f[105] , g[105];
ll fpow( ll xx , ll yy )
{
    if ( yy == 0 )  return 1;
    ll z = fpow( xx , yy / 2 ) % MOD;
    if ( yy % 2 )   return ( ( z * z ) % MOD * xx ) % MOD;
    else    return ( z * z ) % MOD;
}
ll ff( ll xx )
{
    if ( xx > cmp1 )    return ( ( ( xx - cmp1 ) / 2 ) % MOD + (ll)f[cmp1] ) % MOD;
    else    return (ll)f[xx];
}
ll gg( ll xx )
{
    if ( xx > cmp2 )    return ( ( ( xx - cmp2 ) / 2 ) % MOD + (ll)g[cmp2] ) % MOD;
    else    return (ll)g[xx];
}
int main()
{
    cin >> t;
    for ( ll k = 1; k <= t; k++ )
    {
        ll cmp , ans = 1;
        cmp1 = 2 , cmp2 = 2 , cin >> n >> a >> b >> x >> y , f[1] = a , f[2] = b , g[1] = x , g[2] = y;
        while ( f[++cmp1 - 1] != f[cmp1 - 2] && cmp1 <= n + 3 ) f[cmp1] = ( (ll)( sqrt( f[cmp1 - 1] * f[cmp1 - 2] ) ) + 1 ) % MOD;
        while ( g[++cmp2 - 1] != g[cmp2 - 2] && cmp2 <= n + 3 ) g[cmp2] = ( (ll)( sqrt( g[cmp2 - 1] * g[cmp2 - 2] ) ) + 1 ) % MOD;
        cmp1 -= 2 , cmp2 -= 2 , cmp = max( cmp1 , cmp2 );
        for ( ll i = 1; i <= min( n , cmp - 1 ); i++ )  ans *= ( gg( i ) - ff( i ) ) % MOD , ans %= MOD;
        if ( cmp <= n )
        {
            if ( cmp1 % 2 == cmp2 % 2 ) ans *= fpow( ( gg( cmp ) - ff( cmp ) ) % MOD , n - cmp + 1 ) , ans %= MOD;
            else
            {
                ans *= fpow( ( ( gg( cmp ) - ff( cmp ) ) % MOD * ( gg( cmp + 1 ) - ff( cmp + 1 ) ) % MOD ) % MOD , ( n - cmp + 1 ) / 2 ) , ans %= MOD;
                if ( ( n - cmp + 1 ) % 2 )  ans *= ( gg( cmp ) - ff( cmp ) ) % MOD , ans %= MOD;
            }
        }
        cout << ( ans + MOD ) % MOD << endl;
    }
    return 0;
}