不幸的是13号

Question

我来了这个问题倒霉的13号!最近但想不到有效的解决方案.

问题陈述 :

N被视为输入.

N可以非常大0 <= N <= 1000000009

查找由不包含"13"的N个字符组成的此类字符串的总数.字符串可以包含0-9的任何整数,重复任意次.

# Example:

# N = 2 :
# output : 99 (0-99 without 13 number)

# N =1 :
# output : 10 (0-9 without 13 number)

我的解决方案

N = int(raw_input())

if N < 2:
    print 10

else:
    without_13 = 10

    for i in range(10, int('9' * N)+1):
        string = str(i)
        if string.count("13") >= 1:
            continue
        without_13 += 1
    print without_13

产量

输出文件应包含模块1000000009的新行中每个查询的答案.

还有其他任何有效的解决方法吗？我的解决方案在编码站点上超出了时间限制.

Answer 1

我认为这可以通过递归解决：

ans(n) = { ans([n/2])^2 - ans([n/2]-1)^2 }, if n is even
ans(n) = { ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1) }, if n is odd

基本案例：

• ans(0) = 1
• ans(1) = 10

它的实现甚至像大投入相当快运行10^9（预计其复杂性O(log[n])，而不是O(n)像其他的答案）：

cache = {}

mod = 1000000009

def ans(n):
    if cache.has_key(n):
        return cache[n]

    if n == 0:
        cache[n] = 1
        return cache[n]
    if n == 1:
        cache[n] = 10
        return cache[n]

    temp1 = ans(n/2)
    temp2 = ans(n/2-1)

    if (n & 1) == 0:
        cache[n] = (temp1*temp1 - temp2*temp2) % mod
    else:
        temp3 = ans(n/2 + 1)
        cache[n] = (temp1 * (temp3 - temp2)) % mod

    return cache[n]

print ans(1000000000)

在线演示

解释：

让一个字符串s有偶数个数字“n”。
让我们ans(n)作为输入的答案n，即不包含子字符串的字符串数13。
因此，s具有长度的字符串的答案n可以写成字符串前半部分ans([n/2])的答案( ) 和字符串后半部分的答案( )的乘积ans([n/2])，减去该字符串13出现在字符串中的情况数数字的中间n，即前半部分的最后一位数字是 ，后半部分1的第一位数字是3。

这可以用数学表示为：

ans(n) = ans([n/2])^2 - ans([n/2]-1)*2

同样对于输入数n为奇数的情况，我们可以推导出以下等式：

ans(n) = ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1)

Answer 2

我觉得这个问题的设计期望你最初本能地按照你的方式去做.但是,我认为有一种稍微不同的方法会更快.

您可以自己生成包含数字13的所有数字,而无需遍历中间的所有数字.例如:

2位数:13

3位数位置1:113 213 313等

3位数位置2:131 132 133等

因此,您不必检查从0到n*9的所有数字.您只需计算其中包含13的所有数字,直到长度大于N.

这可能不是最快的解决方案(事实上,如果通过使用一些数学技巧无法有效地解决这个问题,我会感到惊讶)但我相信它会比你目前采用的方法更有效.