大まかな方針

数え上げの式は複雑で、あまり細かい制御が出来るようなものではありません。

\(2\) 次元グリッドを左下から右上に向かって移動していくパスの数え上げのような構造をしています。

通れる/通れないを独立に制御できるような \(40\) マスであって干渉しない（＼の方向に並んでいる）ものを用意できれば、半分全列挙することで \(2^{40}\) 通りほどの値を自在に作ることができ、高確率で \(0\) を作ることができます。

具体的な解法

面積 \((N-1)(N-1)\) のバウンディングボックスはどんな \(X,Y\) でも含まれることを利用します。

1. \(M\) を \((N-1)(N-1)+e\) (\(e\) は \(3\) 程度の小さい整数) の約数であって大きすぎないものにする。
2. \(ix \bmod M \gt M-e\) となる \(x\) がちょうど \(1\) 個である \(i\) についての \((i,x)\) を列挙する。
3. 長さ \(40\) の (\(x\) についての) DS (decreasing subsequence) を取る。
   • DS の各要素の間に上記のような \(x\) が \(0\) 個であるような \(i\) が存在する、という制約付きで求める必要があります。（”通れる” にする場合に必要）
4. DS の各 \((i,x)\) を (C の解説で言うところの) \(W_1,W_2, \dots, W_{40}\) に割り当てる。
5. DS の各要素に対し、対応するマスを “通れない” にした場合の差分を求める。
   • ここが計算量のネックとなります。
6. この差分についての部分和問題を半分全列挙で解き、それに対応する \(Y\) を求める。

いくつかの \(N,e,M\) を試すことで、例えば \(N=2001, (e=3), M=4111\) （DS：((73,1971), (159,1965), (225,1955), (260,1929), (297,1924), (428,1873), (458,1867), (464,1834), (474,1830), (585,1799), (602,1796), (611,1783), (633,1760), (731,1749), (805,1721), (940,1710), (950,1692), (965,1687), (1065,1683), (1105,1663), (1124,1591), (1166,1576), (1202,1563), (1227,1501), (1263,1481), (1338,1441), (1357,1439), (1402,1428), (1428,1402), (1434,1399), (1525,1391), (1542,1365), (1585,1315), (1657,1305), (1668,1289), (1707,1274), (1821,1271), (1863,1260), (1890,1242), (1979,1236))）などが見つかります。

上記の手法がどのような \(P\) についても生成できることを示すことは難しいですが、制約範囲内の全ての \(P\) について常に生成可能であることは確認できます。