/*解题思路和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 相结合后组成的钥匙还是不合法的）
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

__int64 Lock[26];   //凿深为 i 时的可能钥匙种类 
__int64 one[26];    //当左边第一个凿深为 1 时的可能钥匙种类 
__int64 two[26];    //当左边第一个凿深为 2 时的可能钥匙种类
__int64 a[26];      //当左边第一个凿深为 1 时,后面的 i - 1 中可能的不合法情况
__int64 b[26];      //当左边第一个凿深为 1 时,后面的 i - 1 中可能的不合法情况

int main ()
{
    one[3] = 16;
    two[3] = 18;
    Lock[3] = 104;   
    for (int i = 4; i < 26; i ++)
    {

        a[i] = 16 * (pow (2, i - 2) - 1);
        b[i] = 9 * (pow (2, i - 1) - 2);
        
        one[i] = one[i - 1] + 4 * two[i - 1] + a[i];
        two[i] = 2*one[i - 1] + 4 * two[i - 1] + b[i];
        
        Lock[i] = 2 * one[i] + 4 * two[i];
    }
    
    for (int i = 3;i < 26; i ++)
    {
        printf("N=%d: %I64d\n", i, Lock[i]);
    }
    system ("pause");
    return 0;
}