\(X=2\) の時を考えます。

まず、一番上の行に書く整数を決めると全てのマス目に書くべき整数が一意に定まり、一番下の行以外のマスに対する条件が全て満たされることに注目します。厳密に言うと、全てのマスは \(A_{1,1},A_{1,2},\dots,A_{1,M}\) の線形和で表すことができます。その係数は \(\mathrm{O}(NM^2)\) で求めることができます。

一番下の行のマス目に書く \(M\) 個の整数とそれぞれに対する \(M\) 個の条件からなる \(M\) 変数 \(M\) 式連立 \(1\) 次方程式を解けばよく、これは掃き出し法を用いることにより \(\mathrm{O}(M^3)\) で解くことができます。

しかし、\(X\) が一般の場合は掃き出し法を使うときに \(\bmod\) 上での割り算ができない可能性があります。ここで、最後に中国剰余定理を使うこととし、\(X\) を素冪と仮定します。 素数 \(p\) と正整数 \(e\) に対し、\(X=p^e\) と表されるとします。

ここで、掃き出し法の時に今残っている係数のうち、最も \(p\) で割り切れる回数が少ないものを左上に持ってくることを繰り返すことで必ず割り算をすることが可能です。掃き出し法の計算量は \(\mathrm{O}(M^3\log X)\) となります。

ここで、対角成分に \(p\) の倍数が含まれている場合は総和が \(1\) 以上となるような構成が存在し、そうでない場合は総和が \(0\) になる構成しか存在しないことが示せます。

よって、この問題を \(\mathrm{O}(M^2(N+M)\log^2 X)\) で解くことができました。