HU-1348キーカウントの一つ

http://acm.hdu.edu.cn/showproblem.php?pid=1438                                鍵の数の一つ
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：1328    Acceepted Submission(s)：552
Problem Description
一つの鍵はN個の溝があります。溝の深さは1、2、3、4です。各鍵は少なくとも3つの異なる深さを有し、少なくとも1対の連結溝の深さの差は3である。このような鍵の総数を求めます。
 
 
Input
本題には入力がありません
 
 
Output
N>=2かつN<=31に対して、要求を満たす鍵の総数を出力します。
 
 
Sample Output
N=2:0 N=3:8 N=4:64 N=5:360.................N=31:...注：Pku Jdge 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-1の位置がキーであるかが分かりません。
  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<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
__int64 pow(int x,int y)
{
    int i;
    __int64 sum=1;
    for(i=1;i<=y;i++)
        sum*=x;
     return sum;
}
int main()
{
    __int64 temp,a[40],b[40];
    int i;
      a[2]=b[2]=0;
    a[3]=8;b[3]=4;
    for(i=4;i<=31;i++)
    {
        a[i]=a[i-1]*4;
        a[i]+=pow(2,i)-4;
        temp=(pow(4,i-2)-pow(2,i-2))*2-b[i-1];
        a[i]+=temp;
        b[i]=a[i-1]*2+temp;
    }
    for(i=2;i<=31;i++)
         printf("N=%d: %I64d
",i,a[i]);
   return 0;

}