以下のグリッドの和を求めることを考えてみます。

  1  0  3  0
  0  6  0  8
  9  0 11  0
  0 14  0 16
 17  0 19  0

奇数行のゼロでないグリッドを抜き出すと、

  1  3 
  9  11
 17 19

となります。以下ではこのグリッドを元グリッドと呼び、この合計値を求め、偶数行については別途考えることとします。 元グリッド全体の平均値が求まれば、元グリッドのマス数に書かれている数字の和は (平均値) x (元グリッドのマス数)で求めることができます。

さて、元グリッド全体の平均値をO(1)で求めるためにはどのように計算すればよいでしょうか？ まず各行の平均値を求めてみましょう。初項a、末項l、項数nの等差数列の和はn(a + l)/2であることから、平均値は(a + l) / 2であることがわかります。

3 5 7 9 

の場合だと、(3 + 9) / 2 = 6が平均値です。

次に各行の平均値の平均値ですが、

  2 
 10 
 18

で見ていくと、やはりこれも等差数列になっているため、(a + l) / 2で求めることができます。この例だと(2 + 18) / 2 = 10が平均値であり、これが元グリッド全体の平均値です。

結局、元グリッドの左上、右上、左下、右下の４つのマスの数字の平均値がグリッド全体の平均値となります。

さらに言うと(元グリッドの左上の数字) +(元グリッドの 右下の数字) = (元グリッドの右上の数字) +(元グリッドの 左下の数字) が成立するため、元グリッド全体の平均値は(元グリッドの左上の数字)+(元グリッドの右下の数字) / 2で求めることができます。

上記のグリッドの例で言えば(1 + 19) / 2 = 10が平均値です。この性質はどのような元グリッドでも成立します。

左上と右下のマスがどこにあたるかはmod2に気をつけながら求めれば、元グリッドのマス数を求めることができます。さらに定義どおり左上と右下の値を計算することで、元グリッド全体の平均値を求めることができます。

同様の議論は偶数行についても成立するので、それらの合計が答えです。

実装例(Rust)

https://atcoder.jp/contests/abc269/submissions/34942209