For coprime positive integers \(a\) and \(b\), let
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]
be the numerical semigroup generated by \(a\) and \(b\), and let \(G(a,b)\) be the set of positive integers that do not belong to \(S\). A legal frog configuration is a subset \(A\subseteq G(a,b)\) such that for any two distinct chosen gaps, their positive difference is still outside \(S\). In the language of the title, no frog attacks another.
The implementations compute the weighted total
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]
The target instance is \(F(19,53)\). The code also checks the small benchmark values \(F(3,5)=23\) and \(F(5,13)=16336\).
The key step is to stop thinking about arbitrary integers and to replace the gap set by a finite lattice diagram. In that diagram, the attack condition becomes a clean partial order, and the final sum can be computed by a one-dimensional dynamic program.
For a two-generator numerical semigroup with \(\gcd(a,b)=1\), every gap has a unique representation
\[ g(x,y)=ab-ax-by \]
with
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
So the \(x\)-th column of the diagram has height \(h(x)\), and each cell \((x,y)\) corresponds to one gap value \(g(x,y)\). The positivity condition is exactly \(ax+by\lt ab\), which is why the columns taper off like a staircase. Summing the column heights gives the classical genus formula
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
This is the finite set on which the algorithm actually works.
Take two cells \((x_1,y_1)\) and \((x_2,y_2)\). Their gap values satisfy
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]
If \(x_2\ge x_1\) and \(y_2\ge y_1\), then this difference is visibly representable by \(a\) and \(b\), so the two cells are incompatible. The important point is that the converse is also true in this bounded rectangle.
Indeed, suppose
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
with \(p,q\ge 0\). Comparing coefficients gives
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]
Because \(-b\lt x_2-x_1\lt b\), reducing modulo \(b\) forces \(p=x_2-x_1+kb\) for some integer \(k\). If \(k\lt 0\), then \(p\lt 0\), impossible. If \(k\gt 0\), then
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
again impossible since \(-a\lt y_2-y_1\lt a\). Hence \(k=0\), so \(p=x_2-x_1\) and \(q=y_2-y_1\). Therefore
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{and}\ y_2\ge y_1. \]
So two frogs attack exactly when their cells are comparable in the coordinatewise order. Legal frog configurations are precisely the antichains of this Ferrers poset.
Once the cells are read from left to right by column, an antichain has a simple description. It can use at most one cell from any fixed column, and if it chooses cells
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
with
\[ x_1\lt x_2\lt \cdots\lt x_k, \]
then it must satisfy
\[ y_1\gt y_2\gt \cdots\gt y_k. \]
The whole two-dimensional incompatibility rule collapses to one number: after the last chosen row is \(y\), every future row must be smaller than \(y\).
For \((a,b)=(3,5)\), the column heights are
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]
The cells and gap values are therefore
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
Legal nonempty antichains are
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]
For example, \(\{7,4\}\) is forbidden because \(7-4=3\in S\), while \(\{2,4\}\) is allowed because \(|4-2|=2\notin S\). The weighted total is
\[ 7+2+4+1+(2+4)+(2+1)=23, \]
matching the checkpoint. This tiny case already shows the mechanism: once row \(1\) is chosen, no later cell can be added; row \(2\) may be followed by row \(1\).
After some initial columns have been processed, let \(C(\ell)\) be the number of partial antichains for which the next chosen row must satisfy \(y\lt \ell\). Let \(W(\ell)\) be the total contribution
\[ \sum_{A}\sum_{g\in A} g \]
over those same partial antichains. Initially, the empty antichain is the only possibility, so
\[ C(a)=1,\qquad W(a)=0. \]
Now process one column \(x\) of height \(h(x)\).
If the column is skipped, the state \(\ell\) stays unchanged.
If one chooses the cell \((x,y)\), then \(y\) must satisfy
\[ 1\le y\le \min(h(x),\ell-1), \]
and the next state becomes \(y\). The selected gap value is \(g(x,y)=ab-ax-by\), so the transition is
\[ C_{\mathrm{new}}(y)\leftarrow C_{\mathrm{new}}(y)+C(\ell), \]
\[ W_{\mathrm{new}}(y)\leftarrow W_{\mathrm{new}}(y)+W(\ell)+C(\ell)\,g(x,y). \]
The first added term carries the previously accumulated weights. The second adds the newly selected gap once for each predecessor antichain. After the last column, the required value is
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]
The correctness is now transparent: the lattice bijection identifies the gaps, the comparability test identifies attacks, and the column-by-column recurrence generates every antichain exactly once.
The C++, Python, and Java implementations first swap the generators if necessary so that \(a\le b\). This does not change the semigroup \(\langle a,b\rangle\), the gap set, or the answer; it only makes the state space smaller. The code then iterates through the columns \(x=1,2,\dots,b-1\) and computes each column height \(h(x)\).
The main loop stores, for every possible row bound \(\ell\), how many partial antichains are currently possible and what the total selected-gap sum of those partial antichains is. For each column, a fresh copy of the current tables already accounts for the “skip this column” choice. Then every admissible row \(y\) updates the state indexed by \(y\), exactly as in the recurrence above.
The arithmetic is done with exact integers throughout. The Python and Java versions use arbitrary-precision integers automatically; the C++ version uses 128-bit unsigned arithmetic because the answer does not fit comfortably in 64 bits.
All three implementations include a tiny brute-force checker for small coprime pairs. It explicitly lists the gap set, enumerates every subset, rejects any subset containing an attacking pair, and sums the selected gap values for the surviving subsets. This is used only on very small instances, where the number of gaps is at most 20, to confirm the optimized dynamic program. The symmetry \(F(a,b)=F(b,a)\) and the checkpoint values \(23\) and \(16336\) are also verified before the target case is computed.
After the normalization \(a\le b\), there are \(b-1\) columns. For each column, the implementation scans \(a\) possible row bounds, and from each bound it may try up to \(a-1\) row choices. Therefore the optimized method runs in
\[ O(ba^2) \]
time and uses
\[ O(a) \]
memory. For the target pair \((19,53)\), this is tiny: only 52 columns and a state width of 19. The exhaustive checker is exponential in the number of gaps, but it is deliberately restricted to miniature instances and is not part of the final computation.
Für teilerfremde positive Zahlen \(a\) und \(b\) sei
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]
die von \(a\) und \(b\) erzeugte numerische Halbgruppe, und \(G(a,b)\) sei die Menge der positiven Zahlen, die nicht in \(S\) liegen. Eine zulässige Froschkonfiguration ist eine Teilmenge \(A\subseteq G(a,b)\), bei der für zwei verschiedene gewählte Lücken auch ihre positive Differenz außerhalb von \(S\) bleibt. Anschaulich greifen sich also keine zwei Frösche an.
Berechnet wird die gewichtete Summe
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]
Das Ziel ist \(F(19,53)\). Zusätzlich werden die kleinen Kontrollwerte \(F(3,5)=23\) und \(F(5,13)=16336\) geprüft.
Der entscheidende Schritt ist, die Lückenmenge nicht mehr als ungeordnete Zahlenmenge zu betrachten, sondern als endliches Gitterdiagramm. In diesem Diagramm wird die Angriffsbedingung zu einer sauberen Halbordnung, und daraus entsteht eine sehr kleine dynamische Programmierung.
Für eine zweierzeugte numerische Halbgruppe mit \(\gcd(a,b)=1\) besitzt jede Lücke die eindeutige Darstellung
\[ g(x,y)=ab-ax-by \]
mit
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
Die \(x\)-te Spalte des Diagramms hat also Höhe \(h(x)\), und jede Zelle \((x,y)\) steht für genau eine Lücke \(g(x,y)\). Die Bedingung \(ax+by\lt ab\) erklärt, warum die Spalten stufenförmig auslaufen. Die Summe aller Spaltenhöhen ist die bekannte Gattung
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
Für zwei Zellen \((x_1,y_1)\) und \((x_2,y_2)\) gilt
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]
Wenn \(x_2\ge x_1\) und \(y_2\ge y_1\), dann ist diese Differenz offensichtlich in \(S\) darstellbar, also sind die beiden Zellen unvereinbar. In diesem beschränkten Rechteck gilt auch die Umkehrung.
Angenommen,
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
mit \(p,q\ge 0\). Dann folgt
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]
Wegen \(-b\lt x_2-x_1\lt b\) erzwingt die Reduktion modulo \(b\) die Form \(p=x_2-x_1+kb\). Für \(k\lt 0\) wäre \(p\lt 0\), unmöglich. Für \(k\gt 0\) ergäbe sich
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
ebenfalls unmöglich, da \(-a\lt y_2-y_1\lt a\). Also ist \(k=0\), damit \(p=x_2-x_1\) und \(q=y_2-y_1\). Folglich
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{und}\ y_2\ge y_1. \]
Zwei Frösche greifen sich also genau dann an, wenn ihre Zellen in der koordinatenweisen Ordnung vergleichbar sind. Zulässige Konfigurationen sind genau die Antiketten dieses Ferrers-Posets.
Durchläuft man die Spalten von links nach rechts, dann kann eine Antikette aus jeder Spalte höchstens eine Zelle wählen. Wählt sie
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
mit
\[ x_1\lt x_2\lt \cdots\lt x_k, \]
dann muss gelten
\[ y_1\gt y_2\gt \cdots\gt y_k. \]
Die ganze zweidimensionale Verträglichkeitsbedingung reduziert sich damit auf eine einzige Zahl: Nach einer gewählten Zeile \(y\) dürfen künftig nur noch kleinere Zeilen gewählt werden.
Für \((a,b)=(3,5)\) erhält man
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]
Die Zellen und Lückenwerte sind also
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
Die zulässigen nichtleeren Antiketten sind
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]
Zum Beispiel ist \(\{7,4\}\) verboten, weil \(7-4=3\in S\), während \(\{2,4\}\) erlaubt ist, weil \(|4-2|=2\notin S\). Die gewichtete Summe lautet
\[ 7+2+4+1+(2+4)+(2+1)=23, \]
also genau der Kontrollwert. Schon hier sieht man: Nach der Wahl von Zeile \(1\) ist keine spätere Zelle mehr möglich; Zeile \(2\) kann noch von Zeile \(1\) gefolgt werden.
Nach der Verarbeitung eines Anfangsstücks von Spalten sei \(C(\ell)\) die Zahl der partiellen Antiketten, deren nächste gewählte Zeile \(y\lt \ell\) erfüllen muss. Sei \(W(\ell)\) die gesamte Gewichtssumme
\[ \sum_{A}\sum_{g\in A} g \]
über genau diese partiellen Antiketten. Zu Beginn gibt es nur die leere Antikette, also
\[ C(a)=1,\qquad W(a)=0. \]
Nun wird eine Spalte \(x\) der Höhe \(h(x)\) verarbeitet.
Wird die Spalte übersprungen, bleibt der Zustand \(\ell\) erhalten.
Wird die Zelle \((x,y)\) gewählt, dann muss
\[ 1\le y\le \min(h(x),\ell-1) \]
gelten, und der neue Zustand ist \(y\). Der neu hinzugefügte Lückenwert ist \(g(x,y)=ab-ax-by\), daher
\[ C_{\mathrm{neu}}(y)\leftarrow C_{\mathrm{neu}}(y)+C(\ell), \]
\[ W_{\mathrm{neu}}(y)\leftarrow W_{\mathrm{neu}}(y)+W(\ell)+C(\ell)\,g(x,y). \]
Der erste Summand übernimmt die bereits angesammelten Gewichte, der zweite addiert die neu gewählte Lücke einmal für jede Vorgänger-Antikette. Nach der letzten Spalte ist
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]
Die Korrektheit folgt unmittelbar aus der Gitterparametrisierung, der Vergleichbarkeitscharakterisierung der Angriffe und der eindeutigen Erzeugung jeder Antikette in Spaltenreihenfolge.
Die C++-, Python- und Java-Implementierungen vertauschen die Generatoren zunächst gegebenenfalls so, dass \(a\le b\) gilt. Das ändert weder die Halbgruppe \(\langle a,b\rangle\) noch die Lückenmenge oder den Zielwert, verkleinert aber den Zustandsraum. Danach werden die Spalten \(x=1,2,\dots,b-1\) durchlaufen und ihre Höhen \(h(x)\) berechnet.
Die Hauptschleife speichert für jede mögliche Zeilenschranke \(\ell\), wie viele partielle Antiketten es gibt und wie groß die gesamte Summe ihrer gewählten Lückenwerte ist. Für jede neue Spalte wird zunächst eine Kopie des aktuellen Zustands erzeugt; damit ist der Fall „Spalte überspringen“ bereits berücksichtigt. Danach aktualisiert jede zulässige Zeile \(y\) den durch \(y\) indizierten Folgezustand gemäß der obigen Rekurrenz.
Alle Rechnungen erfolgen exakt mit ganzen Zahlen. Python und Java verwenden dafür automatisch beliebig große Integer-Typen; in C++ wird ein 128-Bit-Integer benutzt, weil das Ergebnis nicht bequem in 64 Bit passt.
Alle drei Implementierungen enthalten außerdem eine winzige Brute-Force-Prüfung für kleine teilerfremde Paare. Dort wird die Lückenmenge explizit aufgelistet, jede Teilmenge getestet, jede angreifende Paarung verworfen und die Summe der gewählten Lücken für die verbleibenden Teilmengen akkumuliert. Diese Vollsuche wird nur bei höchstens 20 Lücken eingesetzt und dient ausschließlich dazu, die optimierte DP zu bestätigen. Außerdem werden die Symmetrie \(F(a,b)=F(b,a)\) sowie die Kontrollwerte \(23\) und \(16336\) geprüft.
Nach der Normalisierung \(a\le b\) gibt es \(b-1\) Spalten. Für jede Spalte betrachtet die Implementierung \(a\) mögliche Zeilenschranken und von jeder Schranke aus höchstens \(a-1\) Zeilen. Daher benötigt das optimierte Verfahren
\[ O(ba^2) \]
Zeit und
\[ O(a) \]
Speicher. Für das Zielpaar \((19,53)\) ist das sehr klein: 52 Spalten bei Zustandsbreite 19. Die Vollsuche ist exponentiell in der Zahl der Lücken, wird aber bewusst nur für Miniaturbeispiele verwendet und spielt für die eigentliche Zielberechnung keine Rolle.
\(a\) ve \(b\) aralarında asal pozitif tam sayılar olsun. Şu kümeyi tanımlayalım:
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\}. \]
Bu, \(a\) ve \(b\) tarafından üretilen sayısal yarıgruptur. \(G(a,b)\) ise \(S\) içinde yazılamayan pozitif tam sayıların kümesidir. Geçerli bir kurbağa yerleşimi, \(A\subseteq G(a,b)\) olacak şekilde seçilen bir altkümedir ve farklı iki seçili boşluğun pozitif farkı yine \(S\) içinde olmamalıdır. Başka bir deyişle, seçilen kurbağalar birbirini “vuramaz”.
Uygulamaların hesapladığı nicelik
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g \]
şeklindedir. Hedef örnek \(F(19,53)\) olup kod ayrıca \(F(3,5)=23\) ve \(F(5,13)=16336\) kontrol değerlerini doğrular.
Temel fikir, boşlukları tek tek tam sayılar olarak değil, sonlu bir kafes diyagramının hücreleri olarak görmektir. Bu bakış açısı saldırı koşulunu kısmi düzene dönüştürür ve problem küçük bir dinamik programlamaya iner.
\(\gcd(a,b)=1\) olan iki üreteçli sayısal yarıgrup için her boşluk tekil olarak
\[ g(x,y)=ab-ax-by \]
biçiminde yazılır; burada
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
Dolayısıyla \(x\)-inci sütunun yüksekliği \(h(x)\) olur ve her \((x,y)\) hücresi tam bir boşluk değeri \(g(x,y)\) ile eşleşir. Pozitiflik koşulu \(ax+by\lt ab\) olduğundan sütunlar basamak gibi aşağı iner. Bütün sütun yüksekliklerinin toplamı klasik genus formülünü verir:
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
\((x_1,y_1)\) ve \((x_2,y_2)\) hücrelerine karşılık gelen boşluklar için
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1) \]
eşitliği vardır. Eğer \(x_2\ge x_1\) ve \(y_2\ge y_1\) ise bu fark açıkça \(S\) içinde temsil edilebilir; dolayısıyla iki hücre birlikte seçilemez. Önemli olan nokta, bu sınırlı dikdörtgende ters yönün de doğru olmasıdır.
Gerçekten de
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
ve \(p,q\ge 0\) olsun. O zaman
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)) \]
elde edilir. \(-b\lt x_2-x_1\lt b\) olduğundan, \(b\) modunda bakınca \(p=x_2-x_1+kb\) biçimi zorunludur. \(k\lt 0\) olursa \(p\lt 0\) çıkar. \(k\gt 0\) olursa da
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
ki bu da mümkün değildir; çünkü \(-a\lt y_2-y_1\lt a\). Demek ki \(k=0\), yani \(p=x_2-x_1\) ve \(q=y_2-y_1\). Sonuç:
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{ve}\ y_2\ge y_1. \]
Böylece iki kurbağa ancak ve ancak hücreleri koordinat bazında karşılaştırılabiliyorsa birbirine saldırır. Geçerli yerleşimler, bu Ferrers posetinin tam olarak antizincirleridir.
Sütunları soldan sağa işlersek, bir antizincir aynı sütundan en fazla bir hücre seçebilir. Seçimler
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
ve
\[ x_1\lt x_2\lt \cdots\lt x_k \]
şeklindeyse mutlaka
\[ y_1\gt y_2\gt \cdots\gt y_k \]
olmalıdır. Yani iki boyutlu uyumluluk kuralı, “bir sonraki seçilecek satır bir öncekinden küçük olsun” biçimindeki tek boyutlu bir sınıra indirgenir.
\((a,b)=(3,5)\) için sütun yükseklikleri
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0 \]
olur. Buna karşılık gelen hücreler ve boşluk değerleri şöyledir:
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
Geçerli boş olmayan antizincirler
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\} \]
şeklindedir. Örneğin \(\{7,4\}\) yasaktır; çünkü \(7-4=3\in S\). Buna karşılık \(\{2,4\}\) serbesttir; çünkü \(|4-2|=2\notin S\). Ağırlıklı toplam
\[ 7+2+4+1+(2+4)+(2+1)=23 \]
çıkar. Bu minik örnek bile şu deseni gösterir: satır \(1\) seçildikten sonra daha ileri sütunlardan başka hücre eklenemez; satır \(2\) ise daha sonra satır \(1\) ile devam edebilir.
İlk birkaç sütun işlendiğinde, \(C(\ell)\) değerini “bir sonraki seçilecek satır \(y\lt \ell\) koşulunu sağlamalı” durumundaki kısmi antizincir sayısı olarak tanımlayalım. \(W(\ell)\) ise aynı kısmi antizincirler üzerinde
\[ \sum_{A}\sum_{g\in A} g \]
toplamını tutsun. Başlangıçta yalnızca boş antizincir vardır:
\[ C(a)=1,\qquad W(a)=0. \]
Şimdi yüksekliği \(h(x)\) olan bir \(x\) sütununu işleyelim.
Sütun atlanırsa durum \(\ell\) değişmez.
\((x,y)\) hücresi seçilecekse
\[ 1\le y\le \min(h(x),\ell-1) \]
olmalıdır ve yeni durum \(y\) olur. Eklenen boşluk değeri \(g(x,y)=ab-ax-by\) olduğuna göre geçiş
\[ C_{\mathrm{yeni}}(y)\leftarrow C_{\mathrm{yeni}}(y)+C(\ell), \]
\[ W_{\mathrm{yeni}}(y)\leftarrow W_{\mathrm{yeni}}(y)+W(\ell)+C(\ell)\,g(x,y) \]
şeklindedir. İlk terim önceki ağırlıkları taşır; ikinci terim yeni seçilen boşluğu, o duruma gelen her antizincir için bir kez ekler. Son sütundan sonra aranan değer
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell) \]
olur. Doğruluk; boşluk-hücre birebirliğinden, saldırı koşulunun karşılaştırılabilirlik ölçütüne eşit olmasından ve her antizincirin sütun sırasıyla tam bir kez üretilmesinden gelir.
C++, Python ve Java uygulamaları önce gerekirse üreteçleri yer değiştirerek \(a\le b\) koşulunu sağlar. Bu işlem yarıgrubu, boşluk kümesini veya cevabı değiştirmez; yalnızca durum uzayını daraltır. Ardından \(x=1,2,\dots,b-1\) sütunları üzerinden gidilip her sütunun yüksekliği \(h(x)\) hesaplanır.
Ana döngü, her olası satır üst sınırı \(\ell\) için iki bilgi saklar: o sınıra kadar gelmiş kısmi antizincirlerin sayısı ve bu kısmi antizincirlerin seçtiği boşlukların toplam ağırlığı. Her sütun başında mevcut tabloların kopyası alınır; böylece “bu sütunu hiç kullanmama” seçeneği otomatik olarak korunmuş olur. Daha sonra izin verilen her \(y\) satırı, yukarıdaki yinelemeye göre \(y\) ile indekslenen yeni durumu günceller.
Tüm işlemler tam sayı olarak ve taşmasız yapılır. Python ve Java doğal olarak büyük tam sayılar kullanır; C++ sürümü ise 64 bitin rahat yetmediği yerde 128 bitlik tamsayı aritmetiğine başvurur.
Üç uygulamanın hepsinde küçük aralarında asal örnekler için bir tam tarama doğrulaması da bulunur. Bu doğrulama önce boşluk kümesini açıkça üretir, sonra bütün altkümeleri dener, saldıran bir çift içerenleri eler ve kalanların seçilmiş boşluk toplamlarını toplar. Bu adım yalnızca boşluk sayısı en fazla 20 olan çok küçük örneklerde kullanılır; amacı optimize dinamik programlamayı teyit etmektir. Ayrıca \(F(a,b)=F(b,a)\) simetrisi ile \(23\) ve \(16336\) kontrol değerleri de sınanır.
Normalize edildikten sonra \(a\le b\) olur ve \(b-1\) adet sütun vardır. Her sütun için \(a\) adet olası satır sınırı taranır; her sınırdan da en fazla \(a-1\) satır denenir. Bu nedenle optimize yöntem
\[ O(ba^2) \]
zamanda çalışır ve
\[ O(a) \]
bellek kullanır. Hedef çift \((19,53)\) için bu yük çok küçüktür: yalnızca 52 sütun ve 19 genişliğinde bir durum uzayı vardır. Tam tarama doğrulaması ise boşluk sayısına göre üstel davranır, fakat yalnızca oyuncak örnekler için çalıştırılır ve asıl hedef hesabın parçası değildir.
Para enteros positivos coprimos \(a\) y \(b\), definimos
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]
como el semigrupo numérico generado por \(a\) y \(b\), y \(G(a,b)\) como el conjunto de enteros positivos que no pertenecen a \(S\). Una colocación legal de ranas es un subconjunto \(A\subseteq G(a,b)\) tal que, para dos huecos distintos elegidos, su diferencia positiva sigue fuera de \(S\). Dicho de otro modo, ninguna rana ataca a otra.
Las implementaciones calculan
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]
El caso objetivo es \(F(19,53)\). También se comprueban los valores pequeños \(F(3,5)=23\) y \(F(5,13)=16336\).
La idea central es reemplazar el conjunto de huecos por un diagrama finito de celdas. Dentro de ese diagrama, la condición de ataque se convierte en una relación de orden parcial y el problema completo cae en una programación dinámica de una sola dimensión.
Para un semigrupo numérico generado por dos números con \(\gcd(a,b)=1\), todo hueco se escribe de manera única como
\[ g(x,y)=ab-ax-by \]
con
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
Así, la columna \(x\) del diagrama tiene altura \(h(x)\), y cada celda \((x,y)\) representa exactamente un hueco. La positividad equivale a \(ax+by\lt ab\), y por eso las alturas descienden como una escalera. La suma total de alturas es la fórmula clásica del género:
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
Para dos celdas \((x_1,y_1)\) y \((x_2,y_2)\), sus valores satisfacen
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]
Si \(x_2\ge x_1\) y \(y_2\ge y_1\), esa diferencia es representable por \(a\) y \(b\), así que las dos celdas son incompatibles. Lo importante es que, en este rectángulo acotado, la recíproca también vale.
Supongamos
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
con \(p,q\ge 0\). Entonces
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]
Como \(-b\lt x_2-x_1\lt b\), al reducir módulo \(b\) se fuerza \(p=x_2-x_1+kb\). Si \(k\lt 0\), entonces \(p\lt 0\). Si \(k\gt 0\), se obtiene
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
lo cual también es imposible porque \(-a\lt y_2-y_1\lt a\). Así que necesariamente \(k=0\), luego \(p=x_2-x_1\) y \(q=y_2-y_1\). En consecuencia,
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{y}\ y_2\ge y_1. \]
Dos ranas se atacan exactamente cuando sus celdas son comparables en el orden coordenado. Los subconjuntos legales son, por tanto, las anticadenas del poset de Ferrers.
Si se recorren las columnas de izquierda a derecha, una anticadena puede tomar a lo sumo una celda por columna. Si elige
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
con
\[ x_1\lt x_2\lt \cdots\lt x_k, \]
entonces debe cumplirse
\[ y_1\gt y_2\gt \cdots\gt y_k. \]
Toda la restricción bidimensional se reduce así a un solo dato: después de escoger una fila \(y\), las filas futuras deben ser menores que \(y\).
Para \((a,b)=(3,5)\), las alturas son
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]
Por lo tanto, las celdas y sus huecos son
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
Las anticadenas no vacías válidas son
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]
Por ejemplo, \(\{7,4\}\) es inválida porque \(7-4=3\in S\), mientras que \(\{2,4\}\) sí es válida porque \(|4-2|=2\notin S\). La suma ponderada vale
\[ 7+2+4+1+(2+4)+(2+1)=23, \]
que coincide con el punto de control. El ejemplo deja clara la regla: una vez elegida la fila \(1\), no puede añadirse ninguna celda posterior; la fila \(2\) todavía puede ir seguida por la fila \(1\).
Después de procesar algunas columnas iniciales, sea \(C(\ell)\) el número de anticadenas parciales cuyo próximo renglón elegido debe satisfacer \(y\lt \ell\). Sea \(W(\ell)\) la suma total
\[ \sum_{A}\sum_{g\in A} g \]
sobre esas mismas anticadenas parciales. Al principio solo existe la anticadena vacía, de modo que
\[ C(a)=1,\qquad W(a)=0. \]
Ahora se procesa una columna \(x\) de altura \(h(x)\).
Si se omite la columna, el estado \(\ell\) permanece igual.
Si se elige la celda \((x,y)\), entonces debe cumplirse
\[ 1\le y\le \min(h(x),\ell-1), \]
y el nuevo estado pasa a ser \(y\). El hueco añadido es \(g(x,y)=ab-ax-by\), así que la transición es
\[ C_{\mathrm{nuevo}}(y)\leftarrow C_{\mathrm{nuevo}}(y)+C(\ell), \]
\[ W_{\mathrm{nuevo}}(y)\leftarrow W_{\mathrm{nuevo}}(y)+W(\ell)+C(\ell)\,g(x,y). \]
El primer término conserva el peso que ya traían las anticadenas anteriores. El segundo añade el nuevo hueco una vez por cada predecesora. Tras la última columna, el valor buscado es
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]
La corrección resulta de combinar la biyección entre celdas y huecos, la caracterización de los ataques como comparabilidad y la generación única de cada anticadena en orden de columnas.
Las implementaciones en C++, Python y Java intercambian primero los generadores si hace falta para garantizar \(a\le b\). Eso no altera el semigrupo \(\langle a,b\rangle\), ni el conjunto de huecos, ni la respuesta; solo reduce el ancho del estado. Después recorren las columnas \(x=1,2,\dots,b-1\) y calculan cada altura \(h(x)\).
El bucle principal guarda, para cada posible cota de fila \(\ell\), cuántas anticadenas parciales hay y cuál es la suma total de los huecos ya seleccionados en esas anticadenas. Al comenzar cada columna, una copia del estado actual ya incorpora la opción de “saltar esta columna”. A continuación, cada fila admisible \(y\) actualiza el estado indexado por \(y\) siguiendo exactamente la recurrencia matemática.
La aritmética es exacta en todo momento. Python y Java usan enteros de precisión arbitraria de forma natural; la versión en C++ emplea enteros sin signo de 128 bits porque la respuesta final supera con comodidad el rango de 64 bits.
Las tres implementaciones incluyen además una comprobación exhaustiva para pares coprimos pequeños. Allí se enumera explícitamente el conjunto de huecos, se prueban todos los subconjuntos, se descartan los que contienen una pareja atacante y se suman los valores de los huecos elegidos en los subconjuntos válidos. Esa verificación solo se usa cuando el número de huecos es como máximo 20, con el fin de confirmar la DP optimizada. También se revisan la simetría \(F(a,b)=F(b,a)\) y los valores de control \(23\) y \(16336\).
Tras imponer \(a\le b\), hay \(b-1\) columnas. Para cada columna, la implementación recorre \(a\) posibles cotas de fila y, desde cada una, prueba como mucho \(a-1\) filas. Por tanto, el método optimizado cuesta
\[ O(ba^2) \]
tiempo y
\[ O(a) \]
memoria. Para el objetivo \((19,53)\), esto es muy pequeño: solo 52 columnas y un ancho de estado de 19. La comprobación exhaustiva es exponencial en el número de huecos, pero se restringe deliberadamente a ejemplos diminutos y no forma parte del cálculo final.
设 \(a,b\) 是互素正整数，定义
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]
为由 \(a\) 与 \(b\) 生成的数值半群，\(G(a,b)\) 为所有 不能 写成这种形式的正整数集合。一次合法的“青蛙摆放”就是选取一个子集 \(A\subseteq G(a,b)\)，并要求任意两个不同被选中的空缺值，它们的正差仍然不属于 \(S\)。用题目的语言说，就是任意两只青蛙都不能互相攻击。
程序真正计算的是下面这个加权总和：
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]
目标实例是 \(F(19,53)\)。另外，代码还会先检查两个小规模验证值：\(F(3,5)=23\) 与 \(F(5,13)=16336\)。
核心转化是：不要把空缺看成一堆分散的整数，而要把它们看成一个有限格点图中的单元格。这样一来，“会不会攻击”就变成了一个偏序问题，最终只需要做一个一维动态规划。
对于 \(\gcd(a,b)=1\) 的双生成数值半群，每个空缺都能且只能写成
\[ g(x,y)=ab-ax-by \]
其中
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
因此，第 \(x\) 列的高度就是 \(h(x)\)，每个单元格 \((x,y)\) 都对应一个唯一的空缺值 \(g(x,y)\)。不等式 \(ax+by\lt ab\) 正好说明为什么列高会逐步下降，形成阶梯状的 Ferrers 图。所有列高相加得到经典的亏格公式
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
程序真正工作的对象就是这个有限图形，而不是从 1 枚举到 \(ab\) 的所有整数。
若两格分别是 \((x_1,y_1)\) 与 \((x_2,y_2)\)，则对应空缺满足
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]
如果 \(x_2\ge x_1\) 且 \(y_2\ge y_1\)，那么右边显然是一个由 \(a\) 与 \(b\) 表示出来的数，于是这两格不能同时出现。关键在于：在当前这个有界矩形里，反过来也成立。
设
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
且 \(p,q\ge 0\)。那么有
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]
因为 \(-b\lt x_2-x_1\lt b\)，模 \(b\) 化简后可知 \(p\) 必须写成 \(x_2-x_1+kb\) 的形式。若 \(k\lt 0\)，则 \(p\lt 0\)，矛盾。若 \(k\gt 0\)，则
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
同样矛盾，因为 \(-a\lt y_2-y_1\lt a\)。所以只能是 \(k=0\)，从而 \(p=x_2-x_1\)、\(q=y_2-y_1\)。于是得到精确判定：
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{且}\ y_2\ge y_1. \]
也就是说，两只青蛙互相攻击，当且仅当它们对应的两个单元格在坐标逐点比较的偏序下是可比较的。于是合法摆放恰好就是这个 Ferrers 偏序上的反链。
按列从左到右扫描时，一个反链在同一列中最多只能取一个单元格。若它依次选择
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
并且
\[ x_1\lt x_2\lt \cdots\lt x_k, \]
那么必然有
\[ y_1\gt y_2\gt \cdots\gt y_k. \]
这样，原本二维的相容性条件就压缩成了一维信息：如果上一次选中的行号是 \(y\)，那么以后只能再选比 \(y\) 更小的行。
当 \((a,b)=(3,5)\) 时，各列高度为
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]
对应的单元格与空缺值是
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
所有合法的非空反链，也就是合法的非空青蛙摆放，为
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]
例如，\(\{7,4\}\) 不合法，因为 \(7-4=3\in S\)；而 \(\{2,4\}\) 合法，因为 \(|4-2|=2\notin S\)。把这些合法集合中的元素和再全部相加，得到
\[ 7+2+4+1+(2+4)+(2+1)=23, \]
恰好等于程序中的验证值。这个小例子也直观说明了行号递减规则：一旦选了第 1 行，后面就再也不能选；若先选第 2 行，则后面仍可以接第 1 行。
处理完前若干列后，定义 \(C(\ell)\) 为这样的部分反链数量：它们下一次选择的行号必须满足 \(y\lt \ell\)。再定义 \(W(\ell)\) 为这些部分反链对目标和的总贡献，即
\[ \sum_{A}\sum_{g\in A} g. \]
初始时只有空反链，因此
\[ C(a)=1,\qquad W(a)=0. \]
现在处理一列高度为 \(h(x)\) 的第 \(x\) 列。
如果跳过这一列，状态 \(\ell\) 保持不变。
如果选择单元格 \((x,y)\)，那么必须满足
\[ 1\le y\le \min(h(x),\ell-1), \]
新的状态就变为 \(y\)。该格子的空缺值为 \(g(x,y)=ab-ax-by\)，因此递推为
\[ C_{\mathrm{new}}(y)\leftarrow C_{\mathrm{new}}(y)+C(\ell), \]
\[ W_{\mathrm{new}}(y)\leftarrow W_{\mathrm{new}}(y)+W(\ell)+C(\ell)\,g(x,y). \]
第一项保留此前已经积累好的贡献，第二项表示把当前新选中的空缺对每个前驱部分反链各加一次。所有列处理完以后，答案就是
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]
正确性来源于三个环节的无缝衔接：单元格与空缺的一一对应，攻击关系与可比较关系的等价，以及按列扫描时每个反链都只会被生成一次。
C++、Python 和 Java 的实现都会先在必要时交换两个生成元，使得 \(a\le b\)。这不会改变半群 \(\langle a,b\rangle\)、空缺集合或者最终答案，只是把动态规划的状态宽度压到较小的那个生成元。随后，程序遍历 \(x=1,2,\dots,b-1\)，逐列计算高度 \(h(x)\)。
主循环对每个可能的行上界 \(\ell\) 保存两类信息：当前可形成多少个部分反链，以及这些部分反链已经选中的空缺值总和是多少。处理一列时，先复制当前状态，这一步自然就把“整列跳过”的选择保留下来；随后再对所有允许的行 \(y\) 做更新，把状态推进到以 \(y\) 为新上界的位置。
整个过程都需要精确整数运算。Python 与 Java 可以直接使用任意精度整数；C++ 实现则采用 128 位无符号整数，因为最终结果并不适合放在 64 位范围内。
三个版本还都带有一个小型的完全枚举检查器，只针对很小的互素参数运行。它会先显式列出空缺集合，再枚举所有子集，删去含有互相攻击对的子集，并把剩余子集的元素和全部累加起来。这种做法只在空缺数不超过 20 的情形下使用，用来核对优化后的动态规划是否正确。代码还会顺便验证对称性 \(F(a,b)=F(b,a)\) 以及 \(23\) 和 \(16336\) 这两个基准值。
在规范化为 \(a\le b\) 之后，一共有 \(b-1\) 列。每一列会扫描 \(a\) 个可能的行上界，而从每个上界出发最多尝试 \(a-1\) 个行选择。因此，优化算法的时间复杂度是
\[ O(ba^2) \]
，空间复杂度是
\[ O(a) \]
。对目标 \((19,53)\) 来说，这个规模非常小，只需要处理 52 列和宽度为 19 的状态数组。完全枚举检查器在空缺数上是指数级的，但它只用于微型样例，不参与最终目标的实际求值。
Пусть \(a\) и \(b\) — взаимно простые положительные числа, и
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]
— числовая полугруппа, порождённая \(a\) и \(b\). Обозначим через \(G(a,b)\) множество положительных чисел, которые не лежат в \(S\). Допустимая расстановка лягушек — это подмножество \(A\subseteq G(a,b)\), в котором для любых двух разных выбранных лакун их положительная разность тоже не принадлежит \(S\). Иными словами, никакие две лягушки не бьют друг друга.
Искомая величина имеет вид
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]
Целевой случай — \(F(19,53)\). Кроме того, код проверяет контрольные значения \(F(3,5)=23\) и \(F(5,13)=16336\).
Главная идея состоит в том, чтобы заменить множество лакун конечной диаграммой клеток. На этой диаграмме условие атаки превращается в условие сравнимости по частичному порядку, а затем задача решается небольшой одномерной динамикой.
Для числовой полугруппы с двумя порождающими и \(\gcd(a,b)=1\) каждая лакуна единственным образом записывается как
\[ g(x,y)=ab-ax-by \]
при условиях
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
Значит, у столбца \(x\) высота равна \(h(x)\), а каждая клетка \((x,y)\) соответствует ровно одной лакуне \(g(x,y)\). Неравенство \(ax+by\lt ab\) объясняет, почему получаем ступенчатую фигуру типа диаграммы Феррерса. Сумма высот столбцов даёт классическую формулу рода
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
Для двух клеток \((x_1,y_1)\) и \((x_2,y_2)\) выполняется
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]
Если \(x_2\ge x_1\) и \(y_2\ge y_1\), то эта разность явно представима через \(a\) и \(b\), значит клетки несовместимы. Важно, что в нашем ограниченном прямоугольнике верно и обратное.
Предположим, что
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
при \(p,q\ge 0\). Тогда
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]
Так как \(-b\lt x_2-x_1\lt b\), после рассмотрения по модулю \(b\) получаем, что \(p\) обязан иметь вид \(x_2-x_1+kb\). При \(k\lt 0\) вышло бы \(p\lt 0\), что невозможно. При \(k\gt 0\) получили бы
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
что тоже невозможно, поскольку \(-a\lt y_2-y_1\lt a\). Значит, \(k=0\), то есть \(p=x_2-x_1\) и \(q=y_2-y_1\). Поэтому
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{и}\ y_2\ge y_1. \]
Две лягушки атакуют друг друга тогда и только тогда, когда соответствующие клетки сравнимы по покоординатному порядку. Следовательно, допустимые расстановки — это в точности антицепи диаграммы Феррерса.
Если идти по столбцам слева направо, то в каждой колонке антицепь может выбрать не более одной клетки. Если выбраны клетки
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
и
\[ x_1\lt x_2\lt \cdots\lt x_k, \]
то обязательно
\[ y_1\gt y_2\gt \cdots\gt y_k. \]
Таким образом, вся двумерная несовместимость сжимается до одного параметра: после выбора строки \(y\) в будущем разрешены только меньшие строки.
Для \((a,b)=(3,5)\) высоты столбцов равны
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]
Соответствующие клетки и значения лакун таковы:
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
Допустимые непустые антицепи:
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]
Например, \(\{7,4\}\) запрещено, потому что \(7-4=3\in S\), а \(\{2,4\}\) разрешено, потому что \(|4-2|=2\notin S\). Взвешенная сумма равна
\[ 7+2+4+1+(2+4)+(2+1)=23, \]
что совпадает с контрольным значением. Этот пример показывает правило убывания строк: после строки \(1\) уже нельзя взять ничего дальше; после строки \(2\) ещё можно перейти к строке \(1\).
После обработки некоторого начального набора столбцов обозначим через \(C(\ell)\) число частичных антицепей, для которых следующий выбранный индекс строки должен удовлетворять \(y\lt \ell\). Через \(W(\ell)\) обозначим суммарный вклад
\[ \sum_{A}\sum_{g\in A} g \]
по этим же частичным антицепям. Изначально существует только пустая антицепь, поэтому
\[ C(a)=1,\qquad W(a)=0. \]
Теперь обрабатывается столбец \(x\) высоты \(h(x)\).
Если его пропустить, состояние \(\ell\) не меняется.
Если выбрать клетку \((x,y)\), то необходимо
\[ 1\le y\le \min(h(x),\ell-1), \]
и новым состоянием становится \(y\). Добавляемая лакуна равна \(g(x,y)=ab-ax-by\), следовательно, переход имеет вид
\[ C_{\mathrm{new}}(y)\leftarrow C_{\mathrm{new}}(y)+C(\ell), \]
\[ W_{\mathrm{new}}(y)\leftarrow W_{\mathrm{new}}(y)+W(\ell)+C(\ell)\,g(x,y). \]
Первое слагаемое переносит уже накопленный вес, второе добавляет новый выбранный элемент по одному разу для каждой предшествующей антицепи. После последнего столбца ответ равен
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]
Корректность следует из биекции между клетками и лакунами, из эквивалентности атак и сравнимости, а также из того, что каждая антицепь строится в столбцовом порядке ровно один раз.
Реализации на C++, Python и Java при необходимости сначала меняют генераторы местами так, чтобы выполнялось \(a\le b\). Это не меняет ни полугруппу \(\langle a,b\rangle\), ни множество лакун, ни итоговый ответ, а лишь уменьшает ширину состояния. Затем код проходит по столбцам \(x=1,2,\dots,b-1\) и вычисляет каждую высоту \(h(x)\).
Главный цикл хранит для каждого возможного верхнего ограничения \(\ell\) две величины: сколько частичных антицепей сейчас существует и какова суммарная сумма уже выбранных лакун во всех этих частичных антицепях. Для каждой новой колонки сначала копируется текущее состояние, что автоматически учитывает вариант «не брать ничего из этой колонки». Затем каждая допустимая строка \(y\) обновляет состояние с индексом \(y\) в точном соответствии с математической рекуррентной формулой.
Вычисления выполняются в точной целочисленной арифметике. Python и Java используют целые числа произвольной длины; версия на C++ применяет 128-битные беззнаковые целые, потому что ответ выходит за удобный диапазон 64 бит.
Во всех трёх версиях есть также маленькая проверка полным перебором для небольших взаимно простых пар. Там явно строится множество лакун, затем перебираются все его подмножества, отбрасываются те, где есть атакующая пара, и суммируются значения выбранных лакун в оставшихся подмножествах. Такой перебор используется только при числе лакун не более 20 и нужен лишь для проверки оптимизированной динамики. Кроме того, проверяются симметрия \(F(a,b)=F(b,a)\) и контрольные числа \(23\) и \(16336\).
После нормализации \(a\le b\) имеется \(b-1\) столбцов. Для каждого столбца код рассматривает \(a\) возможных ограничений по строке и из каждого такого состояния пробует не более \(a-1\) строк. Поэтому оптимизированный алгоритм работает за
\[ O(ba^2) \]
времени и требует
\[ O(a) \]
памяти. Для целевой пары \((19,53)\) это очень мало: всего 52 столбца и ширина состояния 19. Полный перебор имеет экспоненциальную сложность по числу лакун, но намеренно ограничен крошечными примерами и не участвует в финальном расчёте.
لعددين صحيحين موجبين أوليين فيما بينهما \(a\) و\(b\)، نعرّف
\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]
على أنه شبه الزمرة العددية المولدة بواسطة \(a\) و\(b\)، ونكتب \(G(a,b)\) لمجموعة الأعداد الصحيحة الموجبة التي لا تنتمي إلى \(S\). الترتيب القانوني للضفادع هو اختيار مجموعة جزئية \(A\subseteq G(a,b)\) بحيث إن الفرق الموجب بين أي عنصرين مختلفين مختارين يبقى خارج \(S\). بلغة عنوان المسألة: لا توجد ضفدعتان تتهاجمان.
الكمية التي تحسبها التطبيقات هي
\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]
الحالة المستهدفة هي \(F(19,53)\)، كما يتحقق الكود أيضًا من القيمتين الصغيرتين \(F(3,5)=23\) و\(F(5,13)=16336\).
الفكرة الحاسمة هي التوقف عن النظر إلى الفجوات كأعداد منفصلة، واستبدالها بمخطط شبكي محدود. داخل هذا المخطط تتحول قاعدة الهجوم إلى ترتيب جزئي واضح، ومن ثم تنخفض المسألة كلها إلى برمجة ديناميكية أحادية البعد.
في شبه الزمرة العددية ذات المولدين ومع \(\gcd(a,b)=1\)، يمكن كتابة كل فجوة بشكل وحيد على الصورة
\[ g(x,y)=ab-ax-by \]
حيث
\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]
إذًا ارتفاع العمود رقم \(x\) يساوي \(h(x)\)، وكل خلية \((x,y)\) تمثل فجوة واحدة بعينها هي \(g(x,y)\). الشرط \(ax+by\lt ab\) هو الذي يجعل الأعمدة تتناقص على شكل درج. كما أن مجموع ارتفاعات الأعمدة يعطي الصيغة الكلاسيكية للجنس
\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]
إذا أخذنا الخليتين \((x_1,y_1)\) و\((x_2,y_2)\)، فإن قيمتي الفجوتين تحققان
\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]
إذا كان \(x_2\ge x_1\) و\(y_2\ge y_1\)، فالطرف الأيمن قابل للتمثيل بوضوح بواسطة \(a\) و\(b\)، ولذلك لا يجوز اختيار الخليتين معًا. والنقطة المهمة أن العكس صحيح أيضًا داخل هذا المستطيل المحدود.
افترض أن
\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]
مع \(p,q\ge 0\). عندئذ نحصل على
\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]
وبما أن \(-b\lt x_2-x_1\lt b\)، فإن النظر بترديد \(b\) يفرض أن يكون \(p=x_2-x_1+kb\). إذا كان \(k\lt 0\) فهذا يعطي \(p\lt 0\)، وهو محال. وإذا كان \(k\gt 0\) نحصل على
\[ q=(y_2-y_1)-ka\lt a-a=0, \]
وهو محال أيضًا لأن \(-a\lt y_2-y_1\lt a\). إذن لا بد أن يكون \(k=0\)، ومن ثم \(p=x_2-x_1\) و\(q=y_2-y_1\). وبالتالي
\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1,\qquad y_2\ge y_1. \]
أي أن ضفدعتين تتهاجمان إذا وفقط إذا كانت الخليتان المقابلتان لهما قابلتين للمقارنة في الترتيب الإحداثي. ومن ثم فكل ترتيب قانوني للضفادع هو بالضبط anti-chain في poset فيريرز.
عند المرور على الأعمدة من اليسار إلى اليمين، لا تستطيع anti-chain أن تختار أكثر من خلية واحدة من العمود نفسه. وإذا اختارت الخلايا
\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]
بحيث
\[ x_1\lt x_2\lt \cdots\lt x_k, \]
فلا بد أن يكون
\[ y_1\gt y_2\gt \cdots\gt y_k. \]
وهكذا تنهار القيود ثنائية البعد كلها إلى معلومة واحدة: إذا كان آخر صف مختار هو \(y\)، فلا يمكن لاحقًا إلا اختيار صف أصغر من \(y\).
عند \((a,b)=(3,5)\) تكون ارتفاعات الأعمدة
\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]
ومن ثم تكون الخلايا وقيم الفجوات المقابلة لها
\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]
الـ anti-chains غير الفارغة المسموح بها هي
\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]
فمثلًا المجموعة \(\{7,4\}\) ممنوعة لأن \(7-4=3\in S\)، بينما \(\{2,4\}\) مسموح بها لأن \(|4-2|=2\notin S\). وإذا جمعنا مجموع عناصر كل مجموعة قانونية نحصل على
\[ 7+2+4+1+(2+4)+(2+1)=23, \]
وهو تمامًا مقدار التحقق الموجود في الكود. كما يوضح المثال لماذا يجب أن تتناقص الصفوف: بعد اختيار الصف \(1\) لا يمكن إضافة أي خلية لاحقة، أما الصف \(2\) فيمكن أن يتبعه الصف \(1\).
بعد معالجة عدد من الأعمدة الأولى، لنرمز بـ \(C(\ell)\) إلى عدد الـ anti-chains الجزئية التي يجب أن يحقق اختيارها القادم الشرط \(y\lt \ell\). ولنرمز بـ \(W(\ell)\) إلى مجموع المساهمات
\[ \sum_{A}\sum_{g\in A} g \]
على هذه الـ anti-chains الجزئية نفسها. في البداية لا يوجد إلا الـ anti-chain الفارغ، ولذلك
\[ C(a)=1,\qquad W(a)=0. \]
الآن نعالج عمودًا ارتفاعه \(h(x)\).
إذا تم تجاهل العمود، فإن الحالة \(\ell\) تبقى كما هي.
أما إذا اخترنا الخلية \((x,y)\)، فلا بد أن يكون
\[ 1\le y\le \min(h(x),\ell-1), \]
وتصبح الحالة الجديدة هي \(y\). وقيمة الفجوة المضافة هي \(g(x,y)=ab-ax-by\)، ولذلك يكون الانتقال
\[ C_{\mathrm{new}}(y)\leftarrow C_{\mathrm{new}}(y)+C(\ell), \]
\[ W_{\mathrm{new}}(y)\leftarrow W_{\mathrm{new}}(y)+W(\ell)+C(\ell)\,g(x,y). \]
الحد الأول ينقل الوزن المتراكم سابقًا، والحد الثاني يضيف الفجوة الجديدة مرة واحدة لكل anti-chain سابقة. وبعد آخر عمود يصبح الجواب
\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]
وصحة هذه الصيغة تأتي مباشرة من المطابقة بين الخلايا والفجوات، ومن كون الهجوم يكافئ القابلية للمقارنة، ومن أن كل anti-chain تُبنى مرة واحدة فقط عند السير عمودًا بعد عمود.
تبدأ تطبيقات C++ وPython وJava بتبديل المولدين عند الحاجة بحيث يصبح \(a\le b\). هذا لا يغيّر شبه الزمرة \(\langle a,b\rangle\) ولا مجموعة الفجوات ولا الجواب النهائي، وإنما يقلل فقط عرض فضاء الحالات. بعد ذلك تمر الشيفرة على الأعمدة \(x=1,2,\dots,b-1\) وتحسب ارتفاع كل عمود \(h(x)\).
تحتفظ الحلقة الرئيسية، لكل حد علوي ممكن للصف \(\ell\)، بمعلومتين: عدد الـ anti-chains الجزئية الحالية، ومجموع قيم الفجوات المختارة داخل تلك الـ anti-chains. عند بداية كل عمود، تُنسخ الحالة الحالية أولًا، وبهذا تكون إمكانية “تجاوز العمود كله” ممثلة تلقائيًا. ثم تقوم كل قيمة صف مسموحة \(y\) بتحديث الحالة المفهرسة بـ \(y\) وفقًا للعلاقة الرياضية السابقة.
جميع العمليات تتم بحسابات صحيحة دقيقة. تستعمل نسختا Python وJava أعدادًا صحيحة ذات دقة غير محدودة، بينما تستخدم نسخة C++ أعدادًا صحيحة غير موقعة بعرض 128 بت لأن النتيجة النهائية لا تلائم 64 بت بسهولة.
تحتوي النسخ الثلاث أيضًا على مدقق صغير يعتمد على التعداد الكامل للحالات الصغيرة ذات المولدين الأوليين فيما بينهما. فهو يولد مجموعة الفجوات صراحة، ثم يجرب كل المجموعات الجزئية، ويحذف كل مجموعة تحتوي على زوج متهاجم، ويجمع قيم الفجوات المختارة في المجموعات الباقية. هذا الفحص لا يُستخدم إلا عندما لا يزيد عدد الفجوات على 20، وهدفه الوحيد هو التأكد من صحة البرمجة الديناميكية المحسنة. كما يجري التحقق من التناظر \(F(a,b)=F(b,a)\) ومن القيمتين \(23\) و\(16336\).
بعد ترتيب المعطيات بحيث \(a\le b\)، يصبح لدينا \(b-1\) عمودًا. ولكل عمود تفحص الشيفرة \(a\) حدود ممكنة للصف، ومن كل حد قد تجرب ما يصل إلى \(a-1\) صفًا. لذلك فإن الطريقة المحسنة تعمل بزمن
\[ O(ba^2) \]
وتستخدم ذاكرة
\[ O(a) \]
. بالنسبة إلى الحالة الهدف \((19,53)\)، فهذه كلفة صغيرة جدًا: 52 عمودًا فقط وعرض حالة يساوي 19. أما الفاحص القائم على التعداد الكامل فتعقيده أسي في عدد الفجوات، لكنه محصور عمدًا في الأمثلة الصغيرة جدًا ولا يدخل في الحساب النهائي.