Question

这个递推式怎么推导的？

//N为奇数时无解 N为偶数时 F[N] = 4 *　F[N-2] - F[N-4]#include<bits/stdc++.h>using namespace std;const int maxn = 1010;const int mod = 100003;int f[maxn];int main(){ f[2] = 3; f[4] = 11; int n; for(int i = 6;i < maxn;i+=2)f[i] = ((4*f[i-2])%mod -f[i-4]+mod)%mod; while(~scanf("%d",&n)&&n){ if(n&1){puts("0");continue;} printf("%d\n",f[n]); } return 0;}

Answer 1

很有意思的一个公式。

首先N为奇数的时候 无解，这个很容易理解。因为从面积上，用1*2铺成的总面积，必然是2的倍数。而N为奇数的时候 总面积为3*N，同样是奇数。 自然无解。

以横向的3*N为例，即三行，N列。

当N为偶数的时候，最右侧的2列，也就是最后的2*3格子，有两种情况，

1 、2*3正好被3个1*2的填满，这时有三种可能：

其实就是N=2的三种情况。这种情况总数为3*F[N-2]

2、 2*3不被3个1*2填充，这样最右侧的两列，有两种可能，如下图：

可以自己画一下，只有这两种可能。 这种情况的总数是未知的，假定为G[N]

这里得到第一个公式

公式一：F[N]=3*F[N-2]+G[N]

那么这种继续向左铺，又每种有两个可能，一个是正好一个1*2的方块，把空白部分补满，形成这个效果

这样的时候，总数是2*F[N-4]。

另外一种可能，就是继续横向的向左摆，

注意最左侧的边缘形状是和之前相同的，所以这种情况，其实就是G[N-2]个。

所以 可以得到一个公式：

公式二：G[N]=2*F[N-4]+G[N-2]

接下来，回过头来看公式一：

F[N]=3*F[N-2]+G[N] 将N替换为N-2，得到

F[N-2]=3*F[N-4]+G[N-2] ==>  G[N-2]=F[N-2]-3*F[N-4]

带入到公式二：

G[N]=2*F[N-4]+G[N-2]=2*F[N-4]+F[N-2]-3*F[N-4]=F[N-2]-F[N-4]

得到G[N]后，再带回公式一：

F[N]=3*F[N-2]+G[N]=3*F[N-2]+F[N-2]-F[N-4]=4*F[N-2]-F[N-4]

这个就是最终的递推公式了。

追问

服！