HHKB2020 D - Squares (400)
コンテスト中の考察
$ a = b = 1なら$ n^2 \times n^2 - n \times n = n^4 - n^2が答え
$ a \le bとする
マス毎に考える
bの置き方に対して、bが中央に動く度に重複するようなaの置き方が1通りずつ増えていく
上限は$ (\min(n-a-b+1,a+b-1))^2
それぞれの置き方が何通りあるかを高速に求められれば良い
結局ここが$ O(N)になり駄目
解説の解法
マス毎では無く盤面で考える
$ a + b \gt nの場合を事前に弾いておかないとWAになる