Flags (Editorial)

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:

By analogous reasoning, we obtain:

The initial conditions for the first recurrence are obvious:

• fr(1) = 1: A flag consisting of one stripe and starting with red can be colored in exactly one way — $R$.

• fr(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,

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

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

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);