BOJ 2369 - 행렬의 부분합

BOJ 2369 - 행렬의 부분합

일차원에선 흔한 문제지만 이차원에서 생각해보자.

$P[y][x]$ 를 $0 \sim y$ 와 $0 \sim x$에 해당하는 구간합을 $K$로 나눈 나머지라고 하자.

그럼 일단 같은 $y$ 중에서 일차원에서 했던 것과 동일하게 현재 $P$ 값이 $k$ 라면 $K$로 나눈 것이 $k$ 인 것 중 동일한 $x$를 가진 것의 개수를 정답에 더해주면 된다.

$N$이 작음을 이용하여 계속 배열의 가장 왼쪽 칸을 지우면서 이걸 반복한다고 해보자.

그러면 총 $O(N^3)$에 문제 해결이 가능하다.

int cnt[1000000];
void solve() {
   int Y, X, K;
   cin >> Y >> X >> K;
   vvi b(Y, vi(X));
   fv2(b);
   int ans = 0;

   int FX = X;

   // cx 미만의 것은 drop 된다
   for (int cx = 0; cx < FX; cx++, X--) {
      vvi psum(Y + 1, vi(X + 1));
      for (int y = 0; y < Y; y++)
         for (int x = 0; x < X; x++)
            psum[y + 1][x + 1] = md(K, b[y][x + cx] + psum[y + 1][x] + psum[y][x + 1] - psum[y][x]);

      int tmp = 0;
      for (int x = 0; x < X; x++) {
         vi list;
         cnt[0] = 1;
         list.pb(0);
         for (int y = 0; y < Y; y++) {
            int v = psum[y + 1][x + 1];

            tmp += cnt[v];

            cnt[v]++;
            list.pb(v);
         }

         for (int v: list) cnt[v] = 0;
      }
      debug(cx, tmp);
      ans += tmp;
   }

   cout << ans;
}