Consider an \(m\times n\) rectangular grid of unit squares. Each cell may be braced by a diagonal, and \(R(m,n)\) denotes the number of brace selections that make the whole framework rigid. The final target is
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
The implementations do not attack rigidity directly as a geometric problem. Instead, they use the standard combinatorial model in which rigidity becomes a connectivity question in a bipartite graph.
Create one vertex for each horizontal strip of cells and one vertex for each vertical strip of cells. Thus an \(m\times n\) grid gives a bipartite graph with row vertices \(u_1,\dots,u_m\) and column vertices \(v_1,\dots,v_n\).
The cell in row \(a\) and column \(b\) corresponds to the possible edge \(u_a v_b\). Choosing a set of braces is therefore equivalent to choosing a spanning subgraph of the complete bipartite graph \(K_{m,n}\).
The key fact used by the solver is:
$$\text{the braced framework is rigid} \iff \text{the associated bipartite graph is connected}.$$
So \(R(m,n)\) is exactly the number of connected spanning subgraphs of \(K_{m,n}\).
There are \(mn\) possible row-column edges, and each edge is either present or absent. Therefore the total number of subgraphs is
$$2^{mn}.$$
To get \(R(m,n)\), we subtract the disconnected subgraphs.
Fix the distinguished row vertex \(u_1\). In a disconnected graph, the connected component containing \(u_1\) uses some number \(i\) of row vertices and some number \(j\) of column vertices, where
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
For such a component:
$$\binom{m-1}{i-1}$$
chooses the other row vertices that join \(u_1\),
$$\binom{n}{j}$$
chooses the participating column vertices,
$$R(i,j)$$
counts the connected bipartite graph inside that component, and
$$2^{(m-i)(n-j)}$$
counts the arbitrary edges among the remaining rows and remaining columns. No edge is allowed between the chosen component and the remaining vertices, otherwise the component containing \(u_1\) would be larger.
Summing this contribution over all proper pairs \((i,j)\) gives the total number of disconnected graphs.
Subtracting those disconnected cases from \(2^{mn}\) yields the split recurrence actually evaluated by the implementations, with \(M=1{,}000{,}000{,}033\):
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
The second sum is simply the case \(i=m\), where the factor \(2^{(m-i)(n-j)}\) becomes \(1\).
The boundary values are also important. A graph with one row vertex and no column vertices is connected, so
$$R(1,0)=1.$$
For \(m>1\), a graph with no column vertices cannot be connected, so \(R(m,0)=0\). From the recurrence one also gets \(R(1,n)=1\) for every \(n\ge 1\): with only one row vertex, all \(n\) column vertices must attach to it.
For \(R(2,2)\), start from all \(2^4=16\) subgraphs. The component containing the first row can have size \((1,0)\), \((1,1)\), or \((1,2)\), giving
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9.$$
The case \(i=2\) but \(j<2\) contributes
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2=2.$$
Therefore
$$R(2,2)=16-9-2=5.$$
For \(R(2,3)\), the same recurrence gives
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27,$$
and the \(i=2,\ j<3\) part equals
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18.$$
Hence
$$R(2,3)=2^6-27-18=64-45=19.$$
These small values are useful sanity checks for the table.
The C++, Python, and Java implementations precompute two ingredients modulo \(M\): all binomial coefficients \(\binom{a}{b}\) for \(0\le a,b\le 100\), and all powers \(2^e\) for \(0\le e\le 100^2\). After that they fill a table of \(R(m,n)\) in increasing order of \(m\) and \(n\).
For a fixed \(m\), the contribution of all terms with smaller row count \(i<m\) is accumulated first for every \(n\). Then, for each \(n\), the contribution with the same row count but smaller column count \(j<n\) is subtracted. What remains is exactly \(R(m,n)\).
The C++ implementation optionally parallelizes the accumulation over the smaller row counts, while the Python and Java implementations evaluate the same recurrence directly with ordinary nested loops. Once the table is complete, the final answer is the double sum of all \(R(m,n)\) with \(1\le m,n\le N\).
Let the final bound be \(N\). Building Pascal's triangle and the powers of two each costs \(O(N^2)\) time. The dynamic-programming table is dominated by the triple summation over \(m\), the smaller row size \(i\), and the inner column index \(j\), which yields overall \(O(N^4)\) time. The table of values, binomial coefficients, and power table together use \(O(N^2)\) memory.
For the required case \(N=100\), this is entirely practical.
Gegeben ist ein \(m\times n\)-Rechteckgitter aus Einheitsquadraten. Jede Zelle kann durch eine Diagonale versteift werden, und \(R(m,n)\) bezeichnet die Anzahl der Versteifungsmuster, die das gesamte System starr machen. Gesucht ist
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
Die Implementierungen behandeln Starrheit nicht direkt geometrisch, sondern benutzen das äquivalente kombinatorische Modell, in dem Starrheit zu einer Zusammenhangsfrage in einem bipartiten Graphen wird.
Wir führen für jeden horizontalen Zellstreifen einen Zeilenknoten und für jeden vertikalen Zellstreifen einen Spaltenknoten ein. Ein \(m\times n\)-Gitter liefert also einen bipartiten Graphen mit Zeilenknoten \(u_1,\dots,u_m\) und Spaltenknoten \(v_1,\dots,v_n\).
Die Zelle in Zeile \(a\) und Spalte \(b\) entspricht der möglichen Kante \(u_a v_b\). Eine Auswahl von Versteifungen ist damit genau ein aufspannender Teilgraph von \(K_{m,n}\).
Die zentrale Tatsache des Lösers lautet:
$$\text{Das versteifte Gitter ist starr} \iff \text{der zugehörige bipartite Graph ist zusammenhängend}.$$
Also ist \(R(m,n)\) genau die Anzahl zusammenhängender aufspannender Teilgraphen von \(K_{m,n}\).
Es gibt \(mn\) mögliche Zeilen-Spalten-Kanten, und jede ist entweder vorhanden oder nicht vorhanden. Daher ist die Gesamtzahl aller Teilgraphen
$$2^{mn}.$$
Um \(R(m,n)\) zu erhalten, subtrahieren wir die nicht zusammenhängenden Fälle.
Fixiere den ausgezeichneten Zeilenknoten \(u_1\). In einem nicht zusammenhängenden Graphen enthält die Zusammenhangskomponente von \(u_1\) genau \(i\) Zeilenknoten und \(j\) Spaltenknoten mit
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
Für eine solche Komponente gilt:
$$\binom{m-1}{i-1}$$
wählt die weiteren Zeilenknoten,
$$\binom{n}{j}$$
wählt die beteiligten Spaltenknoten,
$$R(i,j)$$
zählt den zusammenhängenden Teilgraphen innerhalb der Komponente, und
$$2^{(m-i)(n-j)}$$
zählt die beliebigen Kanten unter den verbleibenden Zeilen und Spalten. Kanten zwischen der gewählten Komponente und den übrigen Knoten sind verboten, sonst wäre die Komponente von \(u_1\) größer.
Summiert man diesen Beitrag über alle echten Paare \((i,j)\), erhält man die Gesamtzahl der nicht zusammenhängenden Graphen.
Durch Subtraktion dieser nicht zusammenhängenden Fälle von \(2^{mn}\) erhält man die gesplittete Rekursion, die die Implementierungen direkt auswerten; dabei ist \(M=1{,}000{,}000{,}033\):
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
Die zweite Summe ist genau der Fall \(i=m\), bei dem der Faktor \(2^{(m-i)(n-j)}\) zu \(1\) wird.
Wichtig sind auch die Randwerte. Ein Graph mit genau einem Zeilenknoten und ohne Spaltenknoten ist zusammenhängend, also
$$R(1,0)=1.$$
Für \(m>1\) kann ein Graph ohne Spaltenknoten nicht zusammenhängend sein, also \(R(m,0)=0\). Aus der Rekursion folgt außerdem \(R(1,n)=1\) für jedes \(n\ge 1\): Bei nur einer Zeile müssen alle Spalten an dieser einen Zeile hängen.
Für \(R(2,2)\) startet man mit allen \(2^4=16\) Teilgraphen. Die Komponente der ersten Zeile kann die Größe \((1,0)\), \((1,1)\) oder \((1,2)\) haben. Das ergibt
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9.$$
Der Anteil mit \(i=2\), aber \(j<2\), ist
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2=2.$$
Also
$$R(2,2)=16-9-2=5.$$
Für \(R(2,3)\) liefert dieselbe Rekursion
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27,$$
und der Teil mit \(i=2,\ j<3\) ist
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18.$$
Damit folgt
$$R(2,3)=2^6-27-18=64-45=19.$$
Solche kleinen Werte sind gute Plausibilitätsprüfungen für die Tabelle.
Die Implementierungen in C++, Python und Java berechnen zunächst modulo \(M\) alle Binomialkoeffizienten \(\binom{a}{b}\) für \(0\le a,b\le 100\) sowie alle Zweierpotenzen \(2^e\) für \(0\le e\le 100^2\). Danach wird die Tabelle der Werte \(R(m,n)\) in wachsender Reihenfolge von \(m\) und \(n\) gefüllt.
Für ein festes \(m\) wird zuerst der gesamte Beitrag aller kleineren Zeilenzahlen \(i<m\) für jedes \(n\) akkumuliert. Anschließend wird für jedes \(n\) noch der Anteil mit derselben Zeilenzahl, aber kleineren Spaltenzahlen \(j<n\), abgezogen. Der verbleibende Rest ist genau \(R(m,n)\).
Die C++-Implementierung kann die Akkumulation über die kleineren Zeilenzahlen parallel ausführen; die Python- und Java-Implementierungen werten dieselbe Rekursion direkt mit gewöhnlichen Schleifen aus. Ist die Tabelle fertig, wird zum Schluss über alle \(R(m,n)\) mit \(1\le m,n\le N\) summiert.
Sei \(N\) die obere Grenze. Pascalsches Dreieck und Zweierpotenzen kosten jeweils \(O(N^2)\) Zeit. Die dynamische Programmierung wird von den verschachtelten Summen über \(m\), die kleinere Zeilenzahl \(i\) und den inneren Spaltenindex \(j\) dominiert und benötigt insgesamt \(O(N^4)\) Zeit. Die Tabellen für DP-Werte, Binomialkoeffizienten und Zweierpotenzen verbrauchen zusammen \(O(N^2)\) Speicher.
Für den geforderten Fall \(N=100\) ist das gut beherrschbar.
Birim karelerden oluşan \(m\times n\) boyutlu bir dikdörtgen ızgara düşünelim. Her hücreye bir köşegen desteği eklenebilir ve \(R(m,n)\), tüm sistemi rijit yapan destek seçimlerinin sayısını göstersin. İstenen toplam
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
Uygulamalar rijitliği doğrudan geometri üzerinden çözmez. Bunun yerine, rijitliği iki parçalı bir çizgede bağlantılılık koşuluna dönüştüren standart kombinatorik modeli kullanır.
Her yatay hücre şeridi için bir satır düğümü ve her düşey hücre şeridi için bir sütun düğümü oluşturalım. Böylece \(m\times n\) ızgara, satır düğümleri \(u_1,\dots,u_m\) ve sütun düğümleri \(v_1,\dots,v_n\) olan bir iki parçalı çizge verir.
\(a\). satır ve \(b\). sütundaki hücre, olası \(u_a v_b\) kenarına karşılık gelir. Dolayısıyla seçilen destekler, \(K_{m,n}\) tam iki parçalı çizgesinin bir kapsayan alt çizgesi ile bire bir eşleşir.
Çözücünün kullandığı temel gerçek şudur:
$$\text{Desteklenmiş çerçeve rijittir} \iff \text{ilişkili iki parçalı çizge bağlantılıdır}.$$
Bu yüzden \(R(m,n)\), \(K_{m,n}\) üzerindeki bağlantılı kapsayan alt çizgelerin tam sayısıdır.
Toplam \(mn\) adet olası satır-sütun kenarı vardır ve her biri ya seçilir ya da seçilmez. Bu nedenle tüm alt çizgelerin sayısı
$$2^{mn}$$
olur. \(R(m,n)\)'yi bulmak için bağlantısız olanları çıkarırız.
Ayırt edilmiş satır düğümü olarak \(u_1\)'i sabitleyelim. Bağlantısız bir çizgede, \(u_1\)'i içeren bağlı bileşen tam olarak \(i\) satır düğümü ve \(j\) sütun düğümü içerir; burada
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
Böyle bir bileşen için:
$$\binom{m-1}{i-1}$$
\(u_1\)'e katılan diğer satır düğümlerini seçer,
$$\binom{n}{j}$$
kullanılan sütun düğümlerini seçer,
$$R(i,j)$$
bileşenin içindeki bağlantılı yapıları sayar ve
$$2^{(m-i)(n-j)}$$
geriye kalan satırlar ile sütunlar arasındaki serbest kenar seçimlerini sayar. Seçilen bileşen ile dışarıda kalan düğümler arasında kenar olamaz; aksi halde \(u_1\)'in bileşeni daha büyük olurdu.
Bu katkı tüm uygun \((i,j)\) çiftleri üzerinde toplandığında toplam bağlantısız çizge sayısı elde edilir.
Bu bağlantısız durumlar \(2^{mn}\)'den çıkarılınca, uygulamaların doğrudan kullandığı bölünmüş özyineleme elde edilir; burada \(M=1{,}000{,}000{,}033\):
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
İkinci toplam, \(i=m\) durumudur; bu durumda \(2^{(m-i)(n-j)}=1\) olur.
Sınır değerleri de önemlidir. Tek bir satır düğümü ve hiç sütun düğümü içeren çizge bağlantılı kabul edilir; dolayısıyla
$$R(1,0)=1.$$
\(m>1\) iken sütun düğümü olmayan bir çizge bağlantılı olamaz, yani \(R(m,0)=0\). Aynı özyineleme \(n\ge 1\) için \(R(1,n)=1\) sonucunu da verir: tek satır varsa bütün sütunlar ona bağlanmak zorundadır.
\(R(2,2)\) için toplam \(2^4=16\) alt çizge vardır. İlk satırı içeren bileşenin boyutu \((1,0)\), \((1,1)\) veya \((1,2)\) olabilir. Bu katkı
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9$$
eder. \(i=2\) fakat \(j<2\) olan durumların katkısı ise
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2$$
olur. Sonuç:
$$R(2,2)=16-9-2=5.$$
\(R(2,3)\) için aynı yöntem
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27$$
ve
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18$$
verir. Böylece
$$R(2,3)=2^6-27-18=64-45=19.$$
Bu küçük değerler tablo hesabını doğrulamak için çok faydalıdır.
C++, Python ve Java uygulamaları önce \(M\) modunda iki tablo üretir: \(0\le a,b\le 100\) için tüm \(\binom{a}{b}\) değerleri ve \(0\le e\le 100^2\) için tüm \(2^e\) değerleri. Ardından \(R(m,n)\) tablosu artan \(m\) ve \(n\) sırasıyla doldurulur.
Sabit bir \(m\) için, önce daha küçük satır sayılarından \(i<m\) gelen tüm katkılar her \(n\) değeri için biriktirilir. Sonra her \(n\) için aynı satır sayısına sahip ama daha küçük sütun sayılarından \(j<n\) gelen kısım çıkarılır. Geriye kalan değer tam olarak \(R(m,n)\)'dir.
C++ uygulaması bu biriktirme adımını isteğe bağlı olarak paralel yürütebilir; Python ve Java uygulamaları aynı bağıntıyı doğrudan iç içe döngülerle hesaplar. Tablo tamamlandıktan sonra son cevap, \(1\le m,n\le N\) için tüm \(R(m,n)\) değerlerinin çift toplamıdır.
Üst sınır \(N\) olsun. Pascal üçgeni ve ikinin kuvvetleri tabloları ayrı ayrı \(O(N^2)\) zamanda üretilir. Asıl dinamik programlama, \(m\), daha küçük satır boyutu \(i\) ve içteki sütun indeksi \(j\) üzerindeki toplamlar tarafından belirlenir ve toplamda \(O(N^4)\) zaman alır. DP tablosu, binom katsayıları ve kuvvet tablosu birlikte \(O(N^2)\) bellek kullanır.
İstenen \(N=100\) durumu için bu maliyet rahattır.
Se considera una rejilla rectangular de \(m\times n\) cuadrados unitarios. Cada celda puede reforzarse con una diagonal, y \(R(m,n)\) denota el número de selecciones de refuerzos que vuelven rígida toda la estructura. El objetivo final es
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
Las implementaciones no resuelven la rigidez directamente como problema geométrico. En su lugar usan el modelo combinatorio estándar en el que la rigidez se transforma en una cuestión de conectividad dentro de un grafo bipartito.
Se crea un vértice para cada banda horizontal de celdas y otro para cada banda vertical. Así, una rejilla \(m\times n\) produce un grafo bipartito con vértices de fila \(u_1,\dots,u_m\) y vértices de columna \(v_1,\dots,v_n\).
La celda situada en la fila \(a\) y la columna \(b\) corresponde a la arista posible \(u_a v_b\). Por tanto, elegir refuerzos equivale a elegir un subgrafo generador de \(K_{m,n}\).
El hecho clave usado por el algoritmo es:
$$\text{la rejilla reforzada es rígida} \iff \text{el grafo bipartito asociado es conexo}.$$
Por consiguiente, \(R(m,n)\) es exactamente el número de subgrafos generadores conexos de \(K_{m,n}\).
Hay \(mn\) aristas posibles entre filas y columnas, y cada una puede estar presente o ausente. Luego el número total de subgrafos es
$$2^{mn}.$$
Para obtener \(R(m,n)\), restamos los subgrafos no conexos.
Fijemos el vértice de fila distinguido \(u_1\). En un grafo no conexo, la componente conexa que contiene a \(u_1\) usa \(i\) vértices de fila y \(j\) vértices de columna, con
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
Para una componente de ese tipo:
$$\binom{m-1}{i-1}$$
elige las otras filas que acompañan a \(u_1\),
$$\binom{n}{j}$$
elige las columnas de la componente,
$$R(i,j)$$
cuenta el subgrafo bipartito conexo dentro de esa componente, y
$$2^{(m-i)(n-j)}$$
cuenta las aristas arbitrarias entre las filas restantes y las columnas restantes. No puede haber aristas entre la componente elegida y los vértices externos, porque entonces la componente de \(u_1\) sería mayor.
Al sumar esta contribución sobre todos los pares propios \((i,j)\), se obtiene el número total de subgrafos no conexos.
Al restar esos casos no conexos de \(2^{mn}\), aparece la recurrencia separada que evalúan directamente las implementaciones; aquí \(M=1{,}000{,}000{,}033\):
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
La segunda suma no es más que el caso \(i=m\), donde el factor \(2^{(m-i)(n-j)}\) vale \(1\).
También importan las condiciones iniciales. Un grafo con un único vértice de fila y ningún vértice de columna es conexo, por lo que
$$R(1,0)=1.$$
Si \(m>1\), un grafo sin vértices de columna no puede ser conexo, así que \(R(m,0)=0\). Además, la misma recurrencia implica \(R(1,n)=1\) para todo \(n\ge 1\): con una sola fila, todas las columnas deben unirse a ella.
Para \(R(2,2)\), partimos de \(2^4=16\) subgrafos. La componente que contiene a la primera fila puede tener tamaño \((1,0)\), \((1,1)\) o \((1,2)\), lo que produce
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9.$$
La parte con \(i=2\) pero \(j<2\) vale
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2.$$
Por tanto,
$$R(2,2)=16-9-2=5.$$
Para \(R(2,3)\), la misma idea da
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27,$$
y la contribución con \(i=2,\ j<3\) es
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18.$$
En consecuencia,
$$R(2,3)=2^6-27-18=64-45=19.$$
Estos valores pequeños sirven como comprobaciones muy útiles.
Las implementaciones en C++, Python y Java precalculan dos tablas módulo \(M\): todos los coeficientes binomiales \(\binom{a}{b}\) con \(0\le a,b\le 100\), y todas las potencias \(2^e\) con \(0\le e\le 100^2\). Después rellenan la tabla de \(R(m,n)\) en orden creciente de \(m\) y \(n\).
Para un \(m\) fijo, primero se acumulan, para cada \(n\), todas las contribuciones con \(i<m\). Luego, para cada \(n\), se resta la parte con el mismo número de filas pero con \(j<n\). El valor restante es exactamente \(R(m,n)\).
La implementación en C++ puede paralelizar la acumulación sobre los tamaños de fila menores; las versiones en Python y Java evalúan la misma recurrencia con bucles anidados ordinarios. Al final, la respuesta buscada es la suma doble de todos los \(R(m,n)\) con \(1\le m,n\le N\).
Sea \(N\) el límite superior. Construir el triángulo de Pascal y la tabla de potencias de dos cuesta \(O(N^2)\) tiempo en cada caso. La programación dinámica está dominada por las sumas anidadas sobre \(m\), el tamaño de fila menor \(i\) y el índice interior \(j\), lo que lleva a \(O(N^4)\) tiempo total. La tabla DP, los binomiales y las potencias ocupan conjuntamente \(O(N^2)\) memoria.
Para \(N=100\), este coste es perfectamente razonable.
考虑一个由单位正方形组成的 \(m\times n\) 矩形网格。每个小方格都可以加入一条对角支撑，记 \(R(m,n)\) 为能使整个框架变得刚性的支撑方案数。最终要求计算
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
实现并不是直接从几何刚性出发求解，而是采用一个标准的组合模型，把刚性问题转化成二分图的连通性计数问题。
对每一条水平单元带建立一个“行顶点”，对每一条垂直单元带建立一个“列顶点”。于是 \(m\times n\) 网格对应一个二分图，其两侧分别是 \(u_1,\dots,u_m\) 与 \(v_1,\dots,v_n\)。
第 \(a\) 行第 \(b\) 列的方格对应一条可能出现的边 \(u_a v_b\)。因此，选择哪些方格加支撑，等价于在完全二分图 \(K_{m,n}\) 中选择一个生成子图。
求解程序依赖的关键事实是：
$$\text{加固后的框架刚性成立} \iff \text{对应的二分图连通}.$$
所以 \(R(m,n)\) 恰好等于 \(K_{m,n}\) 的连通生成子图个数。
总共有 \(mn\) 条可能的行列边，每条边都可以“选”或“不选”，因此全部子图数量为
$$2^{mn}.$$
接下来只需减去其中不连通的部分。
固定第一个行顶点 \(u_1\)。若图不连通，那么包含 \(u_1\) 的连通块会包含 \(i\) 个行顶点和 \(j\) 个列顶点，其中
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
对这样的一个连通块：
$$\binom{m-1}{i-1}$$
用于从剩余行顶点中选出并入该连通块的 \(i-1\) 个，
$$\binom{n}{j}$$
用于选择这 \(j\) 个列顶点，
$$R(i,j)$$
用于统计该连通块内部的连通二分图数目，而
$$2^{(m-i)(n-j)}$$
表示其余行顶点与其余列顶点之间的边可以任意选择。连通块与外部顶点之间不能有边，否则包含 \(u_1\) 的连通块会更大。
把这一贡献对所有真子情况 \((i,j)\) 求和，就得到不连通子图的总数。
把这些不连通情况从 \(2^{mn}\) 中减去，就得到实现真正计算的拆分递推式，其中 \(M=1{,}000{,}000{,}033\)：
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
第二项就是 \(i=m\) 的情形，因为此时 \(2^{(m-i)(n-j)}=1\)。
边界条件同样重要。只有一个行顶点且没有列顶点时，图仍然是连通的，所以
$$R(1,0)=1.$$
当 \(m>1\) 时，如果没有列顶点，图不可能连通，因此 \(R(m,0)=0\)。由递推还可以推出 \(R(1,n)=1\)（\(n\ge 1\)）：因为只有一个行顶点时，所有列顶点都必须连到它上面。
先看 \(R(2,2)\)。总共有 \(2^4=16\) 个子图。包含第一行的连通块可能是 \((1,0)\)、\((1,1)\) 或 \((1,2)\)，其贡献为
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9.$$
再加上 \(i=2\) 但 \(j<2\) 的部分：
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2.$$
所以
$$R(2,2)=16-9-2=5.$$
再看 \(R(2,3)\)。同样有
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27,$$
而 \(i=2,\ j<3\) 的贡献是
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18.$$
于是
$$R(2,3)=2^6-27-18=64-45=19.$$
这些小结果非常适合作为递推表的校验值。
C++、Python 和 Java 实现都会先在模 \(M\) 下预处理两类数据：一类是所有 \(0\le a,b\le 100\) 的二项式系数 \(\binom{a}{b}\)，另一类是所有 \(0\le e\le 100^2\) 的 \(2^e\)。然后按 \(m\)、\(n\) 递增的顺序填充 \(R(m,n)\) 表。
对固定的 \(m\)，程序先把所有较小行数 \(i<m\) 的贡献按每个 \(n\) 累加出来；随后再对每个 \(n\) 减去同一行数 \(m\) 但更小列数 \(j<n\) 的贡献。剩下的值就是 \(R(m,n)\)。
C++ 实现还可以把“较小行数的累加”这一步并行化；Python 和 Java 则用普通的嵌套循环直接计算同一递推。整张表完成后，再把所有 \(1\le m,n\le N\) 的 \(R(m,n)\) 累加，就得到最终的 \(S(N)\)。
设上界为 \(N\)。预处理帕斯卡三角和二的幂表各需要 \(O(N^2)\) 时间。主动态规划由关于 \(m\)、较小行规模 \(i\) 以及内部列指标 \(j\) 的嵌套求和主导，总时间复杂度为 \(O(N^4)\)。DP 表、二项式系数表以及幂表合起来占用 \(O(N^2)\) 空间。
对于题目要求的 \(N=100\)，这一复杂度完全可行。
Рассматривается прямоугольная решётка из единичных квадратов размера \(m\times n\). В каждую клетку можно добавить диагональную распорку, а \(R(m,n)\) обозначает число таких выборов, при которых вся конструкция становится жёсткой. Требуется вычислить
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
Реализации не работают с геометрической жёсткостью напрямую. Вместо этого используется стандартная комбинаторная модель, где условие жёсткости превращается в условие связности некоторого двудольного графа.
Вводим по одной вершине для каждой горизонтальной полосы клеток и по одной вершине для каждой вертикальной полосы. Тогда решётке \(m\times n\) соответствует двудольный граф с вершинами строк \(u_1,\dots,u_m\) и вершинами столбцов \(v_1,\dots,v_n\).
Клетка в строке \(a\) и столбце \(b\) соответствует возможному ребру \(u_a v_b\). Значит, выбор распорок эквивалентен выбору порождающего подграфа полного двудольного графа \(K_{m,n}\).
Ключевой факт, на котором основан алгоритм:
$$\text{подкреплённая решётка жёсткая} \iff \text{соответствующий двудольный граф связен}.$$
Следовательно, \(R(m,n)\) есть в точности число связных порождающих подграфов графа \(K_{m,n}\).
Всего имеется \(mn\) возможных рёбер между строками и столбцами, и каждое ребро либо присутствует, либо отсутствует. Поэтому число всех подграфов равно
$$2^{mn}.$$
Чтобы получить \(R(m,n)\), нужно вычесть несвязные графы.
Зафиксируем выделенную вершину строки \(u_1\). В несвязном графе компонента связности, содержащая \(u_1\), использует \(i\) строковых вершин и \(j\) вершин столбцов, где
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
Для такой компоненты:
$$\binom{m-1}{i-1}$$
выбирает остальные строковые вершины этой компоненты,
$$\binom{n}{j}$$
выбирает участвующие вершины столбцов,
$$R(i,j)$$
считает связный двудольный граф внутри компоненты, а
$$2^{(m-i)(n-j)}$$
считает произвольные рёбра между оставшимися строками и оставшимися столбцами. Рёбер между выбранной компонентой и внешними вершинами быть не может, иначе компонента с \(u_1\) стала бы больше.
Если просуммировать этот вклад по всем собственным парам \((i,j)\), получится общее число несвязных графов.
Если вычесть эти несвязные случаи из \(2^{mn}\), получится раздельная рекуррентная формула, которую и считают реализации; здесь \(M=1{,}000{,}000{,}033\):
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
Вторая сумма соответствует случаю \(i=m\), когда множитель \(2^{(m-i)(n-j)}\) равен \(1\).
Важны и граничные значения. Граф с одной строковой вершиной и без вершин столбцов считается связным, поэтому
$$R(1,0)=1.$$
Если \(m>1\), то при отсутствии столбцовых вершин граф связным быть не может, значит \(R(m,0)=0\). Из той же рекурсии следует и \(R(1,n)=1\) для всех \(n\ge 1\): при единственной строке все столбцы обязаны быть соединены с ней.
Для \(R(2,2)\) всего имеется \(2^4=16\) подграфов. Компонента, содержащая первую строку, может иметь размеры \((1,0)\), \((1,1)\) или \((1,2)\), и её вклад равен
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9.$$
Часть с \(i=2\), но \(j<2\), даёт
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2.$$
Следовательно,
$$R(2,2)=16-9-2=5.$$
Для \(R(2,3)\) та же схема даёт
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27,$$
а вклад части \(i=2,\ j<3\) равен
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18.$$
Отсюда
$$R(2,3)=2^6-27-18=64-45=19.$$
Такие малые значения удобно использовать как контроль корректности.
Реализации на C++, Python и Java заранее строят две таблицы по модулю \(M\): все биномиальные коэффициенты \(\binom{a}{b}\) для \(0\le a,b\le 100\) и все степени \(2^e\) для \(0\le e\le 100^2\). После этого таблица \(R(m,n)\) заполняется в порядке возрастания \(m\) и \(n\).
Для фиксированного \(m\) сначала накапливается вклад всех состояний с меньшим числом строк \(i<m\) для каждого \(n\). Затем для каждого \(n\) вычитается часть с тем же числом строк, но с меньшим числом столбцов \(j<n\). Оставшееся значение и есть \(R(m,n)\).
В версии на C++ накопление по меньшим размерам строк может выполняться параллельно; версии на Python и Java считают ту же формулу обычными вложенными циклами. Когда таблица готова, остаётся просуммировать все \(R(m,n)\) при \(1\le m,n\le N\).
Пусть верхняя граница равна \(N\). Построение треугольника Паскаля и таблицы степеней двойки требует по \(O(N^2)\) времени. Основная динамика определяется вложенными суммами по \(m\), меньшему размеру строки \(i\) и внутреннему индексу \(j\), что даёт общую сложность \(O(N^4)\). Таблица DP, биномиальные коэффициенты и степени двойки вместе требуют \(O(N^2)\) памяти.
Для случая \(N=100\) такая схема вполне эффективна.
لدينا شبكة مستطيلة من مربعات وحدة بحجم \(m\times n\). يمكن تدعيم كل خلية بقطر، ولتكن \(R(m,n)\) هي عدد اختيارات التدعيم التي تجعل الهيكل كله صلبًا. المطلوب في النهاية هو حساب
$$S(N)=\sum_{m=1}^{N}\sum_{n=1}^{N} R(m,n)\pmod{1{,}000{,}000{,}033}.$$
التنفيذات لا تعالج الصلابة مباشرة بصياغة هندسية، بل تستخدم نموذجًا توافقيًا قياسيًا يحول شرط الصلابة إلى شرط اتصال في رسم بياني ثنائي القسم.
ننشئ رأسًا لكل شريط أفقي من الخلايا ورأسًا لكل شريط عمودي. لذلك فإن شبكة \(m\times n\) تعطي رسمًا ثنائي القسم له رؤوس صفوف \(u_1,\dots,u_m\) ورؤوس أعمدة \(v_1,\dots,v_n\).
الخلية الواقعة في الصف \(a\) والعمود \(b\) تقابل الحافة الممكنة \(u_a v_b\). ومن ثم فإن اختيار الدعامات يكافئ اختيار رسم فرعي مولد للرسم الكامل ثنائي القسم \(K_{m,n}\).
والحقيقة الأساسية التي يعتمد عليها الحل هي أن الإطار المدعم يكون صلبًا إذا وفقط إذا كان الرسم البياني الثنائي الموافق متصلًا.
إذًا \(R(m,n)\) هو بالضبط عدد الرسوم الفرعية المولدة المتصلة للرسم \(K_{m,n}\).
هناك \(mn\) حافة ممكنة بين الصفوف والأعمدة، وكل حافة إما موجودة أو غير موجودة. لذلك فإن العدد الكلي للرسوم الفرعية هو
$$2^{mn}.$$
ولكي نحصل على \(R(m,n)\)، نطرح الرسوم غير المتصلة.
لنثبت رأس الصف المميز \(u_1\). في رسم غير متصل، فإن المكوّن المتصل الذي يحتوي \(u_1\) يضم \(i\) من رؤوس الصفوف و\(j\) من رؤوس الأعمدة، حيث
$$1\le i\le m,\qquad 0\le j\le n,\qquad (i,j)\ne(m,n).$$
لهذا المكوّن:
$$\binom{m-1}{i-1}$$
يختار بقية رؤوس الصفوف التي تنضم إلى \(u_1\)، و
$$\binom{n}{j}$$
يختار رؤوس الأعمدة الداخلة في هذا المكوّن، و
$$R(i,j)$$
يعد الرسوم الثنائية المتصلة داخل هذا المكوّن، بينما
$$2^{(m-i)(n-j)}$$
يعد جميع الاختيارات الحرة للحواف بين الصفوف الباقية والأعمدة الباقية. ولا يسمح بوجود حواف بين هذا المكوّن والرؤوس الخارجية، وإلا لأصبح المكوّن الذي يحتوي \(u_1\) أكبر.
وعند جمع هذه المساهمة على جميع الأزواج الصحيحة \((i,j)\) نحصل على العدد الكلي للرسوم غير المتصلة.
وعند طرح هذه الحالات غير المتصلة من \(2^{mn}\) نحصل على الصيغة المفصولة التي تحسبها التنفيذات مباشرة، حيث \(M=1{,}000{,}000{,}033\):
$$R(m,n)=2^{mn}-\sum_{i=1}^{m-1}\binom{m-1}{i-1}\sum_{j=0}^{n}\binom{n}{j}R(i,j)2^{(m-i)(n-j)}-\sum_{j=0}^{n-1}\binom{n}{j}R(m,j)\pmod{M}.$$
المجموع الثاني هو ببساطة حالة \(i=m\)، وعندها يصبح العامل \(2^{(m-i)(n-j)}\) مساويًا لـ \(1\).
قيم البداية مهمة أيضًا. الرسم الذي يحتوي رأس صف واحدًا ولا يحتوي أي رأس عمود يكون متصلًا، ولذلك
$$R(1,0)=1.$$
أما إذا كان \(m>1\)، فإن الرسم من دون رؤوس أعمدة لا يمكن أن يكون متصلًا، ولذلك \(R(m,0)=0\). كما تعطي العلاقة نفسها \(R(1,n)=1\) لكل \(n\ge 1\): فعند وجود صف واحد فقط يجب أن تتصل به كل الأعمدة.
في حالة \(R(2,2)\)، يوجد \(2^4=16\) رسمًا فرعيًا ممكنًا. يمكن أن يكون المكوّن الذي يحتوي الصف الأول بالحجم \((1,0)\) أو \((1,1)\) أو \((1,2)\)، وهذا يعطي
$$\binom{1}{0}\left[\binom{2}{0}R(1,0)2^2+\binom{2}{1}R(1,1)2^1+\binom{2}{2}R(1,2)2^0\right]=4+4+1=9.$$
أما الجزء الذي فيه \(i=2\) ولكن \(j<2\) فيساوي
$$\binom{2}{0}R(2,0)+\binom{2}{1}R(2,1)=0+2.$$
ومن ثم
$$R(2,2)=16-9-2=5.$$
وفي حالة \(R(2,3)\)، تعطي العلاقة نفسها
$$\binom{1}{0}\left[\binom{3}{0}R(1,0)2^3+\binom{3}{1}R(1,1)2^2+\binom{3}{2}R(1,2)2^1+\binom{3}{3}R(1,3)2^0\right]=8+12+6+1=27,$$
ويكون الجزء \(i=2,\ j<3\) مساويًا لـ
$$\binom{3}{0}R(2,0)+\binom{3}{1}R(2,1)+\binom{3}{2}R(2,2)=0+3+15=18.$$
إذًا
$$R(2,3)=2^6-27-18=64-45=19.$$
هذه القيم الصغيرة مفيدة جدًا للتحقق من صحة الجدول.
تنفيذات C++ وPython وJava تجهز أولًا جدولين بترديد \(M\): جميع معاملات ثنائية الحد \(\binom{a}{b}\) من أجل \(0\le a,b\le 100\)، وجميع قوى العدد \(2^e\) من أجل \(0\le e\le 100^2\). بعد ذلك تملأ جدول \(R(m,n)\) بترتيب تصاعدي في \(m\) و\(n\).
ولكل \(m\) ثابت، تُجمع أولًا مساهمات جميع الأحجام الأصغر للصفوف \(i<m\) لكل قيمة \(n\). ثم، لكل \(n\)، يُطرح الجزء الذي له نفس عدد الصفوف ولكن بعدد أعمدة أصغر \(j<n\). القيمة المتبقية هي \(R(m,n)\) بالضبط.
تنفيذ C++ يستطيع تنفيذ خطوة التجميع على الأحجام الأصغر للصفوف بصورة متوازية عند الحاجة، بينما تنفذ نسختا Python وJava العلاقة نفسها بحلقات متداخلة مباشرة. وبعد اكتمال الجدول، تُجمع كل القيم \(R(m,n)\) حيث \(1\le m,n\le N\) للحصول على \(S(N)\).
إذا كان الحد الأعلى هو \(N\)، فإن بناء مثلث باسكال وجدول قوى العدد \(2\) يكلف \(O(N^2)\) زمنًا لكل منهما. وتسيطر على البرمجة الديناميكية المجاميع المتداخلة على \(m\) والحجم الأصغر للصفوف \(i\) والمؤشر الداخلي \(j\)، ولذلك يكون الزمن الكلي \(O(N^4)\). أما الذاكرة اللازمة لجدول البرمجة الديناميكية ومعاملات ثنائية الحد وجدول القوى فهي \(O(N^2)\).
وبالنسبة إلى الحالة المطلوبة \(N=100\)، فإن هذا التعقيد عملي تمامًا.