TopCoder SRM 455 Div1 Medium ConvexHexagons

問題

正三角形の辺をn等分し、等分した点同士を線分で結び六角形のグリッドを作る。
グリッド上に六角形は何通り書くことが出来るか、mod 10^9+7で求めよ。

制約条件

n≦500000

方針

長さnの正三角形にぴったりくっつく正六角形の数を求めて、足す。


この六角形は、次の2通りの場合に分類できる。

  • 全ての辺の長さがn/2以下
  • 一つの辺の長さがn/2以上

上の六角形の個数は((n-1)/2)^3個で、
下の六角形は、そのときの個数をdp[i]個とすれば、nが偶数のときdp[i-1]+((n-1)/2)^2個で奇数のときdp[i-1]個である。
下の六角形は3通り回転させることができるので3倍する。

ソースコード

const int mod=(int)1e9+7;
ll dp[500001];
class ConvexHexagons {
  public:
  int find(int N) {
    ll ans=0;
    memset(dp,0,sizeof(dp));
    
    for(int i=3;i<=N;i++){
      ll t=(i-1)/2;
      dp[i]=(dp[i-1]+(i%2?0:t*t))%mod;
      t=t*t%mod*t%mod;
      (t+=dp[i]*3ll)%=mod;
      ans+=t*(N-i+2)%mod*(N-i+1)%mod*((mod+1)/2)%mod;
      ans%=mod;
    }
    return ans;
  }
};