posts - 99, comments - 8, trackbacks - 0

/*解題思路和1297類似：都是通過遞推第 n --- 1 種情況合法與不合法，從而知道第 n 種
如下：

設lock[i]表示：有 i個槽的鑰匙的個數
設one[i]表示：有 i個槽且左邊第一個槽深度為1的鑰匙的個數
設two[i]表示：有 i個槽且左邊第一個槽深度為2的鑰匙的個數
..
..
設six[i]表示：有 i個槽且左邊第一個槽深度為6的鑰匙的個數

則顯然：lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i]

由于易知：one[i]=six[i],two[i]=three[i]=four[i]=five[i]

則可以得到：lock[i]=one[i]*2+two[i]*4

當左邊第一個鑿深是1 或 2 時與后面的 i - 1 種不合法的情況結合必須構成合法的，由此遞推開來
其中：

one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i]; //可理解為所有LOKE（i-1）前加1,
                                                              所以后面的不能出現six【i - 1】，否則1 6相鄰
      =one[i-1]+two[i-1]*4 +a[i] //而a[i]即為不成立的LOKE(i-1)，b[i]同理

two[i]=one[i-1]*2+two[i-1]*4 +b[i]

其中，a[i] 和b[i]的含義分別是：
a[i]表示“有 i個槽且左邊第一個槽深度為1，同時這種鑰匙在除掉第一個槽后不再是鑰匙”的鑰匙的個數。
例如 123,124,125,134,135,145,126,136,146,156 就屬于這種情況。

b[i]表示“有 i個槽且左邊第一個槽深度為2，同時這種鑰匙在除掉第一個槽后不再是鑰匙” 的鑰匙的個數。

分析到這里，可以知道，關鍵的是求a[i]和b[i]，我們可以得到如下表達式：
a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4
b[i]=(2^(i-1)-2)*9

其中，a[i] 的各部分的含義如下：
(2^(i-1)-2)*6：
當去掉第一位，后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)兩種數字的時候，
顯然是不合法的鑰匙（不滿足至少有3個不同的深度），加上第一位的1則顯然是一個合格的鑰匙。所以后面的數
字可以為一個組合中兩個數字的任意一個，根據乘法原理i-1位一共有2^(i-1)種組合，當然還需要去掉兩種特殊
情況，就是后面i-1位完全相同的情況。滿足這種條件的一共有上面六種組合，所以得到(2^(i-1)-2)*6。
(2^(i-2)-1)*4：
當去掉第一位，后面i-1位只有 (2,6)或者 (3,6) 或者(4,6) 或者(5，6)兩種數字的時候，顯然是不合法的鑰匙
（不滿足至少有3個不同的深度），加上第一位的1則“可能”是一個合格的鑰匙。因為要注意滿足“相連的槽其
深度之差不得為5”這個條件，所以，緊跟著1的絕對不能是6，這樣，相對于上面的分析，后面i-2位可以是每組
中的任意一個，所以有2^(i-2)，還要減去1是因為同樣要排除后面全部是和第2位一樣的數字這樣的情況。滿足
這種條件的一共有上面的四種組合，所以得到(2^(i-2)-1)*4。

b[i] 的含義如下：
(2^(i-1)-2)*9：
當去掉第一位，后面i-1位只有 (1,3)或者 (1,4) 或者(1,5) 或者(3,4) 或者(3,5) 或者(3,6) 或者(4,5) 或者(4,6)
或者(5,6) 兩種數字的時候，顯然是不合法的鑰匙（不滿足至少有3個不同的深度），加上第一位的1則顯然是一個合
格的鑰匙。所以后面的數字可以為一個組合中兩個數字的任意一個，根據乘法原理i-1位一共有2^(i-1)種組合，當然
還需要去掉兩種特殊情況，就是后面i-1位完全相同的情況。滿足這種條件的一共有上面9種組合，所以得到(2^(i-1)-2)*9。
（排除(1,6)是因為這樣的不合法情況和前面的第一個鑿 2 相結合后組成的鑰匙還是不合法的）
*/