SRM429 Div2 500

問題

文字が敷き詰められた長方形のtableが与えられる．そのtableのコピーを4つ取り，2x2の形に拡張したものを作る．その拡張した長方形のすべての部分長方形を列挙する．
例えば，「OK」というtableの場合，拡張した長方形は

OKOK
OKOK

となる．各アルファベット文字がすべての部分長方形で何回出てきたかを返す．(上の例の場合，OとKがそれぞれ40回)

考え方

まず拡張したtableを作る．
そのtableで(i,j)の文字が何回部分長方形に含まれるかを考える．
左上の文字を(0,0)とすると，0からiと0からjの中の座標のどれか，i+1からtableの高さとj+1からtableの幅の中の座標のどれかを長方形の角の2点としたとき(i,j)の文字が含まれることがわかる．
よってその地点が何回部分長方形に含まれるかは,「{(i+1)*(j+1)} * {(tableの高さ-i)*(tableの幅-j)}」で求められる．
これを配列に記憶しておいて，最後に，各アルファベットについて，回数を合計すればいい．