HDU2045

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2045

问题分析：

假设三种颜色编号为1 2  3，第一个格子涂1，那么此后第二个格子就只能涂2或3，然后再第三个格子中2对应的可以涂1，3；3对应得可以涂1，2。一直到最后一个格子。如果用一个树形表示就是

因为最后一个格子和第一个格子的颜色不能相同，所以总方案数就是最后得分支数减去分支中1的个数。

但是这些1和非1的个数是有规律可循的。非1的个数来自前一个格子非1的个数加上1的个数*2。1的个数是2^n - 非1的个数

所以非1的个数用数学公式表达就是:

因为是三种颜色所以最后总方案数是 Sn = an*3

code:

#include <cstdio>

using namespace std;
typedef long long LL;

LL a[50+7];
LL s[50+7];

void init()
{
    for(int i=0; i<57; i++)
        s[i] = a[i] = 0;
}
LL pow2(int n)
{
    LL res = 1;
    for(int i=0; i<n; i++)
        res = res * 2;
    return res;
}

int main()
{
    init();
    a[0] = 0;
    s[0] = 3;

    for(int i=1; i<51; i++)
    {
        a[i] = pow2(i) - a[i-1];
        // printf("%lld ", a[i]);
    }
    // printf("\n");
    for(int i=1; i<51; i++)
    {
        s[i] = 3*pow2(i) - 3*a[i-1];
        // printf("%lld ", s[i]);
    }
    // printf("\n");

    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf("%lld\n", s[n-1]);
    }



    return 0;
}