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; } };