不难发现，只有$1 * 2, 2 * 2$两种方法

因此，设$f[i]$表示填满$1 - i$的方案数

那么有$f[i] = f[i - 1] + f[i - 2]$，其实就是斐波那契数列....

复杂度$O(n)$

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define ri register int#define mod 1000000007int n;int f[1005];int main() {    cin >> n;    f[0] = 1; f[1] = 1;    for(ri i = 2; i <= n; i ++)    f[i] = (f[i - 1] + f[i - 2]) % mod;    printf("%d\n", f[n]);    return 0;}