Problem 1: Ocean's Anti-11

https://open.kattis.com/problems/anti11

Given $n$, find the number of binary strings of length$n$that do not contain 11 as a substring.

We can consider 2 types of binary strings: those that end in 0, and those that end in 1.

Consider a string that ends in 1: if we want to extend it by a letter, then the next value must be 0. Otherwise, if we want to extend a string ending in 0, the next value can be either 1 or 0.

Let's think about this backwards:

• If the current string ends in 1, then the previous string (which we extended by one letter) must have ended in 0.

  • Thus, the number of strings ending in 1 of the current length $n$must equal to the number strings ending in 0 of length $n - 1$.

• If the current string ends in 0, then the previous string could have ended in 0 or 1.

  • Thus, the number of strings ending in 0 of length $n$equals to the number strings ending in 0 of length $n - 1$, plus the number of strings ending in 1 of length $n - 1$.

Base cases:

• end0[0] = 0, end0[1] = 1

  • there are 0 strings of length 0 ending in 0

  • there is 1 string of length 1 ending in 0

• end1[0] = 0, end1[1] = 1

  • there are 0 strings of length 0 ending in 1

  • there is 1 string of length 1 ending in 1

Recurrence relation:

• end0[i] = end0[i-1] + end1[i-1]

• end1[i] = end0[i-1]

The final answer is given by end0[n] + end1[n].

Remember to useunsigned long longand take modulo 1000000007 after each addition.