使用组合学改进计算外观的运行时间

Question

我想计算有多少d位数不包括数字9,因为它可以很大,输出模10 ^ 9 + 7.

我运行以下代码t次,最多10 ^ 18位数字,我想解决功能应该很容易,对吧？那么也许阅读或印刷需要花费很多时间.

任何提示如何加快速度？

main = do
    contents <- getContents
    let (t:ds) = (map read . words) contents
    let ans = map solve ds
    sequence_ (map print ans)

solve :: Integer -> Integer
solve ds = mod (8 * 9^(ds - 1)) (10^9 + 7)

Answer 1

我认为网站想要看到的是,你掌握了模数乘法的概念.它认为:

(a * b) mod c == ((a mod c) * (b mod c)) mod c

此外,他们没有10^9+7 任意选择:据我所知,它是一个巨大的素数而不是32位整数.因此,我们可以使用所有的微积分Int32,这比使用更快Integer(具有任意精度).

乘法方法(效率较低)

因此,我们可以创建自己的mulmod功能:

mulmod :: Int32 -> Int32 -> Int32 -> Int32
mulmod m a b = mod (a*b) m

现在我们可以用以下公式计算模数m:

solvemod :: Int32 -> Int -> Int32
solvemod m d = foldl (mulmod m) 8 (replicate (d-1) 9)

然后问题可以解决:

solve :: Int -> Int32
solve = solvemod (10^9+7)

对于给定的样本输入,它会导致:

Prelude> solve 1
8
Prelude> solve 2
72
Prelude> solve 100
343393926

这是 - 根据网站 - 正确.

权力方法

然而,它仍然是低效的.我们可以定义一个powmod像:

powmod :: Integral i => Int64 -> Int64 -> i -> Int64
powmod m = powmod'
    where powmod' _ 0 = 1
          powmod' a i | even i = rec
                      | otherwise = mod (a*rec) m
              where rec = powmod' (mod (a*a) m) (div i 2)

然后solve机制是:

solve :: Integral i => i -> Int64
solve d = mod (8 * powmod m 9 (d-1)) m
    where m = 10^9+7

再次导致:

*Main> solve 1
8
*Main> solve 2
72
*Main> solve 100
343393926
*Main> solve (10^18)
303706813

最后一个查询只花了几毫秒,所以我觉得这很有效.我向Kattis提交了最后一种方法,并得到了:

15:29:31"我讨厌第九号"接受0.01秒Haskell

因此,只需0.01秒即可计算出测试用例.