nyoj 980 格子刷油漆

格子刷油漆

描述

　　X國的一段古城牆的頂端可以看成 2*N個格子組成的矩形（如下圖所示），現需要把這些格子刷上保護漆。

vc/UtrXEJiMyNjY4NDvX06Oo0vLOqtPNxuHOtLjJsrvE3LLIo6GjqTwvcD4KPHA+CqGhoaGxyMjno7phIGQgYiBjIGUgZiC+zcrHus8mIzI2Njg0O7XEy6LG4cuz0PKhozwvcD4KPHA+CqGhoaFjIGUgZiBkIGEgYiDKx8Ht0rvW1rrPysq1xLe9sLihozwvcD4KPHA+CqGhoaG1sdLR1qogTiDKsaOsx/PX3LXEt72wuMr9oaO1sU69z7TzyrGjrL3hufu74dG4y9nU9rTzo6zH67DRveG5+7bUIDEwMDAwMDAwMDcgKMqu0trB48bfKSDIocSjoaM8L3A+Cgo8ZGwgY2xhc3M9"others">

輸入

　　輸入數據為一個正整數（不大於1000）

輸出

　　輸出數據為一個正整數。

樣例輸入

2
3
22

樣例輸出

24
96
359635897

說這道題目是一道dp題目。 不如說這是一道數學題目。

遞推公式比較復雜


一共有兩個遞推數組：


首先設Dn表示從左邊或者右邊的某個角出發，然後走遍所有格子回到同一列有多少種方法。
明顯D1=2,Dn=2*Dn-1
所以Dn=2^n


然後設An表示從某個角出發，走遍所有格子（不一定回到同一列）有多少種方法。
An=Dn+2*An-1+4*An-2
這個遞推公式就用統計原理分析出來，分別對應三種不同的走法
Dn對應從這個角走到下一列，然後走遍所有格子回到下一列，再回到這列的走法
2*An-1表示直接走到這列的另一個角，然後再走其他的地方
4*An-2表示走對角線方法走遍前兩列，然後走其他的地方


這樣答案如果從四個角出發，總數就是4*An


然後分析從某一列開始，假設第i列(1 則總數為2*(2*Di-1*An-i+2*Dn-i*Ai-1)
對i從2到n-1全部加和，得到這部分答案


兩部分答案加起來，就是總數，經測試無誤

#include 
long long a[1001]= {0},b[1001]={0};
const int NUM=1000000007;
int main()
{
    int i,n;
    while(~scanf("%d",&n))
    {
        b[1]=1;
        for (i=2; i<=n; i++)
            b[i]=(b[i-1]*2%NUM);
        a[1]=1;
        a[2]=6;
        for (i=3; i<=n; i++)
            a[i]=(2*a[i-1]+b[i]+4*a[i-2])%NUM;
        long long sum=4*a[n];
        for (i=2; i