以下、p=998244353とする。
- n≤4の時はxn<pなので、答えはxnである。
- n=5,6の時、それぞれx5=265536,x6=2265536となる。、2Nの二分累乗法での計算量はO(logN)なので、両方とも二分累乗法で解ける。答えは、n=5の時683753077、n=6の時220050301となる。
- n≥7の時、logxn−1≥logx6≃101.97×104となり、二分累乗法でも間に合わないので、他の方法を考える。
n≥7の時
以下、2aをbで割った余りをf(a,b)と表す。
まず、pは素数なので、2p−1≡1(mod p) よって、k0=f(xn−1,p−1)とすると、求める答えはf(k0,p)となる。
p−1を素因数分解すると、223×7×17となる。よって、中国剰余定理よりf(xn−1,223),f(xn−1,7),f(xn−1,17)が分かれば良い。
- まずf(xn−1,223)を求める。xn−1=2xn−2であり、数列{xn}は単調増加。よってxn−2≥x5=265536≥23 よって、xn−1は素因数2を23個以上持つので、f(xn−1,223)=0
- 次にf(xn−1,7)を求める。23≡1(mod 7)なので、k1=f(xn−2,3)とすると、f(xn−1,7)=f(k1,7)である。
xn−3は偶数なので、mod 3においてxn−2=2xn−3≡(−1)xn−3=1 よって、k1=1よりf(xn−1,7)=2
- 最後にf(xn−1,17)について考える。xn−2=2xn−3であり、xn−3≥x4=65536≥4 よって、xn−2は素因数2を4個以上持つので、24=16の倍数。よって、216≡1(mod 17)より、f(xn−1,17)=1
以上3つの結果から、k0=444596224となので、求める答えはf(k0,p)=220050301
まとめ
以上より、答えは⎩⎨⎧xn if n≤4683753077 if n=5220050301 if n≥6 計算量はO(1)である。
質問・誤りがある場合
Twitterに連絡ください。ID : @YS55749378