Yukicoder No.303 割れません
やるだけって言いながら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