FZU Problem 2200 cleaning dp

Problem Description

N个人围成一圈在讨论大扫除的事情，需要选出K个人。但是每个人与他距离为2的人存在矛盾，所以这K个人中任意两个人的距离不能为2，他们想知道共有多少种方法。

Input

第一行包含一个数T(T<=100)，表示测试数据的个数。

接下来每行有两个数N，K，N表示人数，K表示需要的人数(1<=N<=1000,1<=K<=N)。

Output

输出满足题意的方案数，方案数很大，所以请输出方案数mod 1,000,000,007 后的结果。

Sample Input

2 4 2 8 3

Sample Output

4 16

唔，这次月赛日了狗把．Ａ题矩阵快速幂常数卡的想日狗！

这题一开始看错题看成线性的，于是写下了这个dp方程：dp[i][j] = dp[i-3][j-1] + dp[i-4][j-2]+ dp[i-1][j] ;

dp[i][j]表示前i个人选j个人合法的方案数

嗯,怎么看都很对的样子对吧，然而第二个样例１６跑不出来,花了几乎半小时才发现是环形的,然而没关系233333前面写好的代码可以不用重写,发现假设首个格子和尾格子全没放，只有首或尾放，首和尾全放一共四种情况,讨论一下就可以Ｏ（１）成线性的的了

然后边界发现好麻烦，干脆小于６的全部打表，于是写下了如此丑陋的代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define maxn 2000

#define MOD 1000000007

using namespace std;

long long dp[maxn][maxn];

int main()

{

    int t;

    int n,k;

    scanf("%d",&t);

    dp[][]= dp[][] = dp[][] = ;

    dp[][]=;dp[][]=;dp[][]=;

    dp[][]=;dp[][]=;dp[][]=;

    for(int i=;i<=;i++)

    {

        dp[i][] = ;

        dp[i][] = i;

        for(int j=;j<=(i);j++)

        {

            dp[i][j] = ((dp[i-][j-] + dp[i-][j-])%MOD + dp[i-][j]) % MOD;

        }

    }

    int an[][]={};

    an[][]=an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    an[][]=;

    while(t--)

    {

        scanf("%d%d",&n,&k);

        long long ans=;

        if(n<=)

        {

            printf("%d\n",an[n][k]);

            continue;

        }

        ans = ((dp[n-][k] + *(dp[n-][k-]+ (dp[n-][k-]))%MOD)%MOD+ dp[n-][k-])%MOD;

        //cout<<fac[k]<<" "<<fac[n-k]<<endl;

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西