HDU 1396: Triangle Counting Find Patterns

题意：边长为n的等边三角形共有多少个；

原题http://acm.hdu.edu.cn/showproblem.php?pid=1396

解析：边长为n的三角形数量函数f(n)等于边长为n-1时的三角形数量f(n-1)，加上第n层新增的三角形数2n-1，再加上边长大于1的正向三角形数n(n-1)/2，以及倒置的三角形数目；

即f(n)=f(n-1)+2n-1+n(n-1)/2+倒置的三角形数目；

倒置的三角形数目从第四层开始出现，第四层有1个，第五层有2个，第六层有4个，依此类推；

归纳可得两种情形：当(n-3)为奇数时，其值为1+3+5+……+(n-3)；

当(n-3)为偶数时，则为2+4+6+……+(n-3)；

错误分析：未计入倒置方向的三角形数量；

总数非常庞大，需使用__int64类型进行存储；

 #include<cstdio>

    
 using namespace std;
    
 typedef __int64 ll;
    
 ll a[501];
    
 void init()
    
 {
    
     a[1]=1;
    
     for(int i=2;i<501;i++)
    
     {
    
     a[i]=a[i-1]+i*(i-1)/2+2*i-1;