SRM455 Div1 Medium(550) ConvexHexagons

ConvexHexagons

元の正三角形から小さな正三角形を切り出し、その正三角形の頂点を切り落として六角形を作ると考える。
サイズNの正三角形に含まれるサイズtの正三角形の個数は(N-t+2)(N-t+1)/2。サイズtの正三角形から上・左下・右下の切り取る幅をそれぞれu, l, rとすると、各辺に少なくとも長さ１は辺が残ることを考えて、可能な組み合わせは、1≦u≦t-2, 1≦r≦t-u-1, 1≦l≦t-max(u,r)-1。
これをそのまま書くとO(n³)で間に合わないので場合分けしてゴリゴリ計算しO(n)に落とすのが想定解法な気がするが、最初10項くらいを出力してオンライン整数列大辞典でカンニングすると、((t-2)²+1)(2(t-2)+3)/8と書けるらしい。上位陣のコードを見てみると確かにこの数式が出てくる。

using namespace std;

class ConvexHexagons
{
public:
    int find( int N );
};

int ConvexHexagons::find( int N )
{
    long long r = 0;

    for ( long long t=3; t<=N; t++ )
    {
        //  三角形の数
        long long tn = (N-t+1)*(N-t+2)/2 % 1000000007;

        //  六角形の数
        long long n = t - 2;
        long long hn = (n*n+1)*(2*n+3)/8 % 1000000007;

        r += tn * hn;
        r %= 1000000007;
    }

    return (int)r;
}