Прапори (Розбір)

Нехай:

• f_r(n) — кількість способів розмалювати прапор з $n$ смуг, почавши з червоної смуги;

• f_w(n) — кількість способів розмалювати прапор з $n$ смуг, почавши з білої смуги;

Розглянемо обчислення функції f_r(n):

• Якщо наступною після червоної поставити білу смугу, то залишившийся прапор довжини n - 1 можна розмалювати f_w(n - 1) способами;

• Якщо наступною після червоної поставити синю смугу, то за синьою повинна стояти біла смуга. Після чого залишившийся прапор довжини n - 2 можна розмалювати f_w(n - 2) способами;

Отже, маємо рівність:

Аналогічними міркуваннями отримуємо:

Початкові умови для першої рекурентності очевидні:

• fr(1) = 1: Прапор з однієї смуги, що починається з червоної, може бути розмальований лише одним способом — $R$.

• fr(2) = 1: Якщо перша смуга червона, то друга не може бути червоною і не може бути синьою (синя повинна знаходитися між червоною і білою), отже, друга смуга повинна бути білою. Єдиний варіант — $RW$.

Аналогічно

Обидві функції — і f_r(n) і f_w(n) задають числа Фібоначчі:

Розмальовування прапора починається з першої смуги. Вона може бути або червоною, або білою. Отже, загальна кількість способів розмалювати прапор дорівнює

Реалізація алгоритму

Оголосимо константи.

#define MAX 1000001
#define MOD 1000000007

Оголосимо масив $fib$ для зберігання чисел Фібоначчі.

long long fib[MAX];

Читаємо вхідне значення $n$.

scanf("%d", &n);

Заповнюємо масив $fib$ числами Фібоначчі.

fib[1] = 1; fib[2] = 1;
for (i = 3; i < MAX; i++) 
  fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;

Виводимо відповідь.

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