曆屆試題 格子刷油漆
問題描述
X國的一段古城牆的頂端可以看成 2*N個格子組成的矩形（如下圖所示），現需要把這些格子刷上保護漆。
你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數），但不能移動到較遠的格子（因為油漆未幹不能踩！）
比如：a d b c e f 就是合格的刷漆順序。
c e f d a b 是另一種合适的方案。
當已知 N 時，求總的方案數。當N較大時，結果會迅速增大，請把結果對 1000000007 (十億零七) 取模。
輸入格式
輸入資料為一個正整數（不大于1000）
輸出格式
輸出資料為一個正整數。
樣例輸入
2
樣例輸出
24
樣例輸入
3
樣例輸出
96
樣例輸入
22
樣例輸出
359635897
思路：畢竟是決賽題，難度是很大的（對我來說），看了這位部落客的思路，才發現規律真的很奇妙，導航門https://www.jianshu.com/p/214d09476203
1構造數組a[x]、b[x]。a[x]表示在2 * x的格子條件下，從四個角任意一個角的格子出發，周遊全體格子的方法總數，b[x]表示在2 * x的條件下，從四個角任意一個角的格子出發，周遊全體格子後回到與之相對的格子中的方法總數。
顯然，a[1]=1，b[1]=1。
遞推式：
a[x]=
b[x]=b[x-1] * 2
推導如下：
-
先考慮出發點在角上，從一個角出發，隻有3種可能性。
（1）先去同一列相鄰的格子，然後前往下一列，這就簡化成從2 * (x-1)的格子中，從一個角出發，周遊全體格子的 問題。因為前往下一列有兩種選法，是以有2 * a[x-1]種方法。
（2）先去相鄰列的同一行的格子。又分為：
先去左下角，再去右邊部分， a[x-2] * 2種方法
先周遊右邊的所有，再回來左下角，b[x-1]種方法
（3）先去右下角的格子，又分為：
先去左邊格子，再周遊右邊，a[x-2] * 2種方法
先周遊右邊，再去左邊，b[x-1]種方法
整理可得
a[x]=a[x-1] * 2+a[x-2] * 4+b[x-1] * 2
b[x]=2 * b[x-1]
而從中間某列的一點（2種選擇）出發時，顯然不能直接往下走，否則無法周遊所有的點，應當先周遊左邊（右邊）左右的點，然後回到相對的點，再周遊右邊（左邊）的點。假設從第i列出發，出發的點有兩種選擇，第二步也有兩種選擇，是以所有的走法有2 * (b[i-1] * 2 * 2 * a[n-i]+ 2 * b[n-i] * 2 * a[i-1])種。加法的前一半時先周遊左邊，後一半是先周遊右邊。
于是，總數就是4 * a[x]+Σ（2到n-1）2 * (b[i-1] * 2 * 2 * a[n-i]+ 2 * b[n-i] * 2 * a[i-1])
代碼方面注意對取餘的處理就行了
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 int main()
6 {
7 int x;
8 cin >> x;
9 long long int a[x+1];
10 long long int b[x+1];
11 a[1]=1;
12 b[1]=1;
13 a[2]=6;
14 long long int def=1000000007;
15 for(int i=2;i<=x;i++){
16 b[i]=(b[i-1]*2);
17 b[i]%=def;
18 }
19 for(int i=3;i<=x;i++){
20 a[i]=(a[i-1]*2+a[i-2]*4+b[i-1]*2);
21 a[i]%=def;
22 }
23 long long int sum=0;
24 sum=4*a[x];
25 for(int i=2;i<=x-1;i++){
26 sum+=2*(b[i-1]*2*2*a[x-i]%def+2*b[x-i]*2*a[i-1]%def);
27 sum%=def;
28 }
29 if(x==1) sum=2;
30 cout <<sum;
31 return 0;
32 }