2↑↑n

2 secs 1024 MB
YSatUT's icon YSatUT
Tweet
問題
提出
テストケース
解説

以下、p=998244353p=998244353とする。

  • n≤4n\leq4の時はxn<px_n<pなので、答えはxnx_nである。
  • n=5,6n=5,6の時、それぞれx5=265536,x6=2265536x_5=2^{65536},x_6=2^{2^{65536}}となる。、2N2^Nの二分累乗法での計算量はO(log⁡N)O(\log N)なので、両方とも二分累乗法で解ける。答えは、n=5n=5の時683753077683753077、n=6n=6の時220050301220050301となる。
  • n≥7n\geq 7の時、log⁡xn−1≥log⁡x6≃101.97×104\log x_{n-1}\geq \log x_6\simeq 10^{1.97\times 10^4}となり、二分累乗法でも間に合わないので、他の方法を考える。

n≥7n\geq 7の時

以下、2a2^aをbbで割った余りをf(a,b)f(a,b)と表す。\\ まず、ppは素数なので、2p−1≡1(mod p)2^{p-1}\equiv 1({\rm mod}\ p) よって、k0=f(xn−1,p−1)k_0=f(x_{n-1},p-1)とすると、求める答えはf(k0,p)f(k_0,p)となる。\\ p−1p-1を素因数分解すると、223×7×172^{23}\times7\times17となる。よって、中国剰余定理よりf(xn−1,223),f(xn−1,7),f(xn−1,17)f(x_{n-1},2^{23}),f(x_{n-1},7),f(x_{n-1},17)が分かれば良い。

  • まずf(xn−1,223)f(x_{n-1},2^{23})を求める。xn−1=2xn−2x_{n-1}=2^{x_{n-2}}であり、数列{xn}\left\{x_n\right\}は単調増加。よってxn−2≥x5=265536≥23x_{n-2}\geq x_5=2^{65536}\geq23　よって、xn−1x_{n-1}は素因数22を2323個以上持つので、f(xn−1,223)=0f(x_{n-1},2^{23})=0
  • 次にf(xn−1,7)f(x_{n-1},7)を求める。23≡1(mod 7)2^3\equiv1({\rm mod}\ 7)なので、k1=f(xn−2,3)k_1=f(x_{n-2},3)とすると、f(xn−1,7)=f(k1,7)f(x_{n-1},7)=f(k_1,7)である。\\ xn−3x_{n-3}は偶数なので、mod 3{\rm mod}\ 3においてxn−2=2xn−3≡(−1)xn−3=1x_{n-2}=2^{x_{n-3}}\equiv(-1)^{x_{n-3}}=1 　よって、k1=1k_1=1よりf(xn−1,7)=2f(x_{n-1},7)=2
  • 最後にf(xn−1,17)f(x_{n-1},17)について考える。xn−2=2xn−3x_{n-2}=2^{x_{n-3}}であり、xn−3≥x4=65536≥4x_{n-3}\geq x_4=65536\geq4　よって、xn−2x_{n-2}は素因数22を44個以上持つので、24=162^4=16の倍数。よって、216≡1(mod 17)2^{16}\equiv1({\rm mod}\ 17)より、f(xn−1,17)=1f(x_{n-1},17)=1

以上3つの結果から、k0=444596224k_0=444596224となので、求める答えはf(k0,p)=220050301f(k_0,p)=220050301

まとめ

以上より、答えは{xn  if  n≤4683753077  if  n=5220050301  if  n≥6\left\{\begin{array}{l}x_n\ \ {\rm if}\ \ n\leq4 \\ 683753077\ \ {\rm if}\ \ n=5 \\ 220050301\ \ {\rm if}\ \ n\geq6 \end{array}\right.　計算量はO(1)O(1)である。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378