SRM429 Div1 250

問題

文字がセルに敷き詰められた長方形が与えられる。
それをコピーして右、右下、下にくっつける。(サイズ的には4倍)
ここで、この拡張した長方形の中の部分長方形を考える。
各部分長方形をすべて考える時、各セルに書かれた文字は全部で何回出現するか。

考え方

まず、拡張した長方形を作る。
その長方形の各セルが部分長方形を考えたとき、何回出現しうるかを計算する。

for(int starty=0; starty<h; starty++){
  for(int endy=starty+1; endy<=h; endy++){
    for(int startx=0; startx<w; startx++){
      for(int endx=startx+1; endx<=w; endx++){
        for(int i=starty; i<endy; i++){
          for(int j=startx; j<endx; j++){
            ...

みたいにやってしまうと、50^6とかになってしまうので、計算式を考える。
あるセル(j,i)は長方形を考えると、x軸方向では(w-j)*(j+1)の組み合わせが考えられる。y軸も同様なので、セル(j,i)は(w-j)*(j+1)*(h-i)*(i+1)回出現する。答えは、セル(j,i)にある文字の個数にこの出現回数を加えていくことで計算できる。