>>29
途中書くの面倒になった

4*n の部屋に 1*2 の畳を敷き詰める方法を a[n] 通りとすると

a[0]=1, a[1]=1, a[2]=5, a[3]=11, a[4]=36
a[n+5] = 2a[n+4] + 4a[n+3] - 4a[n+2] - 2a[n+1] + a[n]

が成立する

これを解いて
a[5]=95, a[6]=281, a[7]=781, a[8]=2245, a[9]=6336, a[10]=18061