Доміно (Розбір)

Позначимо через $f(n)$ кількість способів покрити прямокутник 2 \times n доміно 2 \times 1. Очевидно, що

• f(1) = 1, одна вертикальна доміношка;

• f(2) = 2, або дві вертикальні, або дві горизонтальні доміношки.

Розглянемо алгоритм обчислення $f(n)$:

• можна покласти одну доміношку вертикально, після чого залишковий прямокутник довжини n - 1 покривається f(n - 1) способом,

• або покласти дві доміношки горизонтально, після чого залишковий прямокутник довжини n - 2 покривається f(n - 2) способами.

Таким чином, отримуємо рекурентне співвідношення:

Таким чином, $f(n)$ є числом Фібоначчі.

Java реалізація

Оскільки n < 65536, то слід скористатися довгою арифметикою або мовою програмування Java.

import java.util.*;
import java.math.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    
    BigInteger a = new BigInteger("1"), b = a;
    for(int i = 0; i < n; i++)
    {
      BigInteger temp = a.add(b); 
      a = b;
      b = temp;
    }
    
    System.out.println(a);    
    con.close();
  }
}

Python реалізація

Збільшуємо ліміт до потрібного числа (наприклад, $100000$ цифр)

import sys
sys.set_int_max_str_digits(100000)

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

n = int(input())

Обробляємо базові випадки.

if n == 1:
  print(1)
elif n == 2:
  print(2)
else:

Обчислюємо $n$-е число Фібоначчі.

  f1, f2 = 1, 2
  for i in range(n - 2):
    temp = f1 + f2
    f1, f2 = f2, temp

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

  print(f2)