9558. Flags

The flag consists of n vertical stripes, each of which can be colored white, red, or blue. Moreover:

· No two adjacent stripes may have the same color.

· Any blue stripe must be placed between a red and a white stripe (in any order).

How many ways are there to color a flag with n stripes?

Input. One integer n (1 ≤ n ≤ 10⁶) – the number of stripes on the flag.

Output. Print the number of ways to color a flag with n stripes. The answer should be given modulo 10⁹ + 7.

Sample input	Sample output
3	4

SOLUTION

Fibonacci numbers

Algorithm analysis

Let:

· f_r(n) be the number of ways to color a flag with n stripes, starting with a red stripe;

· f_w(n) be the number of ways to color a flag with n stripes, starting with a white stripe.

Let’s consider how to compute the function f_r(n):

· If the stripe following the red one is white, then the remaining flag of length n – 1 can be colored in f_w(n – 1) ways;

· If the stripe following the red one is blue, then the stripe after the blue one must be white. After that, the remaining flag of length n – 2 can be colored in f_w(n – 2) ways;

Thus, we obtain the following equality:

f_r(n) = f_w(n – 1) + f_w(n – 2)

By analogous reasoning, we obtain:

f_w(n) = f_r(n – 1) + f_r(n – 2)

The initial conditions for the first recurrence are obvious:

· f_r(1) = 1: A flag consisting of one stripe and starting with red can be colored in exactly one way – R.

· f_r(2) = 1: If the first stripe is red, then the second stripe cannot be red and cannot be blue (since a blue stripe must be placed between a red and a white stripe). Therefore, the second stripe must be white. The only possible arrangement is RW.

Similarly,

f_w(1) = 1, f_w(2) = 1

Both functions f_r(n) and f_w(n) define Fibonacci numbers:

f_r(n) = F_n,

f_w(n) = F_n

The coloring of the flag starts with the first stripe. It can be either red or white. Therefore, the total number of ways to color the flag is

f_r(n) + f_w(n) = 2 * F_n

Algorithm implementation

Declare the constants.

#define MAX 1000001

#define MOD 1000000007

Declare an array fib to store the Fibonacci numbers.

long long fib[MAX];

Read the input value n.

scanf("%d", &n);

Fill the array fib with Fibonacci numbers.

fib[1] = 1; fib[2] = 1;

for (i = 3; i < MAX; i++)

fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;

Print the answer.

printf("%lld\n", (2 * fib[n]) % MOD);