\(N \times N\) の配列 \(A, B\) を

\(A[i][j] ={}\)( \(S[i][j] = {}\)O ならば \(1\) 、そうでなければ \(0\) )
\(B[i][j] ={}\)( \(i + j/2 < M\) ならば \(1\) 、そうでなければ \(0\) )

と定義します。(添字は \(0\) から始めまるものとします。)

マス \((X, Y)\) での答え \(C[X][Y]\) は以下のように求められます。

\[ C[X][Y] = \sum_{\substack{x_a + x_b = X \\ y_a + y_b = Y}} A[x_a][y_a] \times B[x_b][y_b] \]

これは \(2\) 次元の畳み込みの形をしているので、\(2\) 次元 FFT で \(O(N^2 \log N)\) で求めることができます。

具体的には、\(A, B, C\) を \(2^{12} \times 2^{12}\) の大きさに拡張し、縦向きと横向きそれぞれで FFT をすれば良いです。

実装例 (C++)

#include <array>
#include <iostream>
#include <atcoder/convolution>
using namespace std;
using Modint = atcoder::modint998244353;


const int L = 1 << 12;
using Array = array<array<Modint, L>, L>;
Array A, B;
template<bool inv>
void FFT_2D(Array& A){
    vector<Modint> v(L);
    auto conv = [&]{
        if(inv) atcoder::internal::butterfly_inv(v);
        else atcoder::internal::butterfly(v);
    };
    for(int i = 0; i < L; i++){
        for(int j = 0; j < L; j++){
            v[j] = A[i][j];
        }
        conv();
        for(int j = 0; j < L; j++){
            A[i][j] = v[j];
        }
    }
    for(int j = 0; j < L; j++){
        for(int i = 0; i < L; i++){
            v[i] = A[i][j];
        }
        conv();
        for(int i = 0; i < L; i++){
            A[i][j] = v[i];
        }
    }
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){
        char c;
        cin >> c;
        A[i][j] = c == 'O';
    }
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){
        B[i][j] = i * 2 + j < M * 2;
    }
    FFT_2D<0>(A);
    FFT_2D<0>(B);
    const Modint inv = Modint(L * L).inv();
    for(int i = 0; i < L; i++) for(int j = 0; j < L; j++) A[i][j] *= B[i][j] * inv;
    FFT_2D<1>(A);
    int Q;
    cin >> Q;
    while(Q--){
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << A[x][y].val() << '\n';
    }
}