TopCoder SRM 723 Div2 Hard SimpleMazeEasy

実装は簡単なのだが。
https://community.topcoder.com/stat?c=problem_statement&pm=14738

問題

以下の形状をN倍に拡大した図形を考える。

 *
***
 *

「*」同士の距離の総和を答えよ。

解法

この図形は点対象で、かつ（凸ではないものの）距離がマンハッタン距離と一致するような移動手順が常に存在する。
よって上下方向の移動距離の総和を考え、それを倍にすれば上下左右の移動距離の総和を求められる。
また、横方向に(1/N)に圧縮して考えるとラクになる。その分は最後の解に(2つの点の間の総和を求めるので)N^2を掛ければつじつまがあう。

あとは以下のような図形になるので、自然数の１乗和と２乗和を駆使するとO(1)で計算できる。
以下のコードでは、１行目で中心部の縦移動方向の総和、２行目で左右の出っ張り部分の総和、３行目で出っ張り部分と中央部の間の総和を求めている。

 *
 *
 *
***
***
***
 *
 *
 *

class SimpleMazeEasy {
	public:
	int findSum(long long N) {
		ll mo=1000000007;
		ll ret=0;
		ll r6=((mo+1)/2)*((mo+1)/3)%mo;
		
		N%=mo;
		ret=(3*N)%mo*(3*N+1)%mo*(3*N+mo-1)%mo*r6%mo;
		ret+=4*(N)*(N+1)%mo*(N+mo-1)%mo*r6%mo;
		ret+=4*(N)*(7*N*N%mo+mo-1)%mo*r6%mo;
		
		
		
		return ret%mo*2*(N%mo)%mo*(N%mo)%mo;
	}
}

まとめ

プログラミングより数学成分が多い。