Algorithm Analysis

Let's denote by $f(n)$ the number of ways in which a 2 × $n$ rectangle can be covered with 2 × 1 domino pieces. Obviously,

• $f(1)=1$, one vertical piece;

• $f(2)=2$, two vertical or two horizontal pieces.

Consider the algorithm for calculating $f(n)$. One can place one piece vertically and then cover the rectangle of length $n–1$ in $f(n–1)$ ways, or place two pieces horizontally and then cover the rectangle of length $n–2$ in $f(n–2)$ ways. Thus, $f(n)=f(n–1)+f(n–2)$.

Thus, $f(n)$ is a Fibonacci number.

Algorithm Implementation

Since $n<65536$, one should use long arithmetic or the Java programming language.

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