假设矩形不可以旋转，那么枚举上下分了多少有式子：

$\sum\limits_{i=1}^{k-1} {n-1\choose i-1}\times {n-1\choose k-i-1}$

之所以是 $n-1\choose i-1$ 而不是 $n\choose i$ 是因为如果考虑枚举一个长方形第一个的位置，那么为了保证所有的位置都被覆盖，所以第一个的位置是确定的。

考虑从插板法的角度思考，如果上面的式子就相当于有 $2n-2$ 个空子，我们分开枚举第一个空子插 $i-1$ 个板而第二个空子插 $k-i-1$ 个板，所以根据组合意义就有结论：

$\sum\limits_{i=1}^n {n-1\choose i-1}\times{n-1\choose k-i-1}={2\times(n-1)\choose k-2}$

回到原本的问题，我们可以考虑枚举选取了多少的竖着的长方形，将原本的 $2\times n$ 的长方形分割成若干个小长方形然后再在里面跑上面的东西。

假设有 $i$ 个 $1\times 2$ 的东西，有 $j$ 段 $1\times 2$ 的长方形是连在一起的。

不存在竖着在开头

那么有 $2\times(n-1-i-j)$ 个位置放，这是因为每一个 $1\times 2$ 的长方形的前面都不能放，而每一段的末尾的那一个长方形的空子也不能放。

那么因为原本已经分成了 $2\times (j+1)$ 段而每插一个板都增加一个长方形，所以我们只需要新插 $k-2\times(j+1)-i$ 个板就能产生 $k$ 个长方形。

所以方案数为：

$2\times (n-1-i-j)\choose k-2\times(j+1)-i$

只有一个数在开头或者结尾

那么有 $2\times (n-i-j)$ 个位置放置，因为第 $1$ 段的开头或者左后一段的结尾本来就不能放。

因为原本已经为分成了 $2\times j$ 段，所以只需要插 $k-2\times j-i$ 个板就行了，所以方案数为：

$2\times (n-i-j)\choose k-2\times j-i$

开头和结尾都有放置

那么有 $2\times (n-i-j+1)$ 个位置放置，而原来已经被分了 $2\times (j-1)$ 段，所以只需要插 $k-2\times (j-1)-i$ 个板就行了，方案数为：

$2\times (n-i-j+1)\choose k-2\times(j-1)-i$

竖着的放置

先把 $i$ 个 $1\times 2$ 的板子分成 $j$ 组，显然方案数为 $i-1\choose j-1$。

接下来再把 $j$ 组插入原本的序列中，那么根据首尾的插入情况，就可以得到方案数为：

${n-i-1\choose j},{n-i-1\choose j-1},{n-i-1\choose j-2}$

时间复杂度为 $O(n+k^2)$，其中 $O(n)$ 是预处理的时间复杂度。