やるだけって言いながらDPを書いたらoverflowした。

solution

fibonacci数。多倍長整数の行列を繰り返し二乗する。 $\newcommand{dp}{\mathrm{dp}}$ $\newcommand{fib}{\mathrm{fib}}$

単純なDPを考えると、

  • $\dp_0 = 1$
  • $\dp_{\frac{l}{2}} = 0$
  • $\dp_{i} = \Sigma_{j \lt i, j-i \operatorname{is odd}} \dp_j$

である。

  • $\mathrm{acc}_{0,i} = \Sigma_{j \lt i, j \operatorname{is even}} \dp_j$
  • $\mathrm{acc}_{1,i} = \Sigma_{j \lt i, j \operatorname{is odd}} \dp_j$

とすると、最後の漸化式は

  • $\dp_{2i} = \mathrm{acc}_{1,2i}$
  • $\dp_{2i+1} = \mathrm{acc}_{0,2i+1}$

と書ける。

一旦$l$を無視して考えると、

  • $\dp_0 = 1$
  • $\dp_i = \fib_i$

である。ただし

  • $\fib_0 = 1$
  • $\fib_1 = 1$

とする。 これは、

  • $\dp_{2i+2} = \mathrm{acc}_{1,2i+2} = \mathrm{acc}_{1,2i} + \dp_{2i+1} = \dp_{2i} + \dp_{2i+1}$
  • $\dp_{2i+3} = \mathrm{acc}_{0,2i+3} = \mathrm{acc}_{0,2i+1} + \dp_{2i+2} = \dp_{2i+1} + \dp_{2i+2}$

となることから分かる。 よって、$l$が奇数の場合は

  • $\mathrm{ans}(l) = \fib_l$

でよい。

次に、$l$が偶数の場合について。 $\frac{l}{2}$が使えないことを考慮に入れると、$l = 2h$として、

  • $\dp_{i} = \fib_i$ if $i \lt h$
  • $\dp_{h} = 0$
  • $\dp_{h+1} = \mathrm{acc}_{h-1} + \dp_{h} = \mathrm{acc}_{h-1} = \dp_{h-1} = \fib_{h-1}$
  • $\dp_{h+2} = \mathrm{acc}_{h} + \dp_{h+1} = \dp_{h-2} + \dp_{h-1} + \dp_{h+1} = \fib_{h+1}$
  • $\dp_{h+i} = \dp_{h+i-2} + \dp_{h+i-1}$ if $i \gt 2$

である。$h+2$も例外となっている。

  • $a = \dp_{h-1} = \fib_{h-1}$
  • $b = \dp_{h-2} - \dp_{h-1} = \fib_{h+1} - \fib_{h-1} = \fib_h$

として、

  • $\dp_{h+i} = a \fib_{i} + b \fib_{i-1}$ if $i \gt 2$

と書ける。 よって、

  • $\mathrm{ans}(2h) = \dp_{h+h} = a \fib_{h} + b \fib_{h-1} = 2\fib_{h-1}\fib_{h}$

となる。

implementation

c++での多倍長整数演算は以前書いてるが、引っぱり出してくるのが面倒だった。

module Main where
import Data.Bits
import Data.Monoid

data Mat22 a = Mat22 a a a a deriving (Eq, Ord, Show, Read)

instance Num a => Monoid (Mat22 a) where
    mempty = Mat22 1 0 0 1
    mappend (Mat22 a00 a01 a10 a11) (Mat22 b00 b01 b10 b11)
        = Mat22 (a00 * b00 + a01 * b10) (a00 * b01 + a01 * b11) (a10 * b00 + a11 * b10) (a10 * b01 + a11 * b11)

fib :: Int -> Integer
fib n = unpack $ go f0 mempty 1 where
    f0 = Mat22 1 1 1 0
    go :: Mat22 Integer -> Mat22 Integer -> Int -> Mat22 Integer
    go _ g i | i > n = g
    go f g i = if n .&. i == 0
        then go (f <> f)       g  (i `shift` 1)
        else go (f <> f) (f <> g) (i `shift` 1)
    unpack (Mat22 a b c d) = b

solve :: Int -> Integer
solve l = if l `mod` 2 == 0
    then let h = l `div` 2 in 2 * fib (h-1) * fib h
    else fib l

main :: IO ()
main = do
    l <- readLn
    let y = solve l
    if y == 0
        then do
            print $ l+1
            putStrLn "INF"
        else do
            print l
            print y