題意：略~~~~

題解：

N=2: 0 N=3: 8 N=4: 64 N=5: 360 .. .. .. .. .. .. .. N=31: ... 注：根據(jù)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為結(jié)尾的個數(shù)，因為i的位置是1和4，i-1的位置就必修是4和1來配對，但是前面的計算，可能會造成i-2的位置有1和4，這樣就不符合x不是鑰匙，而且什么當(dāng)x是鑰匙的時候，已經(jīng)算了一次，所以要除去i-1位置以1和4結(jié)尾的。 ? 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上面本來就是結(jié)尾加上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] 表示是鑰匙的個數(shù)，b[i] 表示 是鑰匙但是以1或4結(jié)尾的鑰匙數(shù) 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; }

總結(jié)

以上是生活随笔為你收集整理的hdu-1438 钥匙计数之一的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。