我想数一下有多少个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)
2条答案
按热度按时间gwbalxhn1#
我认为网站希望看到的是你掌握 * 模乘 * 的概念。它认为:
此外,他们并没有随意选择
10^9+7
*:据我所知,它是一个巨大的质数,比32位整数所能表示的还要大。因此,我们可以用Int32
来做所有的微积分,这比用Integer
(具有任意精度)来做要快。乘法法(效率较低)
因此,我们可以创建自己的
mulmod
函数:现在,我们可以计算数字模
m
:然后这个问题就可以用下面的公式来解决:
对于给定的样本输入,其结果为:
根据网站的说法,这是正确的。
动力接近
我们可以定义一个
powmod
,如下所示:则
solve
机制为:再次导致:
最后一个查询只花了几毫秒的时间,所以我想这已经足够高效了。
15:29:31“我讨厌数字九”接受0.01 s Haskell
因此,计算测试用例仅需0.01秒。
t3irkdon2#
是的,这是一个简单的算术问题,可以很容易地处理在基地9,因为我们将只下降一个数字字符。如果你不想使用2个数字字符,如我不想9和4,那么你应该去与基地8。所以我的解决方案将是;