nyoj 980 格子刷油漆

落日映苍穹つ 2022-08-25 15:50 95阅读 0赞

##  ##

## 格子刷油漆 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

X国的一段古城墙的顶端可以看成 2\*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。

![RequireFile.do_fid_HLt96rLF][]

你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）

比如：a d b c e f 就是合格的刷漆顺序。

c e f d a b 是另一种合适的方案。

当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。

输入

输入数据为一个正整数（不大于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<i<n)  
则总数为2\*(2\*Di-1\*An-i+2\*Dn-i\*Ai-1)  
对i从2到n-1全部加和，得到这部分答案  
  
  
两部分答案加起来，就是总数，经测试无误

#include <stdio.h>
    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<n; i++)
            {
                sum+=((8*b[n-i]*a[i-1])%NUM+(8*a[n-i]*b[i-1])%NUM)%NUM;
                sum %= NUM;
            }
            if(n==1)  sum=2 ;
            printf("%lld\n",sum);
        }
        return 0;
    }

[RequireFile.do_fid_HLt96rLF]: http://lx.lanqiao.org/RequireFile.do?fid=HLt96rLF