自动搬运

查看原文

来自洛谷，原作者为

	ztntonny Through the path of the clouds, kiss only the footprints of the climbers.

搬运于2025-08-24 22:44:04，当前版本为作者最后更新于2023-01-20 13:13:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

题意

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

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

$$\left\{ \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;
}