標題：格子刷油漆
X國的一段古城墻的頂端可以看成 2*N個格子組成的矩形（如圖1所示），現需要把這些格子刷上保護漆。
你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數），但不能移動到較遠的格子（因為油漆未干不能踩！） 比如：a d b c e f 就是合格的刷漆順序。 c e f d a b 是另一種合適的方案。 當已知 N 時，求總的方案數。當N較大時，結果會迅速增大，請把結果對 1000000007 (十億零七) 取模。 輸入數據為一個正整數（不大于1000） 輸出數據為一個正整數。 例如： 用戶輸入：
2 程序應該輸出：
24 再例如： 用戶輸入：
3 程序應該輸出：
96 再例如： 用戶輸入：
22 程序應該輸出：
359635897
#include <stdio.h> long long a[1001],b[1001],sum;//int 會超，所以long long #define NUM 1000000007 int main() { int i,n; scanf("%d",&n); //dp //總體分為 1:從邊緣的出發 2:從中間出發 //1. //a[i]數組表示從最邊緣的四個格子中某個出發，遍歷完長度為i，個數為2i個格子的所有種類數； //b[i]數組表示從除了最邊緣的四個格子外的某個中間的格子出發，遍歷完一邊回到所對的格子； //第一種情況一直向右走,假設從a點出發，每一列隨機只走一格，也就是每向右只走一步，就是數組b[i]的存儲 //第二種情況就是先走a所對的格子，然后再走下一列，當前就有兩種情況，以此類推2 * a[i - 1] /*第三種考慮會往回走的情況，從第一列到第三列，會經過第二列，比如N = 3的情況， 要走到第三列，只有abcd ,abdc, adbc, acbd 四種情況。*/ //綜上：a[i] = (2 * a[i-1] + b[i] + 4 * a[i-2]) 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; sum = 4 * a[n]; //四個角，所以*4 //2.下面再 加上從中間出發的種數 /* 從第i列開始,則前面有i-1列，后面有n-i列 總的走法是：先遍歷左邊后右邊 + 先遍歷右邊后左邊 == 2*(2*b[i - 1]*2*a[n - i]) + 2*(2*b[n - i]*2*a[i - 1]); */ for (i = 2; i < n; i++) sum += ((8*b[n-i]*a[i-1]%NUM)%NUM + (8*a[n-i]*b[i-1])%NUM) % NUM; if(n == 1)新聞熱點
疑難解答
