We count monotone lattice paths from \((0,0)\) to \((n,n)\), where each step is either one unit right or one unit up. A path is admissible if it never visits any forbidden grid point.
In the implementations, the forbidden points are exactly the interior square-coordinate points
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$$
The final answer is the number of admissible paths modulo \(10^9+7\).
If \((x_1,y_1)\) and \((x_2,y_2)\) satisfy \(x_1 \le x_2\) and \(y_1 \le y_2\), then any monotone path from the first point to the second point must use exactly \(x_2-x_1\) right moves and \(y_2-y_1\) up moves. Hence the number of such paths is
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}.$$
In particular, without any forbidden points, the total number of paths from \((0,0)\) to \((n,n)\) is
$$\binom{2n}{n}.$$
Only points with both coordinates at most \(n\) can matter, so it is enough to enumerate \(a,b \le \lfloor \sqrt{n}\rfloor\). The condition \(a^2+b^2=c^2\) means that \((a,b,c)\) forms a Pythagorean triple, and each such pair produces a forbidden point \((a^2,b^2)\).
After sorting the forbidden points lexicographically, write them as
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m).$$
This ordering is compatible with monotone movement: if a path can go from \(P_j\) to \(P_i\), then necessarily \(x_j \le x_i\) and \(y_j \le y_i\), which implies \(j \lt i\) after lexicographic sorting.
For each forbidden point \(P_i\), let \(B_i\) be the number of monotone paths from \((0,0)\) to \(P_i\) whose first forbidden point is exactly \(P_i\). Start from the unrestricted count
$$\binom{x_i+y_i}{x_i}.$$
If a path reaches an earlier forbidden point \(P_j\) first and later continues to \(P_i\), then the number of such paths is
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j},$$
provided \(x_j \le x_i\) and \(y_j \le y_i\). Therefore
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}.$$
This dynamic program is a topological inclusion-exclusion on the partial order induced by coordinate-wise comparison.
Every inadmissible path from \((0,0)\) to \((n,n)\) has a unique first forbidden point, so after all \(B_i\) are known we subtract the bad paths by that first hit:
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}.$$
This is exactly the recurrence used in the implementations.
For \(n=5\), there are no forbidden points because the only possible square coordinates are \(1\) and \(4\), and none of the sums \(1+1\), \(1+4\), \(4+1\), \(4+4\) is a square. Hence
$$A(5)=\binom{10}{5}=252.$$
For \(n=16\), the forbidden points are \((9,16)\) and \((16,9)\), coming from \(3^2+4^2=5^2\) and \(4^2+3^2=5^2\). The unrestricted count is
$$\binom{32}{16}=601080390.$$
Each forbidden point receives
$$\binom{9+16}{9}=\binom{25}{9}=2042975$$
paths from the origin. Neither forbidden point dominates the other, so no path can pass through both. Therefore
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
which matches the checkpoint value used by the implementations.
All binomial coefficients are evaluated modulo the prime
$$M=10^9+7.$$
The implementations precompute factorials and inverse factorials up to \(2n\), so every combination query becomes
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}.$$
The inverse factorials are derived using Fermat's little theorem:
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$$
After this preprocessing, each path-count query is \(O(1)\).
The C++, Python, and Java implementations follow the same structure. They first build a fast square-membership structure up to \(2n\), enumerate every forbidden point \((a^2,b^2)\) inside the \(n \times n\) grid, sort the resulting list, and remove duplicates. Next they precompute factorials and inverse factorials so that any binomial coefficient needed by the path formulas can be answered in constant time modulo \(10^9+7\).
Once those tables are ready, the implementation scans the forbidden points in sorted order and computes the number of paths whose first forbidden point is each obstacle. The final admissible count is obtained by subtracting all bad-path contributions from the unrestricted total \(\binom{2n}{n}\).
Let \(m\) be the number of forbidden points. Enumerating candidate square pairs takes \(O(n)\) time because both \(a\) and \(b\) range up to \(\lfloor \sqrt{n}\rfloor\). Precomputing factorials and inverse factorials up to \(2n\) also takes \(O(n)\) time and \(O(n)\) memory. The dynamic program compares each forbidden point with all earlier ones, so it costs \(O(m^2)\) time and \(O(m)\) additional memory. Overall, the algorithm runs in \(O(n+m^2)\) time and uses \(O(n+m)\) memory.
Gesucht ist die Anzahl monotoner Gitterpfade von \((0,0)\) nach \((n,n)\), wobei jeder Schritt entweder nach rechts oder nach oben geht. Ein Pfad ist genau dann zulässig, wenn er keinen verbotenen Gitterpunkt betritt.
In den Implementierungen sind die verbotenen Punkte genau die inneren Punkte mit quadratischen Koordinaten
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$$
Das Ergebnis wird modulo \(10^9+7\) ausgegeben.
Seien \((x_1,y_1)\) und \((x_2,y_2)\) mit \(x_1 \le x_2\) und \(y_1 \le y_2\) gegeben. Jeder monotone Pfad zwischen diesen Punkten enthält genau \(x_2-x_1\) Rechts-Schritte und \(y_2-y_1\) Hoch-Schritte. Daher gibt es
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}$$
solche Pfade. Ohne Verbote folgt insbesondere
$$\binom{2n}{n}$$
als Gesamtzahl aller Pfade von \((0,0)\) nach \((n,n)\).
Relevant sind nur Punkte mit Koordinaten höchstens \(n\), also genügt es, \(a,b \le \lfloor \sqrt{n}\rfloor\) zu betrachten. Die Bedingung \(a^2+b^2=c^2\) bedeutet, dass \((a,b,c)\) ein pythagoreisches Tripel bildet. Jedes solche Paar erzeugt einen verbotenen Punkt \((a^2,b^2)\).
Nach dem Sortieren schreiben wir die verbotenen Punkte als
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m).$$
Diese Reihenfolge passt zur monotonen Bewegung: Wenn ein Pfad von \(P_j\) nach \(P_i\) gelangen kann, dann muss \(x_j \le x_i\) und \(y_j \le y_i\) gelten, also erscheint \(P_j\) in der lexikographischen Ordnung vor \(P_i\).
Für jeden verbotenen Punkt \(P_i\) sei \(B_i\) die Anzahl der monotonen Pfade von \((0,0)\) nach \(P_i\), deren erster verbotener Punkt genau \(P_i\) ist. Zunächst gibt es insgesamt
$$\binom{x_i+y_i}{x_i}$$
Pfade zum Punkt \(P_i\). Wenn ein Pfad aber zuerst einen früheren verbotenen Punkt \(P_j\) trifft und danach zu \(P_i\) weiterläuft, dann gibt es davon
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j}$$
unter der Voraussetzung \(x_j \le x_i\) und \(y_j \le y_i\). Also gilt die Rekurrenz
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}.$$
Das ist ein dynamisches Programm in topologischer Ordnung der durch Koordinatenvergleich definierten Halbordnung.
Jeder unzulässige Pfad nach \((n,n)\) besitzt genau einen ersten verbotenen Punkt. Deshalb ist die gesuchte Anzahl
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}.$$
Für \(n=5\) gibt es keine verbotenen Punkte, denn die einzigen quadratischen Koordinaten \(1\) und \(4\) liefern nur die Summen \(1+1\), \(1+4\), \(4+1\), \(4+4\), und keine davon ist ein Quadrat. Daher
$$A(5)=\binom{10}{5}=252.$$
Für \(n=16\) sind die verbotenen Punkte \((9,16)\) und \((16,9)\), entsprechend \(3^2+4^2=5^2\) und \(4^2+3^2=5^2\). Ohne Verbote gibt es
$$\binom{32}{16}=601080390$$
Pfade. Zu jedem der beiden verbotenen Punkte führen
$$\binom{9+16}{9}=\binom{25}{9}=2042975$$
Pfade vom Ursprung. Keiner dieser Punkte liegt koordinatenweise vor dem anderen, also kann kein monotoner Pfad beide besuchen. Somit
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
genau der Kontrollwert der Implementierungen.
Alle Kombinationen werden modulo der Primzahl
$$M=10^9+7$$
berechnet. Dazu werden Fakultäten und inverse Fakultäten bis \(2n\) vorab bestimmt, sodass
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}$$
gilt. Die Inversen folgen aus dem kleinen Satz von Fermat:
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$$
Nach dieser Vorverarbeitung ist jede einzelne Kombinationsabfrage \(O(1)\).
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst wird eine schnelle Struktur aufgebaut, die für alle Werte bis \(2n\) testet, ob sie Quadrate sind. Damit werden alle verbotenen Punkte \((a^2,b^2)\) innerhalb des \(n \times n\)-Gitters erzeugt, sortiert und gegebenenfalls dedupliziert. Danach werden Fakultäts- und Inversfakultätstabellen erzeugt, damit jeder benötigte Binomialkoeffizient in konstanter Zeit modulo \(10^9+7\) berechnet werden kann.
Anschließend verarbeitet die Implementierung die verbotenen Punkte in sortierter Reihenfolge, berechnet für jeden Punkt die Anzahl der Pfade mit genau diesem ersten verbotenen Treffer und subtrahiert schließlich alle unzulässigen Beiträge von der Gesamtzahl \(\binom{2n}{n}\).
Sei \(m\) die Anzahl der verbotenen Punkte. Das Durchlaufen aller Kandidatenpaare \((a,b)\) benötigt \(O(n)\) Zeit, weil sowohl \(a\) als auch \(b\) bis \(\lfloor \sqrt{n}\rfloor\) laufen. Die Vorberechnung von Fakultäten und inversen Fakultäten bis \(2n\) kostet ebenfalls \(O(n)\) Zeit und \(O(n)\) Speicher. Das dynamische Programm vergleicht jeden verbotenen Punkt mit allen früheren Punkten und benötigt daher \(O(m^2)\) Zeit sowie \(O(m)\) zusätzlichen Speicher. Insgesamt ergibt sich \(O(n+m^2)\) Zeit und \(O(n+m)\) Speicher.
\((0,0)\) noktasından \((n,n)\) noktasına yalnız sağa veya yukarı adımlarla giden monoton kafes yollarının sayısı istenir. Bir yol, yasaklı bir noktadan hiç geçmiyorsa admissible kabul edilir.
Uygulamalarda yasaklı noktalar tam olarak şu iç noktalardır:
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$$
Sonuç \(10^9+7\) modunda hesaplanır.
\((x_1,y_1)\) ve \((x_2,y_2)\) için \(x_1 \le x_2\) ve \(y_1 \le y_2\) olsun. Bir monoton yol tam olarak \(x_2-x_1\) adet sağ adımı ve \(y_2-y_1\) adet yukarı adımı içerir. Bu yüzden yol sayısı
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}$$
olur. Özellikle hiçbir yasak yoksa \((0,0)\) ile \((n,n)\) arasındaki toplam yol sayısı
$$\binom{2n}{n}$$
dir.
Yalnız koordinatları \(n\)'i geçmeyen noktalar etkili olabilir; bu nedenle \(a,b \le \lfloor \sqrt{n}\rfloor\) taraması yeterlidir. \(a^2+b^2=c^2\) koşulu, \((a,b,c)\) üçlüsünün Pisagor üçlüsü olması demektir. Böyle her çift, \((a^2,b^2)\) biçiminde bir yasaklı nokta üretir.
Sıralamadan sonra bu noktaları
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m)$$
şeklinde yazalım. Bu leksikografik sıra monoton yürüyüşle uyumludur: Bir yol \(P_j\)'den \(P_i\)'ye gidebiliyorsa mutlaka \(x_j \le x_i\) ve \(y_j \le y_i\) olmalıdır; dolayısıyla \(P_j\), sıralamada \(P_i\)'den önce gelir.
Her yasaklı nokta \(P_i\) için \(B_i\), \((0,0)\)'dan \(P_i\)'ye giden ve karşılaştığı ilk yasaklı nokta tam olarak \(P_i\) olan yol sayısı olsun. Önce sınırsız sayıyı alırız:
$$\binom{x_i+y_i}{x_i}.$$
Eğer bir yol önce daha erken bir yasaklı nokta \(P_j\)'ye uğrayıp sonra \(P_i\)'ye ulaşıyorsa, bu tür yolların sayısı
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j}$$
olur; burada \(x_j \le x_i\) ve \(y_j \le y_i\) gereklidir. Böylece rekürans
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}$$
şeklini alır. Bu, koordinatlara göre tanımlanan kısmi sıralama üzerinde çalışan bir dinamik programdır.
\((n,n)\)'ye giden her geçersiz yolun tek bir ilk yasaklı noktası vardır. Bu nedenle nihai cevap
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}$$
olur.
\(n=5\) için yasaklı nokta yoktur. Çünkü olası kare koordinatlar yalnızca \(1\) ve \(4\) tür; \(1+1\), \(1+4\), \(4+1\), \(4+4\) toplamlarının hiçbiri tam kare değildir. Dolayısıyla
$$A(5)=\binom{10}{5}=252.$$
\(n=16\) için yasaklı noktalar \((9,16)\) ve \((16,9)\) olur; bunlar \(3^2+4^2=5^2\) ve ters sıradaki aynı kimlikten gelir. Yasaksız toplam
$$\binom{32}{16}=601080390$$
dır. Her yasaklı noktaya başlangıçtan
$$\binom{9+16}{9}=\binom{25}{9}=2042975$$
yol gider. Bu iki nokta birbirini koordinat bazında kapsamamadığı için aynı yol üzerinde ikisi birden bulunamaz. O halde
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
ki bu da uygulamalardaki kontrol değeriyle aynıdır.
Tüm kombinasyonlar asal sayı
$$M=10^9+7$$
modunda hesaplanır. Bunun için \(2n\)'e kadar faktöriyeller ve ters faktöriyeller önceden hazırlanır:
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}.$$
Tersler Fermat'nın küçük teoremi ile bulunur:
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$$
Böylece her binom sorgusu sabit zamanda cevaplanır.
C++, Python ve Java implementasyonları aynı hattı izler. Önce \(2n\)'e kadar hangi sayıların kare olduğunu hızlıca sorgulayabilen bir yapı kurulur. Ardından \(n \times n\) kare içindeki tüm \((a^2,b^2)\) adayları taranır, Pisagor koşulunu sağlayanlar yasaklı nokta listesine eklenir, liste sıralanır ve tekilleştirilir. Sonra faktöriyel ve ters faktöriyel tabloları hazırlanarak bütün binom katsayıları \(10^9+7\) modunda sabit zamanda hesaplanabilir hale getirilir.
Bu hazırlıklardan sonra uygulama yasaklı noktaları sıralı biçimde işler, her nokta için ilk yasaklı temas sayısını hesaplar ve en sonunda tüm geçersiz katkıları \(\binom{2n}{n}\) toplamından çıkarır.
\(m\) yasaklı nokta sayısı olsun. Aday \((a,b)\) çiftlerini taramak \(O(n)\) zaman alır; çünkü hem \(a\) hem \(b\), \(\lfloor \sqrt{n}\rfloor\) sınırına kadar gider. \(2n\)'e kadar faktöriyel ve ters faktöriyel ön hesapları da \(O(n)\) zaman ve \(O(n)\) bellek ister. Dinamik program her yasaklı noktayı önceki bütün yasaklı noktalarla karşılaştırdığı için \(O(m^2)\) zaman ve \(O(m)\) ek bellek kullanır. Toplam karmaşıklık \(O(n+m^2)\) zaman ve \(O(n+m)\) bellek olur.
Debemos contar los caminos monótonos desde \((0,0)\) hasta \((n,n)\), donde cada paso es una unidad a la derecha o una unidad hacia arriba. Un camino es admisible si nunca pasa por un punto prohibido.
En las implementaciones, los puntos prohibidos son exactamente los puntos interiores con coordenadas cuadradas
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$$
La respuesta final se calcula módulo \(10^9+7\).
Si \((x_1,y_1)\) y \((x_2,y_2)\) cumplen \(x_1 \le x_2\) y \(y_1 \le y_2\), cualquier camino monótono entre ellos contiene exactamente \(x_2-x_1\) movimientos a la derecha y \(y_2-y_1\) movimientos hacia arriba. Por tanto, el número de caminos es
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}.$$
En particular, sin obstáculos, el número total de caminos desde el origen hasta \((n,n)\) es
$$\binom{2n}{n}.$$
Solo importan los puntos con coordenadas a lo sumo \(n\), así que basta enumerar \(a,b \le \lfloor \sqrt{n}\rfloor\). La condición \(a^2+b^2=c^2\) significa que \((a,b,c)\) forma una terna pitagórica, y cada una de esas parejas produce un punto prohibido \((a^2,b^2)\).
Después de ordenar los puntos prohibidos, escribimos
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m).$$
Este orden es compatible con el movimiento monótono: si un camino puede ir de \(P_j\) a \(P_i\), necesariamente se cumple \(x_j \le x_i\) y \(y_j \le y_i\), así que \(P_j\) aparece antes que \(P_i\) en el orden lexicográfico.
Para cada punto prohibido \(P_i\), sea \(B_i\) el número de caminos desde \((0,0)\) hasta \(P_i\) cuyo primer punto prohibido es exactamente \(P_i\). El número total de caminos hacia \(P_i\) sin restricciones es
$$\binom{x_i+y_i}{x_i}.$$
Si un camino toca primero un punto prohibido anterior \(P_j\) y después continúa hasta \(P_i\), entonces hay
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j}$$
caminos de ese tipo, siempre que \(x_j \le x_i\) y \(y_j \le y_i\). Por ello
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}.$$
Esto es una DP de inclusión-exclusión sobre el orden parcial dado por la comparación coordenada a coordenada.
Cada camino no admisible hasta \((n,n)\) tiene un único primer punto prohibido. Entonces
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}.$$
Para \(n=5\) no hay puntos prohibidos, porque las únicas coordenadas cuadradas posibles son \(1\) y \(4\), y ninguna de las sumas \(1+1\), \(1+4\), \(4+1\), \(4+4\) es un cuadrado. Por tanto
$$A(5)=\binom{10}{5}=252.$$
Para \(n=16\), los puntos prohibidos son \((9,16)\) y \((16,9)\), provenientes de \(3^2+4^2=5^2\) y de la misma identidad con los catetos intercambiados. El total sin restricciones es
$$\binom{32}{16}=601080390.$$
Cada uno de esos puntos recibe
$$\binom{9+16}{9}=\binom{25}{9}=2042975$$
caminos desde el origen. Ninguno domina al otro, así que un camino monótono no puede pasar por ambos. En consecuencia,
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
que coincide con el valor de verificación usado por las implementaciones.
Todos los coeficientes binomiales se calculan módulo el primo
$$M=10^9+7.$$
Las implementaciones precalculan factoriales e inversos factoriales hasta \(2n\), de modo que
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}.$$
Los inversos se obtienen con el pequeño teorema de Fermat:
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$$
Después de esta preparación, cada consulta de combinación cuesta \(O(1)\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen una estructura rápida para comprobar si un número hasta \(2n\) es cuadrado. Luego enumeran todos los puntos \((a^2,b^2)\) dentro del cuadrado \(n \times n\), conservan solo los que satisfacen la condición pitagórica, los ordenan y eliminan duplicados. Después precalculan factoriales e inversos factoriales para responder todas las combinaciones necesarias en tiempo constante módulo \(10^9+7\).
Con esas tablas listas, la implementación recorre los puntos prohibidos en orden, calcula para cada uno cuántos caminos lo tienen como primer punto prohibido y finalmente resta todas esas contribuciones del total libre \(\binom{2n}{n}\).
Sea \(m\) el número de puntos prohibidos. Enumerar los pares candidatos \((a,b)\) cuesta \(O(n)\) tiempo, porque tanto \(a\) como \(b\) llegan hasta \(\lfloor \sqrt{n}\rfloor\). El precálculo de factoriales e inversos factoriales hasta \(2n\) también cuesta \(O(n)\) tiempo y \(O(n)\) memoria. La DP compara cada punto prohibido con todos los anteriores, así que requiere \(O(m^2)\) tiempo y \(O(m)\) memoria adicional. En conjunto, el algoritmo usa \(O(n+m^2)\) tiempo y \(O(n+m)\) memoria.
题目要求统计从 \((0,0)\) 到 \((n,n)\) 的单调格点路径数量，每一步只能向右或向上。若一条路径从未经过任何禁点，则称其为 admissible path。
在这些实现中，禁点恰好是所有内部的平方坐标点
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}$$
最终答案对 \(10^9+7\) 取模。
若 \((x_1,y_1)\) 与 \((x_2,y_2)\) 满足 \(x_1 \le x_2\) 且 \(y_1 \le y_2\)，那么从前者到后者的单调路径必须恰好走 \(x_2-x_1\) 次向右和 \(y_2-y_1\) 次向上。因此路径条数为
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}$$
特别地，不考虑禁点时，从原点到终点的总路径数是
$$\binom{2n}{n}$$
只有坐标不超过 \(n\) 的点才可能影响答案，所以只需枚举 \(a,b \le \lfloor \sqrt{n}\rfloor\)。条件 \(a^2+b^2=c^2\) 表示 \((a,b,c)\) 构成勾股三元组，每一组都会产生一个禁点 \((a^2,b^2)\)。
将所有禁点按字典序排序后记为
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m)$$
这个顺序与单调移动相容。如果一条路径能够从 \(P_j\) 走到 \(P_i\)，那么必有 \(x_j \le x_i\) 且 \(y_j \le y_i\)，于是 \(P_j\) 一定排在 \(P_i\) 之前。
对每个禁点 \(P_i\)，定义 \(B_i\) 为从 \((0,0)\) 到 \(P_i\) 的路径中，“第一次碰到的禁点正好是 \(P_i\)” 的路径数。先看不受限制的总数：
$$\binom{x_i+y_i}{x_i}$$
如果某条路径先到达更早的禁点 \(P_j\)，再走到 \(P_i\)，则这样的路径数为
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j}$$
其中需要满足 \(x_j \le x_i\) 且 \(y_j \le y_i\)。因此有递推式
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}$$
这可以看作是按照坐标偏序进行的拓扑式容斥动态规划。
每一条不合法的终点路径都有唯一的“第一个禁点”，所以最终答案为
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}$$
当 \(n=5\) 时，没有禁点。因为可能的平方坐标只有 \(1\) 和 \(4\)，而 \(1+1\)、\(1+4\)、\(4+1\)、\(4+4\) 都不是完全平方数，所以
$$A(5)=\binom{10}{5}=252$$
当 \(n=16\) 时，禁点只有 \((9,16)\) 和 \((16,9)\)，它们来自 \(3^2+4^2=5^2\) 及其交换形式。不受限制的总路径数为
$$\binom{32}{16}=601080390$$
从原点到每个禁点的路径数都是
$$\binom{9+16}{9}=\binom{25}{9}=2042975$$
这两个禁点互不支配，因此同一条单调路径不可能同时经过它们。于是
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
这与实现中的检查值一致。
所有组合数都在素数模
$$M=10^9+7$$
下计算。实现会预处理到 \(2n\) 的阶乘和逆阶乘，因此
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}$$
逆元利用费马小定理得到：
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}$$
完成预处理后，每次组合数查询都是 \(O(1)\)。
C++、Python 和 Java 实现遵循同一条主线。首先建立一个能够快速判断某个数在 \(2n\) 以内是否为平方数的结构。然后枚举 \(n \times n\) 方格中的所有 \((a^2,b^2)\) 候选点，只保留满足勾股条件的点，并对它们排序去重。接着预处理阶乘和逆阶乘表，以便所有路径公式中的组合数都能在 \(10^9+7\) 模下常数时间求出。
准备完成后，程序按顺序扫描禁点，计算每个禁点作为“第一个禁点”时对应的路径数，最后把这些不合法贡献从自由总数 \(\binom{2n}{n}\) 中减掉。
设禁点个数为 \(m\)。枚举候选对 \((a,b)\) 的时间为 \(O(n)\)，因为 \(a\) 与 \(b\) 都只需遍历到 \(\lfloor \sqrt{n}\rfloor\)。预处理到 \(2n\) 的阶乘与逆阶乘需要 \(O(n)\) 时间和 \(O(n)\) 空间。动态规划部分会把每个禁点与之前所有禁点比较，因此需要 \(O(m^2)\) 时间和 \(O(m)\) 的额外空间。总复杂度为 \(O(n+m^2)\) 时间与 \(O(n+m)\) 空间。
Нужно посчитать количество монотонных путей из \((0,0)\) в \((n,n)\), где каждый шаг идет либо вправо, либо вверх. Путь считается допустимым, если он никогда не проходит через запрещенную точку.
В используемых реализациях запрещенными являются ровно внутренние точки с квадратными координатами
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$$
Ответ требуется по модулю \(10^9+7\).
Пусть \((x_1,y_1)\) и \((x_2,y_2)\) удовлетворяют условиям \(x_1 \le x_2\) и \(y_1 \le y_2\). Тогда любой монотонный путь между ними содержит ровно \(x_2-x_1\) шагов вправо и \(y_2-y_1\) шагов вверх. Следовательно, число таких путей равно
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}.$$
В частности, без каких-либо запретов число путей из начала в \((n,n)\) равно
$$\binom{2n}{n}.$$
Имеют значение только точки с координатами не больше \(n\), поэтому достаточно перебрать \(a,b \le \lfloor \sqrt{n}\rfloor\). Условие \(a^2+b^2=c^2\) означает, что \((a,b,c)\) образует пифагорову тройку, а каждая такая пара дает запрещенную точку \((a^2,b^2)\).
После сортировки обозначим запрещенные точки так:
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m).$$
Этот порядок согласован с монотонным движением: если путь может пройти из \(P_j\) в \(P_i\), то обязательно \(x_j \le x_i\) и \(y_j \le y_i\), а значит, \(P_j\) стоит раньше \(P_i\) в лексикографическом порядке.
Для каждой запрещенной точки \(P_i\) введем \(B_i\): это число путей из \((0,0)\) в \(P_i\), у которых первой запрещенной точкой является именно \(P_i\). Полное число путей в \(P_i\) без ограничений равно
$$\binom{x_i+y_i}{x_i}.$$
Если путь сначала попадает в более раннюю запрещенную точку \(P_j\), а затем идет в \(P_i\), то число таких путей равно
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j}$$
при условиях \(x_j \le x_i\) и \(y_j \le y_i\). Поэтому получаем рекуррентную формулу
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}.$$
Это динамика по топологическому порядку частичного порядка, заданного покоординатным сравнением.
У каждого недопустимого пути в \((n,n)\) есть единственная первая запрещенная точка, поэтому окончательная формула имеет вид
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}.$$
Для \(n=5\) запрещенных точек нет, потому что возможные квадратные координаты только \(1\) и \(4\), а суммы \(1+1\), \(1+4\), \(4+1\), \(4+4\) не являются квадратами. Значит,
$$A(5)=\binom{10}{5}=252.$$
Для \(n=16\) запрещенные точки равны \((9,16)\) и \((16,9)\), что соответствует равенству \(3^2+4^2=5^2\) и перестановке катетов. Общее число путей без ограничений равно
$$\binom{32}{16}=601080390.$$
В каждую из этих точек из начала ведет
$$\binom{9+16}{9}=\binom{25}{9}=2042975$$
путей. Эти две точки несравнимы покоординатно, поэтому один монотонный путь не может пройти через обе. Следовательно,
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
что совпадает с контрольным значением в реализациях.
Все биномиальные коэффициенты вычисляются по модулю простого числа
$$M=10^9+7.$$
Реализации заранее строят таблицы факториалов и обратных факториалов до \(2n\), после чего
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}.$$
Обратные элементы находятся по малой теореме Ферма:
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$$
После этой подготовки каждая комбинация вычисляется за \(O(1)\).
Реализации на C++, Python и Java устроены одинаково. Сначала строится быстрая структура для проверки, является ли число до \(2n\) квадратом. Затем перечисляются все кандидаты \((a^2,b^2)\) внутри квадрата \(n \times n\), сохраняются только точки, удовлетворяющие пифагорову условию, после чего список сортируется и очищается от повторов. Далее предвычисляются факториалы и обратные факториалы, чтобы все биномиальные коэффициенты в формулах путей получать за константное время по модулю \(10^9+7\).
После этого реализация проходит по запрещенным точкам в порядке сортировки, вычисляет число путей, для которых каждая точка является первой запрещенной, и в конце вычитает все недопустимые вклады из свободного количества \(\binom{2n}{n}\).
Пусть \(m\) обозначает число запрещенных точек. Перебор всех пар \((a,b)\) занимает \(O(n)\) времени, потому что и \(a\), и \(b\) изменяются до \(\lfloor \sqrt{n}\rfloor\). Предвычисление факториалов и обратных факториалов до \(2n\) также требует \(O(n)\) времени и \(O(n)\) памяти. Динамика сравнивает каждую запрещенную точку со всеми предыдущими, поэтому стоит \(O(m^2)\) по времени и \(O(m)\) по дополнительной памяти. В итоге полный алгоритм работает за \(O(n+m^2)\) и использует \(O(n+m)\) памяти.
نريد عدّ المسارات الأحادية من \((0,0)\) إلى \((n,n)\)، حيث تكون كل خطوة إما إلى اليمين أو إلى الأعلى. يكون المسار مقبولًا إذا لم يمر بأي نقطة ممنوعة.
في هذه الحلول، النقاط الممنوعة هي بالضبط النقاط الداخلية ذات الإحداثيات المربعة
$$F_n=\{(a^2,b^2): 1 \le a,b \le \lfloor \sqrt{n}\rfloor,\ \exists c \in \mathbb{Z}_{>0}: a^2+b^2=c^2\}.$$
ويحسب الجواب بترديد \(10^9+7\).
إذا كانت \((x_1,y_1)\) و\((x_2,y_2)\) تحققان \(x_1 \le x_2\) و\(y_1 \le y_2\)، فإن أي مسار أحادي بينهما يجب أن يحتوي على \(x_2-x_1\) خطوات إلى اليمين و\(y_2-y_1\) خطوات إلى الأعلى. لذلك يكون عدد هذه المسارات
$$\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}.$$
وبصورة خاصة، من دون نقاط ممنوعة يكون عدد المسارات من البداية إلى \((n,n)\) هو
$$\binom{2n}{n}.$$
النقاط الوحيدة المهمة هي التي لا تتجاوز إحداثياتها \(n\)، لذلك يكفي تعداد \(a,b \le \lfloor \sqrt{n}\rfloor\). الشرط \(a^2+b^2=c^2\) يعني أن \((a,b,c)\) يشكل ثلاثية فيثاغورس، وكل زوج من هذا النوع يولد نقطة ممنوعة هي \((a^2,b^2)\).
بعد ترتيب النقاط الممنوعة ترتيبًا معجميًا نكتبها بالشكل
$$P_1=(x_1,y_1),\ P_2=(x_2,y_2),\ \dots,\ P_m=(x_m,y_m).$$
هذا الترتيب منسجم مع الحركة الأحادية: إذا كان المسار يستطيع الانتقال من \(P_j\) إلى \(P_i\)، فلا بد أن \(x_j \le x_i\) و\(y_j \le y_i\)، وبالتالي يظهر \(P_j\) قبل \(P_i\) في الترتيب.
لكل نقطة ممنوعة \(P_i\)، لتكن \(B_i\) عدد المسارات من \((0,0)\) إلى \(P_i\) التي تكون فيها أول نقطة ممنوعة يتم الوصول إليها هي \(P_i\) نفسها. العدد الكلي غير المقيّد للمسارات إلى \(P_i\) هو
$$\binom{x_i+y_i}{x_i}.$$
أما إذا مرّ المسار أولًا عبر نقطة ممنوعة سابقة \(P_j\) ثم واصل إلى \(P_i\)، فإن عدد هذه المسارات يساوي
$$B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j}$$
مع الشرط \(x_j \le x_i\) و\(y_j \le y_i\). لذلك نحصل على العلاقة
$$B_i=\binom{x_i+y_i}{x_i}-\sum_{\substack{j \lt i \\ x_j \le x_i \\ y_j \le y_i}} B_j \binom{(x_i-x_j)+(y_i-y_j)}{x_i-x_j} \pmod{10^9+7}.$$
وهذا برنامج ديناميكي يسير وفق ترتيب طوبولوجي للترتيب الجزئي المعطى بالمقارنة الإحداثية.
كل مسار غير مقبول إلى \((n,n)\) يملك نقطة ممنوعة أولى وحيدة، ومن ثم يكون الجواب النهائي
$$A(n)=\binom{2n}{n}-\sum_{i=1}^{m} B_i \binom{(n-x_i)+(n-y_i)}{n-x_i} \pmod{10^9+7}.$$
عندما \(n=5\) لا توجد أي نقطة ممنوعة، لأن الإحداثيات المربعة الممكنة هي \(1\) و\(4\) فقط، والمجاميع \(1+1\) و\(1+4\) و\(4+1\) و\(4+4\) ليست مربعات كاملة. لذلك
$$A(5)=\binom{10}{5}=252.$$
وعندما \(n=16\)، تكون النقطتان الممنوعتان هما \((9,16)\) و\((16,9)\)، الناتجتان من العلاقة \(3^2+4^2=5^2\) مع تبادل الضلعين. العدد الكلي للمسارات من دون قيود هو
$$\binom{32}{16}=601080390.$$
ويصل إلى كل نقطة ممنوعة من الأصل عدد مسارات مقداره
$$\binom{9+16}{9}=\binom{25}{9}=2042975.$$
هاتان النقطتان غير قابلتين للمقارنة إحداثيًا، لذا لا يمكن لمسار أحادي واحد أن يمر بهما معًا. ومن ثم
$$A(16)=\binom{32}{16}-2\binom{25}{9}=596994440,$$
وهو بالضبط مقدار التحقق المستخدم في الحلول.
جميع معاملات ثنائية الحد تحسب بترديد العدد الأولي
$$M=10^9+7.$$
تقوم الحلول بتهيئة المضروبات ومعكوسات المضروبات حتى \(2n\)، وبالتالي
$$\binom{N}{R}\equiv N! \cdot (R!)^{-1} \cdot ((N-R)!)^{-1} \pmod{M}.$$
أما المعكوسات فتستخرج من مبرهنة فيرما الصغرى:
$$a^{-1}\equiv a^{M-2}\pmod{M}, \qquad a \not\equiv 0 \pmod{M}.$$
بعد هذه التهيئة تصبح كل قيمة ثنائية الحد قابلة للحساب في زمن \(O(1)\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. في البداية تُبنى بنية سريعة لاختبار ما إذا كان عدد ما حتى \(2n\) مربعًا كاملًا. بعد ذلك تُحصى جميع النقاط المرشحة \((a^2,b^2)\) داخل المربع \(n \times n\)، وتُحتفظ فقط بالنقاط التي تحقق شرط فيثاغورس، ثم تُرتب وتزال التكرارات منها. بعد ذلك تُحضّر جداول المضروبات ومعكوسات المضروبات حتى يمكن حساب كل معاملات ثنائية الحد المطلوبة في صيغ المسارات بزمن ثابت وبترديد \(10^9+7\).
بعد اكتمال هذه الجداول، تمرّ الشيفرة على النقاط الممنوعة بترتيبها، وتحسب لكل نقطة عدد المسارات التي تكون هذه النقطة أول نقطة ممنوعة فيها، ثم تطرح كل الإسهامات غير المقبولة من العدد الحر \(\binom{2n}{n}\).
ليكن \(m\) عدد النقاط الممنوعة. تعداد الأزواج المرشحة \((a,b)\) يحتاج إلى \(O(n)\) زمنًا، لأن كلًا من \(a\) و\(b\) يمتد حتى \(\lfloor \sqrt{n}\rfloor\). كما أن التهيئة المسبقة للمضروبات ومعكوسات المضروبات حتى \(2n\) تحتاج إلى \(O(n)\) زمنًا و\(O(n)\) ذاكرة. البرنامج الديناميكي يقارن كل نقطة ممنوعة بجميع النقاط السابقة، ولذلك يكلف \(O(m^2)\) زمنًا و\(O(m)\) ذاكرة إضافية. المحصلة النهائية هي \(O(n+m^2)\) زمنًا و\(O(n+m)\) ذاكرة.