swift - HackerEarth 中的不幸 13 挑战

Question

我最近遇到了这个编码挑战 - The Unlucky number 13 . (本节最后一个问题)
问题陈述:
编写一个程序来计算由 组成的字符串总数电话 人物。
任何字符串都不能将“ 13 ”作为子字符串。
字符串可以包含 0-9 之间的任何整数，重复任意次数。
输入:
N 作为输入，其中 0<= N <= 1000000009 .
输出:
输出应该是模 1000000009 的答案。
我的解决方案:
我试着用我想出的一个简单的方程来解决它。

ans = 10^n - ((10^(n-2)) * (n-1))

Subtracting the possibilities with 13 as substring from the total number of possibilities.

我用 Swift 编写了代码。当 N 小时它起作用。但是我在提交时遇到运行时错误(可能是当 N 很大时)。
这是我的代码:

let input = Int(readLine()!)
if let n = input as? Int{
    var ans = getPowerOfTen(n)
    ans = ans - getPowerOfTen(n-2) * (n - 1)
    print(ans % 1000000009)
}

// Did not import any library to calculate the power   

 func getPowerOfTen(_ num: Int)->Int{
        var ans = 1
        var n = num
        while(n > 0){
            ans = ans * 10
            n = n - 1
        }
        return ans
 }

我希望得到两个问题的帮助。

你能帮我找到运行时问题吗？
This is the screenshot of the runtime error I get from the site.

有没有更好的方法来解决这个问题？

I found this in Array & Strings problem section. I did not use anyarray though. I think this equation works.

Answer 1

公式似乎是正确的。您的解决方案有两个问题。

1: Time complexity
2: Overflow Issue

时间复杂度
您在计算 10^n mod m 时使用了幼稚的技术.您正在使用来自 1 的简单循环至 n这导致 O(n) 的复杂性.有一种非常流行的技术，称为 Binary Exponentiation计算 a^b mod m在 O(logn) .这种技术在竞争性编程中被广泛用于解决各种问题。

溢出问题
在 while 循环中，您反复更新 ans像这样:

ans = ans * 10

当值足够大时， ans将变为负数，因为它将无法存储该值。这被称为 Overflow .发现有可能发生溢出的一种好方法是在问题中提到它时:

The output should be the answer modulo 1000000009

这表明程序设置者自己知道计算量会很大，因此他们要求以这种格式输出答案。

我没有提供二进制幂运算的算法，因为它已经在提供的链接中。那里使用的算法还处理溢出问题。
我还提供了 Integer Overflow 的另一个链接，以防您想查看它。
如果您仍然遇到任何麻烦，请发表评论。