\(s\) の長さを \(L\) とします。また、\(i = 0, \ldots, L\) について、\(A_i\) を \(s\) の先頭 \(i\) 文字内の \(1\) の個数 (\(\mathrm{mod}~n\))、\(B_i\) を同 \(0\) の個数 (\(\mathrm{mod}~m\)) とします。すると、条件は以下と同等です。

• \(A_L = B_L = 0\)
• ペア \((A_i, B_i)\) は重複しない。ただし、\((A_0, B_0) = (A_L, B_L) = (0, 0)\) を除く。

解釈を変えると次のようになります。\(n \times m\) 頂点の格子グラフを作り、頂点 \((x, y)\) (\(0 \leq x < N\), \(0 \leq y < M\)) から \(((x + 1) \bmod n, y)\) と \((x, (y + 1) \bmod m)\) に辺を張ります。求めたいものは、このグラフの頂点 \((0, 0)\) を始点とする単純サイクルの個数です。まずは、始点が \((0, 0)\) かを無視して、全ての単純サイクルを数えましょう。

サイクルが格子を「一周」する行の集合 \(R\) と列の集合 \(C\) を固定したとします。これに該当する任意のサイクルは、\(R\) や \(C\) の最上行や最左列の頂点と最下行や最右列の頂点とを結ぶ、頂点の交わりのない経路の集まりに対応します。LGV lemma より、そのような経路の集まりの個数は \((-1)^{|R| \times |C|} \times(\) 各要素が各始点から各終点への経路数であるような \((|R| + |C|) \times (|R| + |C|)\) 行列の行列式 \()\) です。ただし、経路を結合すると単一のサイクルとなるためには、\(|R|\) と \(|C|\) が互いに素であることが必要十分であることに注意します。

経路数を全ての \(|R|, |C|\) について求めるには、グラフを次のように変形します（\(x, y\) は可変の重み、無印の辺の重みは \(1\)、\(+\) は送信頂点、\(-\) は受信頂点）。

このグラフに LGV lemma を適用することで、経路の集まり全てに対する重み積の総和が多項式 \(\sum_{r, c} A_{r, c} x^r y^c\) として得られます。すると、答えは \(\sum_{r, c\text{ coprime}} (-1)^{rc} A_{r, c}\) です。

一行目で「一周」する経路のみを計算に含めるには、格子の一行目の送信頂点から受信頂点への辺を削除します。サイクルが \((0, 0)\) を通るのは、一行目か一列目で一周する場合です。

行列式を数式的に求めるのは困難ですが、\(O(NM)\) 個の点 \((x, y)\) で計算して補間することができます。合計計算量は（経路数の行列がブロック三角行列であることを用いれば）\(O(N^2M^2(N + M))\) です。