I think this can be solved via recursion:
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
Base Cases:
It's implementation is running quite fast even for larger inputs like 10^9
( which is expected as its complexity is O(log[n])
instead of O(n)
like the other answers ):
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)
Online Demo
Explanation:
Let a string s
have even number of digits 'n'.
Let ans(n)
be the answer for the input n
, i.e. the number of strings without the substring 13
in them.
Therefore, the answer for string s
having length n
can be written as the multiplication of the answer for the first half of the string (ans([n/2])
) and the answer for the second half of the string (ans([n/2])
), minus the number of cases where the string 13
appears in the middle of the number n
, i.e. when the last digit of the first half is 1
and the first digit of the second half is 3
.
This can expressed mathematically as:
ans(n) = ans([n/2])^2 - ans([n/2]-1)*2
Similarly for the cases where the input number n
is odd, we can derive the following equation:
ans(n) = ans([n/2]+1)*ans([n/2]) - ans([n/2])*ans([n/2]-1)
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…