(より詳しい解説は後日ブログで公開します)

解法 1

拡大前のうさぎの画像を長方形に区切って，各長方形で畳み込みを行うことで答えが求まります．

長方形の 縦+横 の合計を \(L\) として \(O(KL \log(KL))\) 時間と抑えられるので，\(L\) を小さくしたいです．

例えば，画像全体から長方形を縦または横に割っていくという方法に限定すると，事前に DP で最適化でき，\(L = 2282\) が達成できます．\(L\) の値がこれと比べて極端に悪くなく，畳み込みの速度が atcoder::convolution と比べて極端に悪くなければ AC できます．

解法 2

\(K \times K\) の正方形ごと (\(13941\) 個) に畳み込む TLE 解法を，FFT の線型性を用いて高速化し，\(13941\) にかかるオーダーを \(O(K)\) にできます．

\(A, B\) の \(K\) 項ごとを FFT し，各正方形で各点積を計算し，\(i+j\) ごとに和をとってから inverse FFT すればよいです．