本文主要是介绍hdu-1438 钥匙计数之一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：略~~~~
题解：
N=2: 0 N=3: 8 N=4: 64 N=5: 360 .. .. .. .. .. .. .. N=31: ... 注：根据Pku Judge Online 1351 Number of Locks或 Xi'an 2002 改编,在那里N<=16
分析：若x是钥匙，则x加1，2，3，4.都是钥匙则a[i]=a[i-1]*4;
若x不是钥匙，加上2,3。就是钥匙了，这x是由1和4组成。但是要减去x是全1或者全4。a[i]+=(2^i-1-2)*2;
若x不是钥匙，加上1,4就是钥匙但是要减去x是由1和4组成。还要除去b[i-1],表示以1和4为结尾的个数，因为i的位置是1和4，i-1的位置就必修是4和1来配对，但是前面的计算，可能会造成i-2的位置有1和4，这样就不符合x不是钥匙，而且什么当x是钥匙的时候，已经算了一次，所以要除去i-1位置以1和4结尾的。
temp=(4^i-2-2^i-2)*2-b[i-1].
而此时，b[i]=a[i-1]*2+temp,a[i-1]*2是i-1是钥匙，然后加上1和4，temp上面本来就是结尾加上1和4.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef __int64 LL;LL a[32],b[32];
// a[i] 表示是钥匙的个数，b[i] 表示 是钥匙但是以1或4结尾的钥匙数
LL pow(int a,int b){LL sum = a;for(int i = 2;i <= b;i++){sum *= a;}return sum;
}
int main(){a[2] = 0;b[2] = 0;a[3] = 8;b[3] = 4;for(int i = 4;i < 32;i++){a[i] = a[i-1] * 4; a[i] += (pow(2,i-1) - 2) * 2;LL tmp =(pow(4,i-2) - pow(2,i-2)) * 2 - b[i-1];a[i] += tmp;b[i] = a[i-1] * 2 + tmp;}for(int i = 2;i < 32;i++){printf("N=%d: %I64d\n",i,a[i]);}return 0;
}
这篇关于hdu-1438 钥匙计数之一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
