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

Question

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

我运行以下代码 t 次，最多 10^18 位数字，我猜 solve 函数应该很容易处理，对吧？那么可能是阅读或打印比较耗时。

有什么技巧可以加快速度吗？

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 "I Hate The Number Nine" Accepted 0.01 s Haskell

所以计算测试用例只用了0.01s。

Answer 2

是的，这只是一个简单的算术问题，可以很容易地以 9 为基数处理，因为我们将只删除一个数字字符。如果您不想使用 2 个数字字符，例如我不想使用 9 和 4，那么您应该使用基数 8。所以我的解决方案是；

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

*Main> solve 1
8
*Main> solve 2
72
*Main> solve 100
343393926

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

Improve runtime of counting appearances with combinatorics

algorithm

haskell

runtime

combinatorics

乘法方法（效率较低）

权力接近