HackerEarth 中的倒霉 13 挑战

Question

我最近遇到了这个编码挑战 - The Unlucky number 13。（本节最后一道题）

问题陈述：

编写一个程序来计算正好由 N 个字符组成的字符串的总数。 None 个字符串可以将“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 较小时有效。但是我在提交时遇到运行time 错误（可能是当 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 any array though. I think this equation works.

Answer 1

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

1: Time complexity
2: Overflow Issue

时间复杂度

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

溢出问题

在 while 循环中，您重复更新 ans，如下所示：

ans = ans * 10

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

The output should be the answer modulo 1000000009

这表明程序 setter 自己知道计算量很大，所以他们要求以这种格式输出答案。

我没有提供 二进制求幂算法，因为它已经存在于所提供的 link 中。那里使用的算法也处理溢出问题。我还提供了 另一个 link 用于整数溢出 以防你想查看它。

如果您仍然遇到任何问题，请发表评论。

HackerEarth 中的倒霉 13 挑战

The Unlucky 13 Challenge in HackerEarth

algorithm

equation

runtime-error

permutation

swift

时间复杂度

溢出问题