本文共 837 字，大约阅读时间需要 2 分钟。

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 128M，其他语言256M

牛牛有一块"2n"的空白瓷砖并且有足够多的"12"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.

输入描述:

输出描述:

输入例子1:

输出例子1:

这是一个比较简单的动态规划：

#include 
   
    #include
    
     using namespace std;const int maxn=1e6;int p=10007;int dp[maxn];int main(){       int t;    cin>>t;    while(t--)    {           int x;        cin>>x;        memset(dp,0,sizeof dp);        dp[1]=1;        dp[2]=2;        dp[3]=4;        for(int i=4;i<=x;i++)        {               dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%p;        }        cout<
     
      <