格子刷油漆

2019-11-10 18:47:15

字體：大中小

供稿：網(wǎng)友

標(biāo)題：格子刷油漆

X國(guó)的一段古城墻的頂端可以看成 2*N個(gè)格子組成的矩形（如圖1所示），現(xiàn)需要把這些格子刷上保護(hù)漆。

你可以從任意一個(gè)格子刷起，刷完一格，可以移動(dòng)到和它相鄰的格子（對(duì)角相鄰也算數(shù)），但不能移動(dòng)到較遠(yuǎn)的格子（因?yàn)橛推嵛锤刹荒懿龋。?比如：a d b c e f 就是合格的刷漆順序。 c e f d a b 是另一種合適的方案。當(dāng)已知 N 時(shí)，求總的方案數(shù)。當(dāng)N較大時(shí)，結(jié)果會(huì)迅速增大，請(qǐng)把結(jié)果對(duì) 1000000007 (十億零七) 取模。輸入數(shù)據(jù)為一個(gè)正整數(shù)（不大于1000）輸出數(shù)據(jù)為一個(gè)正整數(shù)。例如：用戶輸入：

2 程序應(yīng)該輸出：

24 再例如：用戶輸入：

3 程序應(yīng)該輸出：

96 再例如：用戶輸入：

22 程序應(yīng)該輸出：

359635897

#include <stdio.h> long long a[1001],b[1001],sum;//int 會(huì)超，所以long long #define NUM 1000000007 int main() { int i,n; scanf("%d",&n); //dp //總體分為 1:從邊緣的出發(fā) 2:從中間出發(fā) //1. //a[i]數(shù)組表示從最邊緣的四個(gè)格子中某個(gè)出發(fā)，遍歷完長(zhǎng)度為i，個(gè)數(shù)為2i個(gè)格子的所有種類數(shù)； //b[i]數(shù)組表示從除了最邊緣的四個(gè)格子外的某個(gè)中間的格子出發(fā)，遍歷完一邊回到所對(duì)的格子； //第一種情況一直向右走,假設(shè)從a點(diǎn)出發(fā)，每一列隨機(jī)只走一格，也就是每向右只走一步，就是數(shù)組b[i]的存儲(chǔ) //第二種情況就是先走a所對(duì)的格子，然后再走下一列，當(dāng)前就有兩種情況，以此類推2 * a[i - 1] /*第三種考慮會(huì)往回走的情況，從第一列到第三列，會(huì)經(jīng)過第二列，比如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]; //四個(gè)角，所以*4 //2.下面再加上從中間出發(fā)的種數(shù) /* 從第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)