Let \(g(n)\) denote the number of distinct \(n\times n\) binary grids in which every row and every column contains exactly two black cells, where two grids are considered the same if one can be obtained from the other by a symmetry of the square.
Equivalently, we count orbits of \(n\times n\) \(0\)-\(1\) matrices with row sums and column sums equal to \(2\) under the dihedral group \(D_4\).
The required value is
$$g(7^7)+g(8^8)\pmod{10^9+7}.$$
The solution never enumerates grids directly. It uses Burnside's lemma, then computes the number of colorings fixed by each symmetry type with short recurrences coming from generating functions.
There are eight symmetries of the square: the identity, one half-turn, two quarter-turns, two axial reflections, and two diagonal reflections. If we write
$$I_n=\mathrm{Fix}(\text{identity}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{vertical reflection}),\qquad D_n=\mathrm{Fix}(\text{main diagonal reflection}),$$
then the paired symmetries have equal fixed counts, so Burnside gives
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
The whole problem is therefore reduced to evaluating five fixed-point formulas.
For the identity symmetry, a grid is simply an \(n\times n\) binary matrix with row sum \(2\) and column sum \(2\). Interpreting rows and columns as the two parts of a bipartite graph, every valid grid corresponds to a simple \(2\)-regular bipartite graph on \(n+n\) labeled vertices.
Every connected component of such a graph is an alternating cycle of length \(2k\) with \(k\ge 2\). On chosen sets of \(k\) row labels and \(k\) column labels, the number of alternating cycles is \(k!^2/(2k)\), so the labeled-set construction yields the ordinary generating function
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$$
Differentiating gives
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)},$$
hence the coefficients satisfy
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0.$$
The actual number of fixed grids is then
$$\boxed{I_n=(n!)^2U_n.}$$
A coloring fixed by a diagonal reflection corresponds to a symmetric \(0\)-\(1\) matrix with row sum \(2\). The connected components can be described on the label set \(\{1,\dots,n\}\):
ordinary cycles of length at least \(3\), and path components whose two endpoints carry diagonal entries, so each endpoint already contributes one black cell and the path supplies the second one. A path on \(k\) labeled vertices contributes \(k!/2\), while a cycle on \(k\) labeled vertices contributes \((k-1)!/2\).
Therefore
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$$
From the resulting differential equation one gets the recurrence
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$$
with initial values
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3}.$$
The diagonal fixed count is
$$\boxed{D_n=n!S_n.}$$
The other diagonal has the same count, so Burnside needs this term only once and doubles it.
For a half-turn, opposite rows and opposite columns are paired. When \(n=2m\) is even, the quotient has \(m\) row-pairs and \(m\) column-pairs. A connected component is either a doubled edge on one row-pair and one column-pair, or an alternating cycle on \(k\ge 2\) row-pairs and \(k\) column-pairs; each step has two local orientations, producing a factor \(4^k\).
This gives
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2},$$
so
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$$
and the even half-turn count is
$$\boxed{T_{2m}=(m!)^2E_m.}$$
When \(n=2m+1\) is odd, there is also a central row and a central column, forcing one distinguished open chain in the quotient. If \(O_m\) counts that case, then adding one more paired row and one more paired column either extends the distinguished chain in \(4\) ways or creates a terminal attachment in \(2\) ways. Therefore
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$$
and
$$\boxed{T_{2m+1}=(m!)^2O_m.}$$
For a quarter-turn, no odd grid can be fixed, so only \(n=2m\) matters. After quotienting by the rotation, the connected pieces form a signed cycle class with a forbidden size-\(2\) component, which gives
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
Hence
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$$
with
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1,$$
and the quarter-turn contribution is
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$$
A vertical or horizontal reflection is possible only for even \(n=2m\). In each row, the two black cells must occupy a mirror pair of columns, so each row chooses one of the \(m\) column-pairs. Since every column must contain exactly two black cells, every column-pair must be chosen by exactly two rows.
That is exactly the number of ways to partition the \(2m\) rows into \(m\) unordered pairs and assign those pairs to the \(m\) column-pairs, namely
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
Here \(n=4=2\cdot 2\), so all five symmetry types contribute.
For the identity, the recurrence gives
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$$
hence
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
For the diagonal reflection, the recurrence gives \(S_4=3/4\), so
$$D_4=4!\cdot \frac{3}{4}=18.$$
For the half-turn, \(E_2=9/2\), so
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
For the quarter-turn, \(Q_2=1\), so
$$R_4=2!\cdot 1=2.$$
For axial reflections,
$$V_4=\frac{4!}{2^2}=6.$$
Burnside then gives
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$$
which matches the small check used by the implementation.
The C++, Python, and Java implementations all follow the same pipeline. They first precompute modular inverses up to \(n+1\), because every recurrence divides by \(n+1\) or \(m+1\) inside arithmetic modulo \(10^9+7\).
Next they scan factorials to obtain \(n!\) and \(\lfloor n/2\rfloor!\). Then they evaluate the identity, diagonal, half-turn, and quarter-turn recurrences using constant-sized rolling state, and they compute the axial reflection term from the closed formula \((2m)!/2^m\).
Finally they assemble
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
by multiplying with the modular inverse of \(8\). No grid, graph, orbit table, or search tree is built explicitly; only the recurrence states and the inverse table are needed. The implementation evaluates \(g(7^7)\) and \(g(8^8)\) separately and adds them modulo \(10^9+7\).
Each symmetry contribution is computed by a single linear pass up to \(n\) or \(\lfloor n/2\rfloor\). Therefore the total running time is \(O(n)\). The modular-inverse table has size \(O(n)\), while the recurrence states use only \(O(1)\) extra space, so the total memory usage is \(O(n)\).
Sei \(g(n)\) die Anzahl verschiedener \(n\times n\)-Binärgitter, in denen jede Zeile und jede Spalte genau zwei schwarze Felder enthält, wobei zwei Gitter als gleich gelten, wenn sie durch eine Symmetrie des Quadrats ineinander überführt werden können.
Äquivalent zählt man also Bahnen von \(n\times n\)-\(0\)-\(1\)-Matrizen mit Zeilen- und Spaltensumme \(2\) unter der Diedergruppe \(D_4\).
Gesucht ist
$$g(7^7)+g(8^8)\pmod{10^9+7}.$$
Die Lösung zählt keine Gitter direkt. Stattdessen wird Burnside angewendet, und jede Fixpunktzahl wird über kurze Rekurrenzen aus erzeugenden Funktionen berechnet.
Das Quadrat besitzt acht Symmetrien: die Identität, eine Halbrotation, zwei Vierteldrehungen, zwei Achsenspiegelungen und zwei Diagonalspiegelungen. Mit
$$I_n=\mathrm{Fix}(\text{Identität}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{Achsenspiegelung}),\qquad D_n=\mathrm{Fix}(\text{Diagonalspiegelung})$$
und wegen gleicher Beiträge gepaarter Symmetrien gilt
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
Damit müssen nur fünf Fixpunktzahlen bestimmt werden.
Unter der Identität ist ein Gitter einfach eine \(n\times n\)-Matrix mit Zeilen- und Spaltensumme \(2\). Interpretiert man Zeilen und Spalten als die zwei Klassen eines bipartiten Graphen, so entspricht jedes gültige Gitter einem einfachen \(2\)-regulären bipartiten Graphen auf \(n+n\) markierten Ecken.
Jede Zusammenhangskomponente ist ein alternierender Zyklus der Länge \(2k\) mit \(k\ge 2\). Auf vorgegebenen Mengen von \(k\) Zeilen- und \(k\) Spaltenmarken gibt es \(k!^2/(2k)\) solche Zyklen. Daher ist die erzeugende Funktion
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$$
Aus
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)}$$
folgt die Rekurrenz
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0,$$
und damit
$$\boxed{I_n=(n!)^2U_n.}$$
Eine Färbung, die unter einer Diagonalspiegelung invariant ist, entspricht einer symmetrischen \(0\)-\(1\)-Matrix mit Zeilensumme \(2\). Auf der Markenmenge \(\{1,\dots,n\}\) entstehen zwei Komponententypen:
gewöhnliche Zyklen der Länge mindestens \(3\) und Pfade, deren beide Endpunkte auf der Diagonale liegen. An jedem Endpunkt liefert der Diagonaleintrag bereits eine schwarze Zelle, der Pfad liefert die zweite.
Ein Pfad auf \(k\) markierten Ecken trägt \(k!/2\) bei, ein Zyklus auf \(k\) markierten Ecken \((k-1)!/2\). Also
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$$
Daraus folgt
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$$
mit
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3},$$
und somit
$$\boxed{D_n=n!S_n.}$$
Die andere Diagonale liefert dieselbe Zahl und wird in Burnside deshalb einfach mit Faktor \(2\) berücksichtigt.
Bei einer Halbrotation werden gegenüberliegende Zeilen und Spalten gepaart. Für gerades \(n=2m\) besitzt der Quotient \(m\) Zeilenpaare und \(m\) Spaltenpaare. Zusammenhangskomponenten sind entweder doppelte Kanten oder alternierende Zyklen auf \(k\ge 2\) Zeilen- und Spaltenpaaren; jede lokale Kante hat zwei Orientierungen, also entsteht der Faktor \(4^k\).
Damit erhält man
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2},$$
also
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$$
und
$$\boxed{T_{2m}=(m!)^2E_m.}$$
Für ungerades \(n=2m+1\) bleiben zusätzlich eine zentrale Zeile und eine zentrale Spalte übrig. Dadurch entsteht im Quotienten genau eine ausgezeichnete offene Kette. Bezeichnet \(O_m\) diese Fälle, so gilt
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$$
und damit
$$\boxed{T_{2m+1}=(m!)^2O_m.}$$
Für die Vierteldrehung kann nur gerades \(n=2m\) Beiträge liefern. Nach dem Quotienten unter der Rotation entsteht eine signierte Zyklusklasse mit ausgeschlossener Größe \(2\):
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
Daraus folgt
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$$
mit
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1,$$
und somit
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$$
Eine vertikale oder horizontale Spiegelung ist nur für gerades \(n=2m\) möglich. In jeder Zeile müssen die beiden schwarzen Felder ein Spiegelpaar von Spalten bilden; jede Zeile wählt also eines der \(m\) Spaltenpaare. Weil jede Spalte insgesamt genau zwei schwarze Felder haben muss, wird jedes Spaltenpaar von genau zwei Zeilen gewählt.
Das ist genau die Anzahl, die \(2m\) Zeilen in \(m\) ungeordnete Paare zu zerlegen und diesen die \(m\) Spaltenpaare zuzuordnen:
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
Hier ist \(n=4=2\cdot 2\), also tragen alle fünf Symmetrietypen bei.
Für die Identität liefert die Rekurrenz
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$$
daher
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
Für die Diagonalspiegelung ist \(S_4=3/4\), also
$$D_4=4!\cdot \frac{3}{4}=18.$$
Für die Halbrotation ist \(E_2=9/2\), also
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
Für die Vierteldrehung gilt \(Q_2=1\), also
$$R_4=2!\cdot 1=2.$$
Und für Achsenspiegelungen
$$V_4=\frac{4!}{2^2}=6.$$
Burnside ergibt damit
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$$
genau den kleinen Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen benutzen denselben Ablauf. Zuerst werden modulare Inversen bis \(n+1\) vorbereitet, denn in allen Rekurrenzen wird innerhalb der Arithmetik modulo \(10^9+7\) durch \(n+1\) oder \(m+1\) dividiert.
Danach werden Fakultäten durchlaufen, um \(n!\) und \(\lfloor n/2\rfloor!\) zu erhalten. Anschließend werden die Rekurrenzen für Identität, Diagonalspiegelung, Halbrotation und Vierteldrehung mit einem Rollfenster aus konstant vielen Zuständen ausgewertet; der Achsenspiegelungsbeitrag kommt direkt aus \((2m)!/2^m\).
Zum Schluss wird
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
über das modulare Inverse von \(8\) zusammengesetzt. Weder Gitter noch Graphen noch Orbits werden explizit erzeugt. Die Implementierung berechnet \(g(7^7)\) und \(g(8^8)\) getrennt und addiert beide Werte modulo \(10^9+7\).
Jeder Symmetriebeitrag wird durch einen einzigen linearen Durchlauf bis \(n\) oder \(\lfloor n/2\rfloor\) berechnet. Die Laufzeit ist daher \(O(n)\). Die Tabelle der modularen Inversen benötigt \(O(n)\) Speicher, während die Rekurrenzzustände selbst nur \(O(1)\) zusätzlichen Platz brauchen. Insgesamt ergibt sich also \(O(n)\) Speicherbedarf.
\(g(n)\), her satırında ve her sütununda tam olarak iki siyah hücre bulunan \(n\times n\) ikili karelerin, karesel simetriler altında birbirinden farklı kaç sınıfa ayrıldığını göstersin.
Başka bir deyişle, satır ve sütun toplamları \(2\) olan \(n\times n\) \(0\)-\(1\) matrislerinin, kare üzerindeki dihedral grup \(D_4\) etkisi altındaki orbitlerini sayıyoruz.
İstenen değer
$$g(7^7)+g(8^8)\pmod{10^9+7}$$
şeklindedir.
Çözüm hiçbir zaman kareleri tek tek üretmez. Burnside lemmasıyla orbit sayısını sabit nokta sayılarına ayırır ve her simetri türü için kısa üreteç fonksiyonu reküransları kullanır.
Karenin sekiz simetrisi vardır: özdeşlik, bir adet \(180^\circ\) dönüş, iki adet \(90^\circ\) türü dönüş, iki eksen yansıması ve iki köşegen yansıması. Şunları tanımlayalım:
$$I_n=\mathrm{Fix}(\text{özdeşlik}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{eksen yansıması}),\qquad D_n=\mathrm{Fix}(\text{köşegen yansıması}).$$
Eş türden ikili simetrilerin sabit sayıları aynı olduğundan Burnside formülü
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
Dolayısıyla problem, bu beş katkının kapalı ya da rekürsif biçimde hesaplanmasına dönüşür.
Özdeşlik altında sabit kalmak için ekstra bir koşul yoktur; elimizde yalnızca satır ve sütun toplamı \(2\) olan bir ikili matris vardır. Satırları ve sütunları iki ayrı tepe kümesi gibi düşünürsek, her geçerli kare basit bir \(2\)-düzenli bipartit grafa karşılık gelir.
Böyle bir grafiğin her bağlı bileşeni, uzunluğu \(2k\) olan ve \(k\ge 2\) şartını sağlayan alternatif bir çevrimdir. Seçilmiş \(k\) satır etiketi ve \(k\) sütun etiketi üzerinde bu çevrimlerin sayısı \(k!^2/(2k)\) olur. Böylece üreteç fonksiyonu
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}$$
elde edilir.
Türev alırsak
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)}$$
ve katsayı karşılaştırmasından
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0$$
çıkar. Gerçek sabit kare sayısı da
$$\boxed{I_n=(n!)^2U_n}$$
olur.
Bir köşegen yansıması altında sabit kalan kare, satır toplamı \(2\) olan simetrik bir \(0\)-\(1\) matristir. Etiket kümesi \(\{1,\dots,n\}\) üzerinde iki bileşen türü vardır:
uzunluğu en az \(3\) olan sıradan çevrimler ve uçlarında köşegen hücresi bulunan yollar. Böyle bir yolun iki ucunda köşegen üzerindeki siyah hücre birer katkı yapar; yolun kenarları da her uca ikinci siyah hücreyi tamamlar.
\(k\) etiketli tepe üzerindeki yol sayısı \(k!/2\), çevrim sayısı \((k-1)!/2\) olduğundan
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right)$$
elde edilir.
Bunun verdiği rekürans
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}}$$
ve başlangıç değerleri
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3}$$
şeklindedir. Dolayısıyla
$$\boxed{D_n=n!S_n}$$
olur. Diğer köşegen için sayı aynıdır; Burnside içinde bu yüzden ikiyle çarpılır.
\(180^\circ\) dönüşte karşılıklı satırlar ve sütunlar eşleştirilir. \(n=2m\) çift ise bölüm yapısında \(m\) satır çifti ve \(m\) sütun çifti vardır. Bağlı bileşen ya tek bir çift satır ile tek bir çift sütun arasındaki çift kenardır ya da \(k\ge 2\) için alternatif bir çevrimdir; her yerel adımda iki yön seçeneği bulunduğundan \(4^k\) katsayısı gelir.
Böylece
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2}$$
ve dolayısıyla
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1$$
elde edilir. Çift durumdaki sabit sayı
$$\boxed{T_{2m}=(m!)^2E_m}$$
olur.
\(n=2m+1\) tek olduğunda ortada bir satır ve bir sütun da kalır; bölüm yapısında tek bir ayırt edilmiş açık zincir oluşur. Bu durumu \(O_m\) saysın. Yeni bir satır çifti ve sütun çifti eklenince ya bu zincir \(4\) farklı biçimde uzar ya da \(2\) farklı uç bağlantısı yapılır. Bu yüzden
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0$$
ve
$$\boxed{T_{2m+1}=(m!)^2O_m}$$
olur.
\(90^\circ\) dönüşte yalnızca çift \(n=2m\) mümkündür. Dönüşe göre bölüm alındığında, işaretli çevrimlerden oluşan ve boyutu \(2\) olan yasaklı kısa bileşeni çıkartılmış bir sınıf elde edilir:
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
Buradan
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}}$$
ve
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1$$
gelir. Sonuç olarak
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0}$$
elde edilir.
Dikey ya da yatay yansıma yalnızca çift \(n=2m\) için mümkündür. Her satırda iki siyah hücre birbirinin aynadaki eşi olan iki sütunda bulunmak zorundadır; yani her satır \(m\) sütun çiftinden birini seçer. Her sütunda toplam tam iki siyah hücre istenildiği için her sütun çifti tam olarak iki satır tarafından seçilmelidir.
Bu da \(2m\) satırı \(m\) adet sırasız çifte ayırıp bu çiftleri \(m\) sütun çiftine atama sayısıdır:
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
Burada \(n=4=2\cdot 2\) olduğundan beş simetri katkısının tamamı vardır.
Özdeşlik için rekürans
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32}$$
verir. Dolayısıyla
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
Köşegen yansıması için \(S_4=3/4\), yani
$$D_4=4!\cdot \frac{3}{4}=18.$$
\(180^\circ\) dönüş için \(E_2=9/2\), yani
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
\(90^\circ\) dönüş için \(Q_2=1\), yani
$$R_4=2!\cdot 1=2.$$
Eksen yansımalarında
$$V_4=\frac{4!}{2^2}=6$$
olur. Burnside formülüyle
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20$$
elde edilir; bu, uygulamanın kullandığı küçük doğrulama değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı işlem sırasını izler. Önce \(n+1\) değerine kadar modüler tersler hazırlanır; çünkü reküranslarda mod \(10^9+7\) altında \(n+1\) ya da \(m+1\) ile bölme vardır.
Daha sonra faktöriyel taramasıyla \(n!\) ve \(\lfloor n/2\rfloor!\) elde edilir. Kimlik, köşegen, yarım dönüş ve çeyrek dönüş katkıları sabit boyutlu kayan durumlarla hesaplanır; eksen yansıması katkısı ise doğrudan \((2m)!/2^m\) formülünden gelir.
Son adımda
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
ifadesi, \(8\)'in modüler tersi kullanılarak birleştirilir. Uygulama açıkça kare üretmez, orbit tablosu kurmaz ve arama yapmaz. \(g(7^7)\) ile \(g(8^8)\) ayrı ayrı hesaplanıp mod altında toplanır.
Her simetri katkısı \(n\) ya da \(\lfloor n/2\rfloor\) seviyesine kadar tek bir doğrusal geçişle hesaplanır. Bu yüzden zaman karmaşıklığı \(O(n)\) olur. Modüler ters tablosu \(O(n)\) bellek kullanır; rekürans durumları ise yalnızca \(O(1)\) ek alan ister. Toplam bellek karmaşıklığı da \(O(n)\)'dir.
Sea \(g(n)\) el número de rejillas binarias \(n\times n\) distintas en las que cada fila y cada columna contiene exactamente dos celdas negras, considerando equivalentes dos rejillas si una se obtiene de la otra mediante una simetría del cuadrado.
De forma equivalente, contamos órbitas de matrices \(0\)-\(1\) de tamaño \(n\times n\) con suma \(2\) en cada fila y en cada columna bajo la acción del grupo diedral \(D_4\).
La cantidad pedida es
$$g(7^7)+g(8^8)\pmod{10^9+7}.$$
La solución no genera rejillas una por una. Usa el lema de Burnside y calcula los conteos fijos de cada tipo de simetría mediante recurrencias lineales obtenidas de funciones generadoras.
El cuadrado tiene ocho simetrías: la identidad, una media vuelta, dos cuartos de vuelta, dos reflexiones axiales y dos reflexiones diagonales. Definimos
$$I_n=\mathrm{Fix}(\text{identidad}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{reflexión axial}),\qquad D_n=\mathrm{Fix}(\text{reflexión diagonal}).$$
Como las simetrías emparejadas tienen el mismo número de puntos fijos, Burnside da
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
Así, todo el problema se convierte en hallar cinco contribuciones fijas.
Bajo la identidad, una rejilla válida es simplemente una matriz binaria con suma \(2\) en cada fila y en cada columna. Si interpretamos las filas y las columnas como las dos partes de un grafo bipartito, cada matriz válida corresponde a un grafo bipartito simple \(2\)-regular con \(n+n\) vértices etiquetados.
Toda componente conexa de ese grafo es un ciclo alternante de longitud \(2k\) con \(k\ge 2\). Sobre conjuntos elegidos de \(k\) filas y \(k\) columnas, el número de esos ciclos es \(k!^2/(2k)\). Por tanto, la función generadora es
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$$
Derivando obtenemos
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)},$$
de donde sale la recurrencia
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0,$$
y el número fijo real es
$$\boxed{I_n=(n!)^2U_n.}$$
Una coloración fija por una reflexión diagonal corresponde a una matriz simétrica \(0\)-\(1\) con suma \(2\) en cada fila. Sobre el conjunto de etiquetas \(\{1,\dots,n\}\) aparecen dos tipos de componentes:
ciclos ordinarios de longitud al menos \(3\), y caminos cuyos dos extremos están en la diagonal. Cada extremo ya aporta una celda negra diagonal, y el camino aporta la segunda celda negra necesaria.
Un camino sobre \(k\) vértices etiquetados aporta \(k!/2\), mientras que un ciclo sobre \(k\) vértices etiquetados aporta \((k-1)!/2\). Entonces
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$$
La ecuación diferencial asociada conduce a
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$$
con valores iniciales
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3},$$
y por tanto
$$\boxed{D_n=n!S_n.}$$
La otra diagonal tiene el mismo conteo, así que Burnside la incorpora multiplicando por \(2\).
Para una media vuelta, las filas opuestas y las columnas opuestas se agrupan por parejas. Si \(n=2m\) es par, el cociente tiene \(m\) pares de filas y \(m\) pares de columnas. Una componente conexa es o bien una arista doble entre un par de filas y un par de columnas, o bien un ciclo alternante sobre \(k\ge 2\) pares de filas y \(k\) pares de columnas. Cada paso local tiene dos orientaciones, lo que produce el factor \(4^k\).
Por ello
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2},$$
y la recurrencia es
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$$
de modo que
$$\boxed{T_{2m}=(m!)^2E_m.}$$
Si \(n=2m+1\) es impar, también existe una fila central y una columna central. Eso obliga a una única cadena abierta distinguida en el cociente. Si \(O_m\) cuenta ese caso, entonces al añadir un nuevo par de filas y un nuevo par de columnas la cadena se puede prolongar de \(4\) maneras o se puede crear un acoplamiento terminal de \(2\) maneras. Por tanto
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$$
y
$$\boxed{T_{2m+1}=(m!)^2O_m.}$$
Para un cuarto de vuelta solo pueden contribuir tamaños pares \(n=2m\). Tras tomar el cociente rotacional aparece una clase de ciclos con signo y con el componente corto de tamaño \(2\) excluido:
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
De aquí sale
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$$
con
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1,$$
y en consecuencia
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$$
Una reflexión vertical u horizontal solo es posible si \(n=2m\) es par. En cada fila, las dos celdas negras deben ocupar una pareja de columnas simétrica respecto del eje, así que cada fila elige una de las \(m\) parejas de columnas. Como cada columna debe contener exactamente dos celdas negras, cada pareja de columnas debe ser elegida por exactamente dos filas.
Eso equivale a particionar las \(2m\) filas en \(m\) pares no ordenados y asignar esos pares a las \(m\) parejas de columnas. Por tanto,
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
Aquí \(n=4=2\cdot 2\), así que contribuyen los cinco tipos de simetría.
Para la identidad, la recurrencia produce
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$$
luego
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
Para la reflexión diagonal, \(S_4=3/4\), así que
$$D_4=4!\cdot \frac{3}{4}=18.$$
Para la media vuelta, \(E_2=9/2\), por tanto
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
Para el cuarto de vuelta, \(Q_2=1\), de modo que
$$R_4=2!\cdot 1=2.$$
Para las reflexiones axiales,
$$V_4=\frac{4!}{2^2}=6.$$
Burnside da entonces
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$$
que coincide con la comprobación pequeña usada por la implementación.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero precalculan inversos modulares hasta \(n+1\), porque todas las recurrencias dividen por \(n+1\) o por \(m+1\) dentro de la aritmética módulo \(10^9+7\).
Después recorren factoriales para obtener \(n!\) y \(\lfloor n/2\rfloor!\). Luego evalúan las recurrencias de identidad, diagonal, media vuelta y cuarto de vuelta con un estado rodante de tamaño constante, y calculan la reflexión axial con la fórmula cerrada \((2m)!/2^m\).
Finalmente combinan
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
multiplicando por el inverso modular de \(8\). Nunca se construye explícitamente ninguna rejilla ni ninguna órbita. La implementación evalúa \(g(7^7)\) y \(g(8^8)\) por separado y suma ambos valores módulo \(10^9+7\).
Cada contribución de simetría se calcula con un único recorrido lineal hasta \(n\) o \(\lfloor n/2\rfloor\). Por ello, el tiempo total es \(O(n)\). La tabla de inversos modulares ocupa \(O(n)\) memoria y los estados de las recurrencias usan solo \(O(1)\) espacio adicional, así que la memoria total es \(O(n)\).
设 \(g(n)\) 表示这样的 \(n\times n\) 二元方格在正方形对称意义下的不同方案数：每一行恰好有两个黑格，每一列也恰好有两个黑格，并且如果两个方格能通过正方形的某个旋转或翻折互相得到，就把它们视为同一种方案。
等价地说，我们是在计数所有行和列的和都等于 \(2\) 的 \(n\times n\) \(0\)-\(1\) 矩阵，在二面体群 \(D_4\) 作用下的轨道数。
题目要求计算
$$g(7^7)+g(8^8)\pmod{10^9+7}.$$
核心思想不是直接枚举网格，而是先用 Burnside 引理把轨道计数改写成若干固定点计数，再用生成函数推出线性递推。这样每一种对称类型都只需要一趟线性计算。
正方形一共有 \(8\) 个对称：恒等变换、一次 \(180^\circ\) 旋转、两次 \(90^\circ\) 型旋转、两次轴反射、两次对角线反射。记
$$I_n=\mathrm{Fix}(\text{恒等}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{轴反射}),\qquad D_n=\mathrm{Fix}(\text{对角线反射}).$$
由于成对出现的两种轴反射固定点数相同，两种对角线反射也相同，两种四分之一转的固定点数同样相同，所以 Burnside 直接给出
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
因此真正需要做的，是分别求出这五类固定点计数。
在恒等变换下，固定的对象就是原问题本身：一个行和列和都等于 \(2\) 的二元矩阵。把“行”与“列”看成二分图的左右两个顶点集，黑格 \((i,j)\) 就对应于一条连接第 \(i\) 行和第 \(j\) 列的边。
因为每一行和每一列都恰好有两个黑格，所以对应图中左右两侧每个顶点的度都等于 \(2\)。又因为矩阵元素只能是 \(0\) 或 \(1\)，所以这是一张简单的 \(2\)-正则二分图。
这样的连通分量只能是长度为 \(2k\) 的交替偶环，其中 \(k\ge 2\)。在给定的 \(k\) 个行标号和 \(k\) 个列标号上，交替环的数量是 \(k!^2/(2k)\)。于是得到普通生成函数
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$$
对它求导可得
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)},$$
从而系数满足递推
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0.$$
最后再乘回标号排列的因子，就得到
$$\boxed{I_n=(n!)^2U_n.}$$
若一个方案在主对角线反射下保持不变，那么矩阵必须是对称的，并且每一行仍然有两个黑格。把标号集合写成 \(\{1,\dots,n\}\) 后，连通分量有两类：
一类是长度至少为 \(3\) 的普通环；另一类是“带对角端点的路径”。所谓带对角端点，是指路径两端所在的顶点各自还占据一个对角线上的黑格，因此这两个顶点各自已经拿到了一次贡献，路径上的边再补上第二次贡献。
在 \(k\) 个带标号顶点上，这类路径的数量是 \(k!/2\)，普通环的数量是 \((k-1)!/2\)。因此生成函数为
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$$
由相应微分方程可推出递推
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$$
初值为
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3}.$$
于是主对角线反射的固定点数就是
$$\boxed{D_n=n!S_n.}$$
另一条对角线的固定点数完全相同，所以在 Burnside 公式里统一写成 \(2D_n\)。
对 \(180^\circ\) 旋转来说，相对的行会成对出现，相对的列也会成对出现。若 \(n=2m\) 为偶数，则商结构里有 \(m\) 个行对和 \(m\) 个列对。一个连通分量不是“一个行对与一个列对之间的双边”，就是一个覆盖 \(k\ge 2\) 个行对与 \(k\) 个列对的交替环。由于每一步在还原回原网格时都有两个局部朝向选择，所以大小为 \(k\) 的环会带来 \(4^k\) 的权重。
因此得到
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2}.$$
对应递推为
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$$
所以偶数情形的半转固定点数为
$$\boxed{T_{2m}=(m!)^2E_m.}$$
若 \(n=2m+1\) 为奇数，还会额外出现一条中心行和一条中心列。这会在商结构中强制产生一条带区分的开放链。设对应计数为 \(O_m\)，那么再加入一个新的行对和列对时，要么以 \(4\) 种方式延长这条开放链，要么以 \(2\) 种方式接上一段末端结构，因此有
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$$
从而
$$\boxed{T_{2m+1}=(m!)^2O_m.}$$
对 \(90^\circ\) 旋转来说，只有偶数边长 \(n=2m\) 才可能有固定点。把旋转商掉以后，会得到一个“带符号的环类”，其中大小为 \(2\) 的短分量必须排除。于是生成函数为
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
因此
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$$
并取
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1.$$
最终四分之一转的贡献是
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$$
纵向或横向反射只有在 \(n=2m\) 为偶数时才可能保持方案不变。每一行中的两个黑格必须位于一对关于反射轴对称的列里，因此每一行等价于从 \(m\) 个列对中选一个。与此同时，每一列总共必须出现恰好两个黑格，所以每一对列必须被恰好两行选中。
这正好等价于：把 \(2m\) 行拆成 \(m\) 个无序的行对，再把这些行对分配给 \(m\) 个列对。因此
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
这里 \(n=4=2\cdot 2\)，所以五类对称都要计入。
恒等情形下，递推给出
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$$
于是
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
对角线反射下 \(S_4=3/4\)，所以
$$D_4=4!\cdot \frac{3}{4}=18.$$
半转下 \(E_2=9/2\)，因此
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
四分之一转下 \(Q_2=1\)，因此
$$R_4=2!\cdot 1=2.$$
轴反射下
$$V_4=\frac{4!}{2^2}=6.$$
代回 Burnside 公式得到
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$$
这与实现中使用的小规模校验值一致。
C++、Python 和 Java 实现遵循完全相同的流程。首先预计算到 \(n+1\) 为止的模逆元，因为所有递推都要在模 \(10^9+7\) 的意义下除以 \(n+1\) 或 \(m+1\)。
接着顺次计算阶乘，从而得到 \(n!\) 和 \(\lfloor n/2\rfloor!\)。之后用常数大小的滚动状态分别推进恒等、对角线、半转和四分之一转的递推，而轴反射项直接使用闭式 \((2m)!/2^m\)。
最后把
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
用 \(8\) 的模逆元合并起来。整个实现不显式构造任何网格、图、轨道表或搜索树，只保留逆元表和少量递推状态。程序分别计算 \(g(7^7)\) 与 \(g(8^8)\)，再在模 \(10^9+7\) 下相加。
每一种对称贡献都只需要做到 \(n\) 或 \(\lfloor n/2\rfloor\) 的一次线性扫描，所以总时间复杂度是 \(O(n)\)。模逆元表占用 \(O(n)\) 空间，而递推本身只用 \(O(1)\) 额外状态，因此总空间复杂度也是 \(O(n)\)。
Пусть \(g(n)\) обозначает число различных бинарных таблиц \(n\times n\), в которых в каждой строке и в каждом столбце ровно две чёрные клетки, причём две таблицы считаются одинаковыми, если одна получается из другой симметрией квадрата.
Иначе говоря, мы считаем орбиты \(n\times n\) матриц \(0\)-\(1\) с суммой \(2\) в каждой строке и каждом столбце относительно диэдральной группы \(D_4\).
Требуется найти
$$g(7^7)+g(8^8)\pmod{10^9+7}.$$
Прямого перебора таблиц нет. Используется лемма Бёрнсайда: число орбит выражается через количества конфигураций, неподвижных относительно разных симметрий, а эти количества вычисляются по линейным рекуррентным формулам, выведенным из производящих функций.
У квадрата \(8\) симметрий: тождественная, поворот на \(180^\circ\), два поворота на \(90^\circ\), две осевые симметрии и две диагональные симметрии. Обозначим
$$I_n=\mathrm{Fix}(\text{тождественная}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{осевая симметрия}),\qquad D_n=\mathrm{Fix}(\text{диагональная симметрия}).$$
Парные типы симметрий дают одинаковые числа неподвижных конфигураций, поэтому по Бёрнсайду
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
Значит, достаточно вычислить пять фиксированных вкладов.
При тождественной симметрии фиксированная таблица - это просто бинарная матрица с суммой \(2\) в каждой строке и в каждом столбце. Если строки и столбцы считать двумя долями двудольного графа, то чёрная клетка задаёт ребро между соответствующими вершинами.
Поскольку в каждой строке и каждом столбце ровно две единицы, получается простой \(2\)-регулярный двудольный граф на \(n+n\) помеченных вершинах. Каждая его связная компонента - это чередующийся цикл длины \(2k\), где \(k\ge 2\).
На выбранных \(k\) метках строк и \(k\) метках столбцов число таких циклов равно \(k!^2/(2k)\). Поэтому
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$$
Тогда
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)},$$
и коэффициенты удовлетворяют рекурсии
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0.$$
Само число фиксированных таблиц равно
$$\boxed{I_n=(n!)^2U_n.}$$
Конфигурация, неподвижная относительно диагонального отражения, соответствует симметричной \(0\)-\(1\) матрице с суммой \(2\) в каждой строке. На множестве меток \(\{1,\dots,n\}\) возникают два типа компонент:
обычные циклы длины не меньше \(3\) и пути, у которых оба конца лежат на диагонали. В таком пути диагональные клетки уже дают по одной чёрной клетке на концах, а рёбра пути обеспечивают вторые чёрные клетки.
Путь на \(k\) помеченных вершинах даёт вклад \(k!/2\), цикл на \(k\) вершинах - \((k-1)!/2\). Следовательно,
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$$
Из соответствующего дифференциального уравнения получается
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$$
при начальных значениях
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3}.$$
Поэтому
$$\boxed{D_n=n!S_n.}$$
Для другой диагонали счёт тот же, поэтому в формуле Бёрнсайда он удваивается.
Для поворота на \(180^\circ\) противоположные строки и столбцы объединяются в пары. Если \(n=2m\) чётно, то в факторе остаётся \(m\) пар строк и \(m\) пар столбцов. Связная компонента либо является двойным ребром между одной парой строк и одной парой столбцов, либо представляет собой чередующийся цикл на \(k\ge 2\) парах строк и \(k\) парах столбцов. На каждом локальном шаге есть две ориентации, что даёт множитель \(4^k\).
Получаем
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2},$$
следовательно,
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$$
и для чётного случая
$$\boxed{T_{2m}=(m!)^2E_m.}$$
Если \(n=2m+1\) нечётно, то остаются ещё центральная строка и центральный столбец. Они заставляют появиться одну выделенную открытую цепочку в факторе. Если её считает \(O_m\), то при добавлении новой пары строк и пары столбцов цепочка либо продолжается \(4\) способами, либо присоединяется терминальный блок \(2\) способами. Поэтому
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$$
и
$$\boxed{T_{2m+1}=(m!)^2O_m.}$$
Для поворота на \(90^\circ\) возможны только чётные размеры \(n=2m\). После факторизации по вращению получается класс знаковых циклов, из которого исключена запрещённая компонента размера \(2\):
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
Отсюда следует
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$$
при
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1,$$
и потому
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$$
Вертикальное или горизонтальное отражение возможно только при чётном \(n=2m\). В каждой строке две чёрные клетки должны образовывать зеркальную пару столбцов, то есть каждая строка выбирает одну из \(m\) пар столбцов. Так как в каждом столбце должно быть ровно две чёрные клетки, каждая пара столбцов должна быть выбрана ровно двумя строками.
Это в точности число способов разбить \(2m\) строк на \(m\) неупорядоченных пар и сопоставить эти пары \(m\) парам столбцов:
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
Здесь \(n=4=2\cdot 2\), поэтому участвуют все пять типов симметрий.
Для тождественной симметрии рекурсия даёт
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$$
значит
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
Для диагонального отражения \(S_4=3/4\), поэтому
$$D_4=4!\cdot \frac{3}{4}=18.$$
Для поворота на \(180^\circ\) имеем \(E_2=9/2\), значит
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
Для поворота на \(90^\circ\) имеем \(Q_2=1\), значит
$$R_4=2!\cdot 1=2.$$
Для осевых отражений
$$V_4=\frac{4!}{2^2}=6.$$
Теперь по Бёрнсайду
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$$
что совпадает с малой проверкой, используемой реализацией.
Реализации на C++, Python и Java устроены одинаково. Сначала они предвычисляют модульные обратные до \(n+1\), потому что во всех рекурсиях приходится делить на \(n+1\) или \(m+1\) в арифметике по модулю \(10^9+7\).
Затем они одним проходом считают факториалы, чтобы получить \(n!\) и \(\lfloor n/2\rfloor!\). После этого рекурсии для тождественной симметрии, диагонального отражения, полуповорота и четверть-поворота вычисляются на скользящем состоянии постоянного размера, а осевой вклад берётся из явной формулы \((2m)!/2^m\).
В конце собирается
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
с помощью модульного обратного к \(8\). Никакие таблицы клеток, графы или орбиты явно не строятся. Реализация отдельно вычисляет \(g(7^7)\) и \(g(8^8)\), после чего складывает результаты по модулю \(10^9+7\).
Каждый вклад симметрии считается одним линейным проходом до \(n\) или \(\lfloor n/2\rfloor\), поэтому общее время равно \(O(n)\). Таблица модульных обратных требует \(O(n)\) памяти, а состояния рекурсий занимают лишь \(O(1)\) дополнительного места, так что суммарная память равна \(O(n)\).
لتكن \(g(n)\) هي عدد الشبكات الثنائية \(n\times n\) المختلفة التي تحتوي في كل صف وفي كل عمود على خليتين سوداوين بالضبط، مع اعتبار شبكتين متماثلتين إذا أمكن الحصول على إحداهما من الأخرى بواسطة تناظر من تناظرات المربع.
وبصورة مكافئة نحن نعد مدارات مصفوفات \(0\)-\(1\) ذات المقاس \(n\times n\) التي يكون مجموع كل صف وكل عمود فيها مساويا لـ \(2\)، وذلك تحت تأثير الزمرة الثنائية السطوح \(D_4\).
القيمة المطلوبة هي
$$g(7^7)+g(8^8)\pmod{10^9+7}.$$
الحل لا يولد الشبكات مباشرة. بدلا من ذلك يستخدم لمّة Burnside لتحويل عدّ المدارات إلى عدّ الحالات الثابتة تحت كل نوع من أنواع التناظر، ثم يحسب هذه القيم بعلاقات عودية خطية مشتقة من دوال مولدة.
للمربع ثمانية تناظرات: الهوية، دوران بزاوية \(180^\circ\)، دورانان من نوع \(90^\circ\)، انعكاسان محوريان، وانعكاسان قطريان. نكتب
$$I_n=\mathrm{Fix}(\text{identity}),\qquad T_n=\mathrm{Fix}(180^\circ),\qquad R_n=\mathrm{Fix}(90^\circ),$$
$$V_n=\mathrm{Fix}(\text{axis reflection}),\qquad D_n=\mathrm{Fix}(\text{diagonal reflection}).$$
ولأن التناظرات المتناظرة في كل زوج تعطي العدد نفسه من التثبيتات، نحصل من Burnside على
$$\boxed{g(n)=\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}.}$$
إذن المطلوب فعليا هو حساب هذه المساهمات الخمس.
عند الهوية لا يوجد شرط إضافي؛ فالتلوين الثابت هو مجرد مصفوفة ثنائية يكون مجموع كل صف وكل عمود فيها مساويا لـ \(2\). إذا اعتبرنا الصفوف والاعمدة جزأين من رسم ثنائي، فإن كل خلية سوداء تمثل ضلعا بين صف وعمود.
وبما أن كل صف وكل عمود لهما بالضبط خليتان سوداوين، فإننا نحصل على رسم ثنائي بسيط منتظم من الدرجة \(2\) على \(n+n\) رأسا معلمة. كل مركبة متصلة في هذا الرسم لا بد أن تكون دورة متناوبة طولها \(2k\) حيث \(k\ge 2\).
وعلى مجموعة مختارة من \(k\) صفوف و\(k\) أعمدة يكون عدد هذه الدورات هو \(k!^2/(2k)\). لذلك تكون الدالة المولدة
$$U(x)=\sum_{n\ge 0} U_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2k}\right)=e^{-x/2}(1-x)^{-1/2}.$$
ومن ثم
$$\frac{U'(x)}{U(x)}=\frac{x}{2(1-x)},$$
فنحصل على العلاقة العودية
$$\boxed{(n+1)U_{n+1}=nU_n+\frac{1}{2}U_{n-1}},\qquad U_0=1,\ U_1=0.$$
وبعد إعادة عامل التوسيم نحصل على
$$\boxed{I_n=(n!)^2U_n.}$$
إذا كان التلوين ثابتا تحت انعكاس قطري، فإن المصفوفة تكون متناظرة ومجموع كل صف فيها يساوي \(2\). على مجموعة الفهارس \(\{1,\dots,n\}\) تظهر مركبتان أساسيتان:
دورات عادية طولها على الأقل \(3\)، ومسارات يكون طرفاها على القطر. كل طرف من هذين الطرفين يملك خلية سوداء قطرية بالفعل، بينما تضيف أضلاع المسار الخلية السوداء الثانية اللازمة لذلك الصف.
عدد المسارات على \(k\) رؤوس معلمة هو \(k!/2\)، وعدد الدورات على \(k\) رؤوس معلمة هو \((k-1)!/2\). لذلك
$$S(x)=\sum_{n\ge 0} S_n x^n=\exp\left(\sum_{k\ge 2}\frac{x^k}{2}+\sum_{k\ge 3}\frac{x^k}{2k}\right).$$
ومنها تنتج العلاقة
$$\boxed{(n+1)S_{n+1}=2nS_n-(n-2)S_{n-1}-\frac{1}{2}S_{n-3}},$$
مع القيم الابتدائية
$$S_0=1,\qquad S_1=0,\qquad S_2=\frac{1}{2},\qquad S_3=\frac{2}{3}.$$
وعليه فإن
$$\boxed{D_n=n!S_n.}$$
والقطر الآخر يعطي العدد نفسه، ولهذا يضرب هذا الحد في \(2\) داخل صيغة Burnside.
في دوران \(180^\circ\) تتزاوج الصفوف المتقابلة وكذلك الأعمدة المتقابلة. إذا كان \(n=2m\) زوجيا، فإن بنية القسمة تحتوي على \(m\) أزواج من الصفوف و\(m\) أزواج من الأعمدة. المركبة المتصلة تكون إما ضلعا مزدوجا بين زوج صفوف وزوج أعمدة، أو دورة متناوبة على \(k\ge 2\) من أزواج الصفوف و\(k\) من أزواج الأعمدة. ولكل خطوة محلية اختياران في الاتجاه، لذلك يظهر العامل \(4^k\).
ومن هنا نحصل على
$$E(x)=\sum_{m\ge 0} E_m x^m=\exp\left(x+\sum_{k\ge 2}\frac{4^k x^k}{2k}\right)=e^{-x}(1-4x)^{-1/2}.$$
إذن
$$\boxed{(m+1)E_{m+1}=(4m+1)E_m+4E_{m-1}},\qquad E_0=1,\ E_1=1,$$
وفي الحالة الزوجية يكون عدد التثبيتات
$$\boxed{T_{2m}=(m!)^2E_m.}$$
أما إذا كان \(n=2m+1\) فرديا، فتبقى أيضا سطر مركزي وعمود مركزي، وهذا يفرض سلسلة مفتوحة مميزة داخل بنية القسمة. إذا رمزنا لعدد هذه الحالات بـ \(O_m\)، فإن إضافة زوج صفوف جديد وزوج أعمدة جديد إما تمد السلسلة المميزة بعدد \(4\) من الطرق أو تضيف وصلة طرفية بعدد \(2\) من الطرق. لذلك
$$\boxed{O_m=4O_{m-1}+2E_{m-1}},\qquad O_0=0,$$
ومن ثم
$$\boxed{T_{2m+1}=(m!)^2O_m.}$$
بالنسبة إلى دوران \(90^\circ\)، لا توجد حالات ثابتة إلا عندما يكون \(n=2m\) زوجيا. بعد أخذ القسمة بالنسبة إلى الدوران نحصل على فئة من الدورات الموقعة مع استبعاد المركبة القصيرة ذات الحجم \(2\):
$$Q(x)=\sum_{m\ge 0} Q_m x^m=\exp\left(\sum_{k\ge 1}\frac{2^{k-1}x^k}{k}-\frac{x^2}{2}\right)=e^{-x^2/2}(1-2x)^{-1/2}.$$
ومنها
$$\boxed{(m+1)Q_{m+1}=(2m+1)Q_m-Q_{m-1}+2Q_{m-2}},$$
مع
$$Q_{-2}=0,\qquad Q_{-1}=0,\qquad Q_0=1,$$
فتكون مساهمة هذا الدوران
$$\boxed{R_{2m}=m!Q_m,\qquad R_{2m+1}=0.}$$
الانعكاس العمودي أو الأفقي لا يمكن أن يثبت تلوينا إلا إذا كان \(n=2m\) زوجيا. ففي كل صف يجب أن تقع الخليتان السوداوان في زوج من الأعمدة المتناظرة حول المحور، أي إن كل صف يختار واحدا من \(m\) أزواج الأعمدة. وبما أن كل عمود يجب أن يحتوي بالضبط على خليتين سوداوين، فلا بد أن يختار كل زوج من الأعمدة صفين بالضبط.
وهذا يساوي عدد طرق تقسيم الصفوف \(2m\) إلى \(m\) أزواج غير مرتبة ثم إسناد هذه الأزواج إلى أزواج الأعمدة:
$$\boxed{V_{2m}=\frac{(2m)!}{2^m},\qquad V_{2m+1}=0.}$$
هنا \(n=4=2\cdot 2\)، ولذلك تساهم الأنواع الخمسة كلها.
في حالة الهوية تعطي العلاقة
$$U_2=\frac{1}{4},\qquad U_3=\frac{1}{6},\qquad U_4=\frac{5}{32},$$
ومن ثم
$$I_4=(4!)^2\cdot \frac{5}{32}=90.$$
وفي الانعكاس القطري لدينا \(S_4=3/4\)، لذلك
$$D_4=4!\cdot \frac{3}{4}=18.$$
وفي دوران \(180^\circ\) نحصل على \(E_2=9/2\)، ومنه
$$T_4=(2!)^2\cdot \frac{9}{2}=18.$$
وفي دوران \(90^\circ\) يكون \(Q_2=1\)، ومنه
$$R_4=2!\cdot 1=2.$$
أما في الانعكاسات المحورية فلدينا
$$V_4=\frac{4!}{2^2}=6.$$
وبتطبيق Burnside نحصل على
$$g(4)=\frac{90+18+2\cdot 2+2\cdot 6+2\cdot 18}{8}=\frac{160}{8}=20,$$
وهو نفس المثال الصغير الذي تتحقق منه التطبيقات.
تنفذ تطبيقات C++ وPython وJava الخطوات نفسها. أولا تحسب المقلوبات المعيارية حتى \(n+1\)، لأن كل العلاقات العودية تتضمن قسمة على \(n+1\) أو \(m+1\) داخل الحسابات بترديد \(10^9+7\).
بعد ذلك تمر على المضروبات للحصول على \(n!\) و\(\lfloor n/2\rfloor!\). ثم تحسب عوديات الهوية والانعكاس القطري ونص الدوران وربع الدوران باستخدام حالة منزلقة ذات حجم ثابت، بينما تحسب مساهمة الانعكاس المحوري مباشرة من الصيغة \((2m)!/2^m\).
وفي النهاية تجمع
$$\frac{I_n+T_n+2R_n+2V_n+2D_n}{8}\pmod{10^9+7}$$
عن طريق الضرب في المقلوب المعياري للعدد \(8\). لا يتم إنشاء أي شبكة أو رسم أو جدول مدارات صراحة. ثم تحسب الشيفرة \(g(7^7)\) و\(g(8^8)\) كل على حدة وتجمع الناتجين بترديد \(10^9+7\).
كل مساهمة تناظرية تحسب بمرور خطي واحد حتى \(n\) أو \(\lfloor n/2\rfloor\)، ولذلك يكون الزمن الكلي \(O(n)\). جدول المقلوبات المعيارية يحتاج إلى \(O(n)\) من الذاكرة، بينما تحتاج حالات العوديات نفسها إلى \(O(1)\) فقط من المساحة الإضافية. إذن التعقيد المكاني الكلي هو \(O(n)\).