Let \(F_1=F_2=1\). For each integer \(t\) from \(4\) to \(40\), we consider an \(F_{t-1}\times F_t\) array of cells indexed by two periodic coordinates. A symmetry may independently shift or reverse either coordinate, so two colorings are equivalent if one can be transformed into the other by those operations. Only colorings that use all \(t\) colors at least once are valid, and Problem 651 asks for the sum of all such orbit counts modulo \(10^9+7\).
If \(A_q(r,s)\) denotes the number of valid equivalence classes with \(q\) colors and side lengths \(r\) and \(s\), then the target quantity is
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.$$
A brute-force search over all colorings is hopeless, so the solution counts fixed colorings under symmetry classes and averages them with Burnside's lemma.
The implementation solves a general instance first and only then applies it to consecutive Fibonacci sizes. The key object is the periodic grid
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
For one periodic axis of length \(n\), the allowed symmetries are the affine maps
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
When \(n>2\), this set has \(2n\) elements; for \(n=1\) and \(n=2\) some maps coincide, so those small cases are handled separately by the implementation.
The maps with \(\sigma=1\) are pure shifts. If such a shift has order \(u\), then every orbit on that axis is a cycle of length \(u\), and there are \(n/u\) such cycles. The number of shifts of order \(u\) is \(\varphi(u)\), because
$$u=\frac{n}{\gcd(n,t)}$$
and exactly \(\varphi(u)\) offsets produce that order. So every divisor \(u\mid n\) contributes one shift class with multiplicity \(\varphi(u)\) and cycle profile
$$u^{\,n/u}.$$
The maps with \(\sigma=-1\) are reversals. Their cycle structure depends only on the parity of \(n\):
$$\begin{aligned} n\ \text{odd}&:\quad 1^1\,2^{(n-1)/2},\\ n\ \text{even, one half of the reversals}&:\quad 1^2\,2^{(n-2)/2},\\ n\ \text{even, the other half}&:\quad 2^{n/2}. \end{aligned}$$
This follows from the congruence \(2x\equiv t\pmod n\): for odd \(n\) it has one solution, for even \(n\) it has either two or zero solutions depending on the parity of \(t\).
Let \(\Gamma_r\) and \(\Gamma_s\) be the symmetry sets on the two axes. A coloring is a function
$$f:X_{r,s}\to \{1,2,\dots,q\}.$$
For \((g,h)\in \Gamma_r\times \Gamma_s\), let \(c(g,h)\) be the number of cycles of the induced permutation on the cell set \(X_{r,s}\). A coloring fixed by \((g,h)\) must be constant on each cycle, so the fixed colorings that use every color are exactly the surjections from a \(c(g,h)\)-element cycle set onto the \(q\) colors.
By inclusion-exclusion, that number is
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c.$$
Therefore Burnside gives
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q).$$
This formula is exact, but it becomes fast only after we compress group elements by cycle type.
Suppose one symmetry on the first axis contains \(m_i\) cycles of length \(\ell_i\), and one symmetry on the second axis contains \(n_j\) cycles of length \(r_j\). On the Cartesian product of one \(\ell_i\)-cycle and one \(r_j\)-cycle, the action advances simultaneously around both cycles.
The orbit length is \(\operatorname{lcm}(\ell_i,r_j)\), so the \(\ell_i r_j\) points split into
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
product cycles. Summing over all profile pairs yields
$$c(g,h)=\sum_{i}\sum_{j} m_i n_j\,\gcd(\ell_i,r_j).$$
This is the central formula used to turn two one-dimensional cycle profiles into the number of cycles on the full two-dimensional pattern.
All group elements with the same cycle profile contribute the same fixed-coloring count, so the Burnside sum can be rewritten over classes instead of individual symmetries.
For one axis of length \(n\), the implementation needs only
$$\tau(n)+O(1)$$
different profiles: one shift profile for each divisor of \(n\), plus one or two reversal profiles according to parity. The multiplicities of those profiles are \(\varphi(u)\) for shifts and the obvious parity-dependent counts for reversals.
This compression is why huge symmetry groups never need to be enumerated explicitly. In the actual Fibonacci inputs, the number of class pairs is tiny compared with the raw number of group elements.
This checkpoint appears in the implementation and is small enough to compute by hand.
For length \(2\), the axis has two classes:
$$1^2\ \text{with multiplicity }1,\qquad 2^1\ \text{with multiplicity }1.$$
For length \(3\), the axis has three classes:
$$1^3\ \text{with multiplicity }1,\qquad 3^1\ \text{with multiplicity }2,\qquad 1^1 2^1\ \text{with multiplicity }3.$$
Because \(q=2\), the surjection count simplifies to
$$\operatorname{Surj}(c,2)=2^c-2.$$
Using the product-cycle formula, the six class pairs give
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
So the weighted Burnside numerator is
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132.$$
The group sizes are \(|\Gamma_2|=2\) and \(|\Gamma_3|=6\), hence
$$A_2(2,3)=\frac{132}{2\cdot 6}=11.$$
Once the class-compressed Burnside count \(A_q(r,s)\) is available, Problem 651 simply evaluates it at
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40,$$
and accumulates the results modulo \(10^9+7\):
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they build the binomial coefficients needed by the inclusion-exclusion formula and use fast modular exponentiation for the powers \((q-j)^c\).
For each of the two periodic lengths, the implementation factorizes the length, enumerates its divisors, converts divisor data into shift classes with multiplicities \(\varphi(u)\), and then appends the parity-dependent reversal classes. The tiny degenerate lengths \(1\) and \(2\) are treated explicitly.
Next the implementation loops over every pair of classes from the two axes. For each pair it computes the total cycle count by summing \(\gcd(\ell_i,r_j)\) across the profile entries. Many different class pairs lead to the same cycle count, so the value of \(\operatorname{Surj}(c,q)\) is cached and reused.
Each Burnside contribution is the class multiplicity product times the cached surjection count. After summing all contributions, the implementation divides by the group size using a modular inverse and adds the resulting orbit count to the running Fibonacci total.
For one general instance \(A_q(r,s)\), factorizing the two side lengths by trial division costs \(O(\sqrt{r}+\sqrt{s})\) time in the implementations shown here. If \(K(r)\) and \(K(s)\) denote the numbers of symmetry classes on the two axes, then the Burnside loop uses \(O(K(r)K(s))\) class pairs.
Each class profile has only one or two cycle lengths, so the product-cycle computation for one pair is \(O(1)\). Every distinct cycle count triggers one inclusion-exclusion evaluation in \(O(q)\), but \(q\le 40\) in Problem 651 and many class pairs share the same cycle count. Memory usage is \(O(K(r)+K(s)+U+q^2)\), where \(U\) is the number of distinct cached cycle counts. In practice the method is extremely small compared with the combinatorial size of the raw coloring space.
Seien \(F_1=F_2=1\). Für jedes \(t\) von \(4\) bis \(40\) betrachten wir ein \(F_{t-1}\times F_t\)-Gitter aus Zellen mit zwei periodischen Koordinaten. Auf jeder Achse darf man unabhängig verschieben oder spiegeln; zwei Färbungen gelten also als äquivalent, wenn sie durch solche Operationen ineinander überführt werden können. Zugelassen sind nur Färbungen, die alle \(t\) Farben mindestens einmal verwenden, und Problem 651 verlangt die Summe aller entsprechenden Bahnen modulo \(10^9+7\).
Bezeichnet \(A_q(r,s)\) die Anzahl gültiger Äquivalenzklassen mit \(q\) Farben und Seitenlängen \(r\) und \(s\), so ist gesucht:
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.$$
Direktes Durchprobieren aller Färbungen ist unmöglich; deshalb zählt die Lösung Fixfärbungen unter Symmetrien und mittelt diese mit dem Burnside-Lemma.
Zunächst wird eine allgemeine Instanz gelöst und erst danach auf aufeinanderfolgende Fibonacci-Größen angewendet. Das Grundobjekt ist das periodische Gitter
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
Für eine periodische Achse der Länge \(n\) sind die erlaubten Symmetrien die affinen Abbildungen
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
Für \(n>2\) gibt es davon \(2n\); bei \(n=1\) und \(n=2\) fallen einige Abbildungen zusammen, daher behandelt die Implementierung diese kleinen Fälle separat.
Der Fall \(\sigma=1\) entspricht reinen Verschiebungen. Hat eine solche Verschiebung Ordnung \(u\), dann besteht ihre Zykelzerlegung aus \(n/u\) Zykeln der Länge \(u\). Die Anzahl der Verschiebungen mit Ordnung \(u\) ist \(\varphi(u)\), denn
$$u=\frac{n}{\gcd(n,t)}.$$
Damit liefert jeder Teiler \(u\mid n\) genau eine Verschiebungsklasse mit Multiplizität \(\varphi(u)\) und Zyklusprofil
$$u^{\,n/u}.$$
Der Fall \(\sigma=-1\) beschreibt Spiegelungen. Deren Zyklusstruktur hängt nur von der Parität von \(n\) ab:
$$\begin{aligned} n\ \text{ungerade}&:\quad 1^1\,2^{(n-1)/2},\\ n\ \text{gerade, eine Hälfte der Spiegelungen}&:\quad 1^2\,2^{(n-2)/2},\\ n\ \text{gerade, die andere Hälfte}&:\quad 2^{n/2}. \end{aligned}$$
Das folgt aus \(2x\equiv t\pmod n\): für ungerades \(n\) gibt es genau eine Lösung, für gerades \(n\) je nach Parität von \(t\) entweder zwei oder keine.
Seien \(\Gamma_r\) und \(\Gamma_s\) die Symmetriemengen der beiden Achsen. Eine Färbung ist eine Abbildung
$$f:X_{r,s}\to \{1,2,\dots,q\}.$$
Für \((g,h)\in \Gamma_r\times \Gamma_s\) bezeichne \(c(g,h)\) die Anzahl der Zyklen der induzierten Permutation auf der Zellmenge \(X_{r,s}\). Eine unter \((g,h)\) feste Färbung ist auf jedem Zyklus konstant. Färbungen, die alle Farben benutzen, entsprechen also genau den Surjektionen von einer Menge mit \(c(g,h)\) Elementen auf die \(q\) Farben.
Mit Inklusion-Exklusion erhält man
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c.$$
Daraus folgt
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q).$$
Diese Formel ist exakt; schnell wird sie erst durch Zusammenfassen nach Zyklusprofilen.
Nehmen wir an, eine Symmetrie auf der ersten Achse besitzt \(m_i\) Zykel der Länge \(\ell_i\), und eine Symmetrie auf der zweiten Achse besitzt \(n_j\) Zykel der Länge \(r_j\). Auf dem kartesischen Produkt eines \(\ell_i\)-Zykels mit einem \(r_j\)-Zykel läuft die Wirkung gleichzeitig auf beiden Komponenten.
Die Orbitlänge ist \(\operatorname{lcm}(\ell_i,r_j)\), also zerfallen die \(\ell_i r_j\) Punkte in
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
Produktzyklen. Summiert man über alle Profilpaare, erhält man
$$c(g,h)=\sum_{i}\sum_{j} m_i n_j\,\gcd(\ell_i,r_j).$$
Genau diese Formel macht aus zwei eindimensionalen Zyklusprofilen die Anzahl der Zyklen im vollständigen zweidimensionalen Muster.
Alle Gruppenelemente mit gleichem Zyklusprofil liefern denselben Beitrag, daher kann die Burnside-Summe über Klassen statt über einzelne Symmetrien laufen.
Für eine Achse der Länge \(n\) benötigt die Implementierung nur
$$\tau(n)+O(1)$$
verschiedene Profile: ein Verschiebungsprofil pro Teiler von \(n\) sowie je nach Parität eine oder zwei Spiegelungsklassen. Die Multiplizitäten sind \(\varphi(u)\) bei Verschiebungen und die offensichtlichen paritätsabhängigen Anzahlen bei Spiegelungen.
Gerade dadurch müssen riesige Symmetriegruppen nie explizit durchlaufen werden. Für die Fibonacci-Eingaben ist die Zahl der Klassenpaare winzig im Vergleich zur rohen Gruppengröße.
Dieser Kontrollwert kommt direkt in der Implementierung vor und lässt sich vollständig von Hand nachvollziehen.
Für Länge \(2\) gibt es zwei Klassen:
$$1^2\ \text{mit Multiplizität }1,\qquad 2^1\ \text{mit Multiplizität }1.$$
Für Länge \(3\) gibt es drei Klassen:
$$1^3\ \text{mit Multiplizität }1,\qquad 3^1\ \text{mit Multiplizität }2,\qquad 1^1 2^1\ \text{mit Multiplizität }3.$$
Wegen \(q=2\) vereinfacht sich die Surjektionszahl zu
$$\operatorname{Surj}(c,2)=2^c-2.$$
Mit der Produktzyklus-Formel ergeben sich für die sechs Klassenpaare
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
Damit ist der gewichtete Burnside-Zähler
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132.$$
Da \(|\Gamma_2|=2\) und \(|\Gamma_3|=6\), folgt
$$A_2(2,3)=\frac{132}{2\cdot 6}=11.$$
Sobald das komprimierte Burnside-Ergebnis \(A_q(r,s)\) vorliegt, setzt Problem 651 einfach
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40,$$
und summiert alles modulo \(10^9+7\):
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Pipeline. Zuerst werden die Binomialkoeffizienten für die Inklusion-Exklusion vorbereitet; die Potenzen \((q-j)^c\) werden mit schneller modularer Exponentiation berechnet.
Für jede der beiden periodischen Längen faktorisiert die Implementierung die Zahl, erzeugt daraus alle Teiler, übersetzt diese Teiler in Verschiebungsklassen mit Multiplizitäten \(\varphi(u)\) und ergänzt anschließend die paritätsabhängigen Spiegelungsklassen. Die kleinen degenerierten Fälle \(1\) und \(2\) werden explizit behandelt.
Danach iteriert die Implementierung über alle Klassenpaare der beiden Achsen. Für jedes Paar wird die gesamte Zykluszahl über die \(\gcd\)-Formel bestimmt. Viele Klassenpaare liefern denselben Zykluswert, deshalb wird \(\operatorname{Surj}(c,q)\) nach \(c\) zwischengespeichert und wiederverwendet.
Jeder Burnside-Beitrag ist das Produkt der beiden Klassenmultiplizitäten mit dem zwischengespeicherten Surjektionswert. Nach der Summe wird durch die Gruppengröße per modularer Inversen dividiert und das Ergebnis zum laufenden Fibonacci-Gesamtwert addiert.
Für eine allgemeine Instanz \(A_q(r,s)\) kostet die Faktorisierung der beiden Seitenlängen mittels Trial Division in den gezeigten Implementierungen \(O(\sqrt{r}+\sqrt{s})\) Zeit. Bezeichnen \(K(r)\) und \(K(s)\) die Zahlen der Symmetrieklassen beider Achsen, dann benötigt die Burnside-Schleife \(O(K(r)K(s))\) Klassenpaare.
Jedes Profil besitzt nur eine oder zwei Zykluslängen, daher ist die Produktzyklus-Berechnung pro Paar \(O(1)\). Jeder neue Zykluswert verursacht genau eine Inklusion-Exklusion in \(O(q)\), aber in Problem 651 gilt \(q\le 40\) und viele Klassenpaare teilen sich denselben Wert. Der Speicherbedarf ist \(O(K(r)+K(s)+U+q^2)\), wobei \(U\) die Anzahl verschiedener zwischengespeicherter Zykluszahlen ist. Praktisch ist das Verfahren winzig gegenüber dem tatsächlichen Färbungsraum.
\(F_1=F_2=1\) olsun. \(4\) ile \(40\) arasındaki her \(t\) için, iki periyodik koordinatla indekslenen \(F_{t-1}\times F_t\) hücreli bir desen düşünülür. Her eksen bağımsız olarak kaydırılabilir veya ters çevrilebilir; dolayısıyla iki boyama bu işlemlerden biriyle birbirine dönüştürülebiliyorsa eşdeğer kabul edilir. Yalnızca tüm \(t\) rengin en az bir kez kullanıldığı boyamalar geçerlidir ve Problem 651 bu yörünge sayılarının toplamını \(10^9+7\) modunda ister.
\(q\) renkli, kenar uzunlukları \(r\) ve \(s\) olan geçerli eşdeğerlik sınıfı sayısına \(A_q(r,s)\) dersek aranan büyüklük
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}$$
olur. Tüm boyamaları doğrudan denemek imkansız olduğu için çözüm, simetriler altında sabit kalan boyamaları sayıp Burnside lemmasıyla ortalama alır.
Uygulama önce genel bir durumu çözer, sonra bunu ardışık Fibonacci boyutlarına uygular. Temel nesne şu periyodik ızgaradır:
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
Uzunluğu \(n\) olan periyodik bir eksende izin verilen simetriler şu affine dönüşümlerdir:
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
\(n>2\) için bu kümenin \(2n\) elemanı vardır; \(n=1\) ve \(n=2\) durumlarında bazı dönüşümler çakıştığı için uygulama bu küçük halleri ayrı ele alır.
\(\sigma=1\) olduğunda saf kaydırmalar elde edilir. Böyle bir kaydırmanın mertebesi \(u\) ise, eksen üzerindeki çevrim ayrışımı uzunluğu \(u\) olan \(n/u\) çevrimden oluşur. Mertebesi \(u\) olan kaydırma sayısı \(\varphi(u)\)'dur, çünkü
$$u=\frac{n}{\gcd(n,t)}.$$
Bu yüzden her \(u\mid n\) böleni, çokluğu \(\varphi(u)\) olan ve çevrim profili
$$u^{\,n/u}$$
şeklinde yazılan bir kaydırma sınıfı verir.
\(\sigma=-1\) olduğunda ters çevirmeler gelir. Bunların çevrim yapısı yalnızca \(n\)'in tekliğine ya da çiftliğine bağlıdır:
$$\begin{aligned} n\ \text{tek}&:\quad 1^1\,2^{(n-1)/2},\\ n\ \text{çift, ters çevirmelerin yarısı}&:\quad 1^2\,2^{(n-2)/2},\\ n\ \text{çift, diğer yarısı}&:\quad 2^{n/2}. \end{aligned}$$
Bunun nedeni \(2x\equiv t\pmod n\) denkleminin davranışıdır: \(n\) tekse tek çözüm vardır, \(n\) çiftse \(t\)'nin paritesine göre ya iki çözüm ya da hiç çözüm olmaz.
İki eksendeki simetri kümeleri \(\Gamma_r\) ve \(\Gamma_s\) olsun. Bir boyama
$$f:X_{r,s}\to \{1,2,\dots,q\}$$
şeklinde bir fonksiyondur. \((g,h)\in \Gamma_r\times \Gamma_s\) için, hücre kümesi \(X_{r,s}\) üzerinde oluşan permütasyonun çevrim sayısına \(c(g,h)\) diyelim. \((g,h)\) tarafından sabit kalan bir boyama her çevrim üzerinde sabit olmak zorundadır. Dolayısıyla tüm renkleri kullanan sabit boyamalar, \(c(g,h)\) elemanlı çevrim kümesinden \(q\) renge yapılan sürjektif atamalardır.
Dahil et-çıkar ile bu sayı
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c$$
olur. Böylece Burnside formülü
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q)$$
şeklindedir. Bu formül doğrudur; hızlı hale gelmesi için simetrileri çevrim tipine göre sıkıştırmak gerekir.
Birinci eksendeki bir simetri \(m_i\) tane uzunluğu \(\ell_i\) olan çevrim, ikinci eksendeki bir simetri de \(n_j\) tane uzunluğu \(r_j\) olan çevrim içersin. Bir \(\ell_i\)-çevrimi ile bir \(r_j\)-çevriminin Kartezyen çarpımında etki iki yönde aynı anda ilerler.
Yörünge uzunluğu \(\operatorname{lcm}(\ell_i,r_j)\) olur; bu nedenle \(\ell_i r_j\) nokta
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
adet çevrime ayrılır. Tüm profil çiftleri toplanınca
$$c(g,h)=\sum_i\sum_j m_i n_j\,\gcd(\ell_i,r_j)$$
elde edilir. İki tek boyutlu çevrim profilinden iki boyutlu desenin toplam çevrim sayısını çıkaran temel formül budur.
Aynı çevrim profiline sahip tüm grup elemanları aynı sabit-boyama sayısını verdiği için Burnside toplamı tek tek elemanlar yerine sınıflar üzerinden yazılabilir.
Uzunluğu \(n\) olan tek bir eksen için uygulamanın ihtiyaç duyduğu farklı profil sayısı
$$\tau(n)+O(1)$$
kadardır: \(n\)'in her böleni için bir kaydırma profili ve pariteye göre bir ya da iki ters çevirme profili. Kaydırma sınıflarının çoklukları \(\varphi(u)\), ters çevirme sınıflarının çoklukları ise doğrudan parite hesabından gelir.
Büyük simetri gruplarının hiç açıkça gezilmemesinin nedeni budur. Gerçek Fibonacci girdilerinde sınıf çifti sayısı, ham grup büyüklüğüne göre çok küçüktür.
Bu değer uygulamada kontrol noktası olarak yer alır ve elle tamamen hesaplanabilir.
Uzunluk \(2\) için iki sınıf vardır:
$$1^2\ \text{çokluk }1,\qquad 2^1\ \text{çokluk }1.$$
Uzunluk \(3\) için üç sınıf vardır:
$$1^3\ \text{çokluk }1,\qquad 3^1\ \text{çokluk }2,\qquad 1^1 2^1\ \text{çokluk }3.$$
\(q=2\) olduğundan sürjeksiyon sayısı
$$\operatorname{Surj}(c,2)=2^c-2$$
şeklinde sadeleşir. Ürün-çevrim formülüyle altı sınıf çifti için
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
Böylece ağırlıklı Burnside payı
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132$$
olur. \(|\Gamma_2|=2\) ve \(|\Gamma_3|=6\) olduğundan
$$A_2(2,3)=\frac{132}{2\cdot 6}=11$$
sonucu çıkar.
Sınıf-sıkıştırmalı Burnside sayımı \(A_q(r,s)\) elde edilince Problem 651 sadece
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40$$
yerine koyup mod \(10^9+7\) altında toplar:
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce dahil et-çıkar formülünde gereken binom katsayıları hazırlanır; \((q-j)^c\) üsleri hızlı modüler üs alma ile hesaplanır.
İki periyodik uzunluğun her biri için uygulama sayıyı çarpanlara ayırır, bölenleri üretir, bunlardan \(\varphi(u)\) çokluklu kaydırma sınıfları çıkarır ve ardından pariteye bağlı ters çevirme sınıflarını ekler. Çok küçük ve bozulmuş \(1\) ile \(2\) durumları açıkça ele alınır.
Daha sonra iki eksenden gelen tüm sınıf çiftleri dolaşılır. Her çift için toplam çevrim sayısı \(\gcd\) formülüyle bulunur. Farklı sınıf çiftleri çoğu zaman aynı çevrim sayısını verdiğinden \(\operatorname{Surj}(c,q)\) değeri \(c\)'ye göre önbelleğe alınır ve yeniden kullanılır.
Her Burnside katkısı, iki sınıf çokluğunun çarpımı ile önbellekteki sürjeksiyon sayısının çarpımıdır. Tüm katkılar toplandıktan sonra grup büyüklüğüne modüler ters ile bölünür ve sonuç Fibonacci toplamına eklenir.
Genel bir \(A_q(r,s)\) örneğinde, burada verilen uygulamalarda iki kenar uzunluğunu deneme bölmeleriyle çarpanlara ayırma maliyeti \(O(\sqrt{r}+\sqrt{s})\)'dir. İki eksendeki simetri sınıfı sayıları \(K(r)\) ve \(K(s)\) ise Burnside döngüsü \(O(K(r)K(s))\) sınıf çifti kullanır.
Her sınıf profili yalnızca bir ya da iki çevrim uzunluğu içerdiğinden, tek bir çift için ürün-çevrim hesabı \(O(1)\)'dir. Her yeni çevrim sayısı en fazla bir kez \(O(q)\) maliyetli dahil et-çıkar hesabı üretir; ayrıca Problem 651'de \(q\le 40\) ve birçok sınıf çifti aynı değeri paylaşır. Bellek kullanımı \(O(K(r)+K(s)+U+q^2)\)'dir; burada \(U\), önbellekte tutulan farklı çevrim sayılarının sayısıdır. Pratikte yöntem, ham boyama uzayına göre son derece küçüktür.
Sean \(F_1=F_2=1\). Para cada entero \(t\) entre \(4\) y \(40\), se considera una malla de \(F_{t-1}\times F_t\) celdas indexadas por dos coordenadas periódicas. En cada eje se permite desplazar o invertir la coordenada de forma independiente; por tanto, dos coloraciones son equivalentes si una puede obtenerse de la otra mediante esas simetrías. Solo se aceptan las coloraciones que usan los \(t\) colores al menos una vez, y el problema pide la suma de todas esas órbitas módulo \(10^9+7\).
Si \(A_q(r,s)\) denota el número de clases de equivalencia válidas con \(q\) colores y lados \(r\) y \(s\), entonces la cantidad buscada es
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.$$
Enumerar todas las coloraciones es inviable, así que la solución cuenta coloraciones fijas bajo clases de simetría y luego promedia con el lema de Burnside.
La implementación resuelve primero un caso general y después lo evalúa en tamaños consecutivos de Fibonacci. El objeto básico es la rejilla periódica
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
Para un eje periódico de longitud \(n\), las simetrías permitidas son las aplicaciones afines
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
Si \(n>2\), este conjunto tiene \(2n\) elementos; cuando \(n=1\) o \(n=2\), algunas aplicaciones coinciden y la implementación trata esos casos aparte.
Cuando \(\sigma=1\) obtenemos desplazamientos puros. Si un desplazamiento tiene orden \(u\), su descomposición en ciclos contiene \(n/u\) ciclos de longitud \(u\). El número de desplazamientos de orden \(u\) es \(\varphi(u)\), porque
$$u=\frac{n}{\gcd(n,t)}.$$
Por tanto, cada divisor \(u\mid n\) produce una clase de desplazamientos con multiplicidad \(\varphi(u)\) y perfil cíclico
$$u^{\,n/u}.$$
Cuando \(\sigma=-1\), aparecen las inversiones. Su estructura de ciclos depende solo de la paridad de \(n\):
$$\begin{aligned} n\ \text{impar}&:\quad 1^1\,2^{(n-1)/2},\\ n\ \text{par, una mitad de las inversiones}&:\quad 1^2\,2^{(n-2)/2},\\ n\ \text{par, la otra mitad}&:\quad 2^{n/2}. \end{aligned}$$
Esto sale de la congruencia \(2x\equiv t\pmod n\): si \(n\) es impar hay una única solución; si \(n\) es par hay dos o ninguna según la paridad de \(t\).
Sean \(\Gamma_r\) y \(\Gamma_s\) los conjuntos de simetrías en los dos ejes. Una coloración es una función
$$f:X_{r,s}\to \{1,2,\dots,q\}.$$
Para \((g,h)\in \Gamma_r\times \Gamma_s\), sea \(c(g,h)\) el número de ciclos de la permutación inducida sobre el conjunto de celdas \(X_{r,s}\). Una coloración fija por \((g,h)\) debe ser constante en cada ciclo, así que las coloraciones fijas que usan todos los colores son exactamente las sobreyecciones desde un conjunto de \(c(g,h)\) ciclos hacia los \(q\) colores.
Por inclusión-exclusión, ese número es
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c.$$
Entonces Burnside da
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q).$$
La fórmula es exacta, pero solo resulta eficiente después de agrupar las simetrías por tipo cíclico.
Supongamos que una simetría del primer eje contiene \(m_i\) ciclos de longitud \(\ell_i\), y una simetría del segundo eje contiene \(n_j\) ciclos de longitud \(r_j\). En el producto cartesiano de un ciclo de longitud \(\ell_i\) con otro de longitud \(r_j\), la acción avanza simultáneamente en ambos sentidos.
La longitud de la órbita es \(\operatorname{lcm}(\ell_i,r_j)\), así que los \(\ell_i r_j\) puntos se reparten en
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
ciclos producto. Sumando sobre todos los pares de perfiles se obtiene
$$c(g,h)=\sum_i\sum_j m_i n_j\,\gcd(\ell_i,r_j).$$
Esta es la fórmula central que transforma dos perfiles unidimensionales en el número de ciclos del patrón bidimensional.
Todos los elementos del grupo con el mismo perfil de ciclos aportan el mismo número de coloraciones fijas, así que la suma de Burnside puede escribirse sobre clases en lugar de hacerlo sobre elementos individuales.
Para un eje de longitud \(n\), la implementación solo necesita
$$\tau(n)+O(1)$$
perfiles distintos: uno de desplazamiento por cada divisor de \(n\) y una o dos clases de inversión según la paridad. Las multiplicidades son \(\varphi(u)\) para los desplazamientos y los conteos inmediatos derivados de la paridad para las inversiones.
Gracias a esta compresión, nunca se enumeran explícitamente grupos enormes. En los casos de Fibonacci del problema real, el número de pares de clases es diminuto comparado con el tamaño bruto del grupo.
Este valor aparece como comprobación interna en la implementación y es lo bastante pequeño como para desarrollarlo a mano.
Para longitud \(2\), hay dos clases:
$$1^2\ \text{con multiplicidad }1,\qquad 2^1\ \text{con multiplicidad }1.$$
Para longitud \(3\), hay tres clases:
$$1^3\ \text{con multiplicidad }1,\qquad 3^1\ \text{con multiplicidad }2,\qquad 1^1 2^1\ \text{con multiplicidad }3.$$
Como \(q=2\), el número de sobreyecciones se simplifica a
$$\operatorname{Surj}(c,2)=2^c-2.$$
Aplicando la fórmula de ciclos producto a los seis pares de clases, obtenemos
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
Así, el numerador ponderado de Burnside es
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132.$$
Como \(|\Gamma_2|=2\) y \(|\Gamma_3|=6\), resulta
$$A_2(2,3)=\frac{132}{2\cdot 6}=11.$$
Una vez disponible el conteo comprimido \(A_q(r,s)\), Problem 651 solo evalúa
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40,$$
y acumula los resultados módulo \(10^9+7\):
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
Las implementaciones en C++, Python y Java siguen el mismo esquema matemático. Primero construyen los coeficientes binomiales necesarios para la inclusión-exclusión y usan exponenciación modular rápida para calcular las potencias \((q-j)^c\).
Para cada una de las dos longitudes periódicas, la implementación factoriza el número, enumera sus divisores, convierte esa información en clases de desplazamiento con multiplicidades \(\varphi(u)\) y añade después las clases de inversión dependientes de la paridad. Los casos degenerados \(1\) y \(2\) se tratan explícitamente.
Después, la implementación recorre todos los pares de clases de ambos ejes. Para cada par calcula el número total de ciclos mediante la fórmula con \(\gcd\). Como muchos pares producen el mismo número de ciclos, el valor \(\operatorname{Surj}(c,q)\) se memoriza por \(c\) y se reutiliza.
Cada contribución de Burnside es el producto de las multiplicidades de clase por el valor memorizado de sobreyecciones. Tras sumar todas las contribuciones, la implementación divide por el tamaño del grupo mediante un inverso modular y añade el resultado al total de Fibonacci.
Para una instancia general \(A_q(r,s)\), factorizar las dos longitudes por división de prueba cuesta \(O(\sqrt{r}+\sqrt{s})\) en las implementaciones mostradas. Si \(K(r)\) y \(K(s)\) son los números de clases de simetría en ambos ejes, entonces el bucle de Burnside usa \(O(K(r)K(s))\) pares de clases.
Cada perfil contiene solo una o dos longitudes de ciclo, de modo que el cálculo de ciclos producto para un par es \(O(1)\). Cada nuevo valor de ciclo provoca una única evaluación de inclusión-exclusión en \(O(q)\), pero en Problem 651 se tiene \(q\le 40\) y muchos pares comparten el mismo valor. La memoria es \(O(K(r)+K(s)+U+q^2)\), donde \(U\) es el número de conteos de ciclos distintos guardados en caché. En la práctica, el método es minúsculo comparado con el espacio bruto de coloraciones.
设 \(F_1=F_2=1\)。对每个 \(4\le t\le 40\)，考虑一个大小为 \(F_{t-1}\times F_t\) 的单元格阵列，两个方向都按周期坐标编号。每个方向都允许独立地做平移或反向，因此如果两种着色可以通过这些操作互相变换，就视为同一种图案。题目只接受“所有 \(t\) 种颜色都至少出现一次”的着色，并要求把这些等价类的数量相加，最后对 \(10^9+7\) 取模。
若记 \(A_q(r,s)\) 为使用 \(q\) 种颜色、边长为 \(r\) 与 \(s\) 时的有效等价类数量，那么目标就是
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.$$
直接枚举全部着色完全不可行，所以实现采用 Burnside 引理：先数每个对称操作固定了多少种合法着色，再做平均。
实现先解决一般情形，再把它代入连续 Fibonacci 尺寸。基本对象是周期网格
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
长度为 \(n\) 的一个周期方向上，允许的对称变换是仿射映射
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
当 \(n>2\) 时，这个集合有 \(2n\) 个元素；而 \(n=1\) 与 \(n=2\) 时，一些变换会重合，所以实现中对这两个小规模情形单独处理。
\(\sigma=1\) 时得到纯平移。若某个平移的阶为 \(u\)，那么它在该方向上会分解成 \(n/u\) 个长度为 \(u\) 的循环。阶恰好等于 \(u\) 的平移有 \(\varphi(u)\) 个，因为
$$u=\frac{n}{\gcd(n,t)}.$$
因此每个除数 \(u\mid n\) 都对应一个平移类，其重数为 \(\varphi(u)\)，循环轮廓写成
$$u^{\,n/u}.$$
\(\sigma=-1\) 时是反向操作。它的循环结构只取决于 \(n\) 的奇偶性：
$$\begin{aligned} n\ \text{为奇数}&:\quad 1^1\,2^{(n-1)/2},\\ n\ \text{为偶数，反向的一半}&:\quad 1^2\,2^{(n-2)/2},\\ n\ \text{为偶数，另一半}&:\quad 2^{n/2}. \end{aligned}$$
原因是固定点方程 \(2x\equiv t\pmod n\) 的解数不同：当 \(n\) 为奇数时恰有一个解；当 \(n\) 为偶数时，根据 \(t\) 的奇偶性，要么有两个解，要么没有解。
记两个方向上的对称集合分别为 \(\Gamma_r\) 与 \(\Gamma_s\)。一次着色就是一个函数
$$f:X_{r,s}\to \{1,2,\dots,q\}.$$
对于 \((g,h)\in \Gamma_r\times \Gamma_s\)，记它在单元格集合 \(X_{r,s}\) 上诱导出的置换循环数为 \(c(g,h)\)。如果某种着色在 \((g,h)\) 作用下保持不变，那么同一个循环里的所有单元格必须同色。因此，既固定又“用满全部 \(q\) 种颜色”的着色数量，恰好就是把 \(c(g,h)\) 个循环映射到 \(q\) 种颜色上的满射数量。
用容斥原理可得
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c.$$
于是 Burnside 公式写成
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q).$$
这个公式本身已经完全正确，但若不继续压缩循环类型，计算仍然太慢。
设第一条轴上的某个对称包含 \(m_i\) 个长度为 \(\ell_i\) 的循环，第二条轴上的某个对称包含 \(n_j\) 个长度为 \(r_j\) 的循环。取其中一个 \(\ell_i\)-循环与一个 \(r_j\)-循环做笛卡尔积，在乘积空间上，动作会同时沿两个方向前进。
单个轨道的长度是 \(\operatorname{lcm}(\ell_i,r_j)\)，因此总共 \(\ell_i r_j\) 个点会分裂成
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
个乘积循环。把所有轮廓项都加起来，就得到
$$c(g,h)=\sum_i\sum_j m_i n_j\,\gcd(\ell_i,r_j).$$
这正是实现中最核心的公式：它把两个一维循环轮廓转化为整个二维图案上的循环总数。
只要循环轮廓相同，对固定着色数量的贡献就完全相同，所以 Burnside 求和没必要逐个遍历所有对称元素，只需要按“循环轮廓类”计数即可。
对于长度为 \(n\) 的单个方向，实现只需要
$$\tau(n)+O(1)$$
种不同轮廓：每个除数对应一个平移类，再加上依据奇偶性出现的一类或两类反向类。平移类的重数是 \(\varphi(u)\)，反向类的重数则由奇偶结构直接给出。
这一步压缩是算法快的根本原因。真实输入中的群规模很大，但轮廓类数量很小，Burnside 求和因此可以在很少的类对上完成。
这个值在实现里作为检验点出现，而且规模足够小，可以完整手算。
当长度为 \(2\) 时，有两类：
$$1^2\ \text{，重数 }1,\qquad 2^1\ \text{，重数 }1.$$
当长度为 \(3\) 时，有三类：
$$1^3\ \text{，重数 }1,\qquad 3^1\ \text{，重数 }2,\qquad 1^1 2^1\ \text{，重数 }3.$$
因为此时 \(q=2\)，满射数简化为
$$\operatorname{Surj}(c,2)=2^c-2.$$
利用乘积循环公式，六个类对的循环数分别为
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
所以 Burnside 加权分子为
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132.$$
又因为 \(|\Gamma_2|=2\)、\(|\Gamma_3|=6\)，所以
$$A_2(2,3)=\frac{132}{2\cdot 6}=11.$$
一旦得到一般情形的压缩 Burnside 计数 \(A_q(r,s)\)，Problem 651 只需在
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40$$
处求值，并在模 \(10^9+7\) 下累加：
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
C++、Python 和 Java 实现遵循同一条数学流程。首先预计算容斥公式需要的二项式系数，并用快速模幂计算 \((q-j)^c\) 这样的幂。
对于两个周期长度中的每一个，程序先做因数分解，再枚举所有约数，把这些约数转换成重数为 \(\varphi(u)\) 的平移类，然后补上依赖奇偶性的反向类。长度 \(1\) 和 \(2\) 这两个退化情形会单独处理。
接下来，程序遍历两个方向上所有的类对。对每一对，它用 \(\gcd\) 公式计算总循环数。由于很多不同类对会得到同一个循环数，\(\operatorname{Surj}(c,q)\) 会按 \(c\) 做缓存，只算一次、反复复用。
每个 Burnside 项等于“类重数之积”乘以“缓存的满射数”。所有项相加后，再通过模逆除以群大小，得到该尺寸下的轨道数，并把它加到 Fibonacci 总和里。
对一般实例 \(A_q(r,s)\) 而言，这里的实现用试除法分解两个边长，时间复杂度为 \(O(\sqrt{r}+\sqrt{s})\)。若两个方向上的对称类数量分别为 \(K(r)\) 与 \(K(s)\)，那么 Burnside 主循环需要 \(O(K(r)K(s))\) 个类对。
每个类轮廓只含一到两个循环长度，所以单个类对的乘积循环计算是 \(O(1)\)。每出现一个新的循环数，只需额外做一次 \(O(q)\) 的容斥求值；而在 Problem 651 中 \(q\le 40\)，并且很多类对共享同一个循环数。空间复杂度是 \(O(K(r)+K(s)+U+q^2)\)，其中 \(U\) 表示缓存中不同循环数的个数。与原始着色空间相比，这个算法在实际中极其紧凑。
Пусть \(F_1=F_2=1\). Для каждого \(t\) от \(4\) до \(40\) рассматривается прямоугольный массив из \(F_{t-1}\times F_t\) ячеек, индексированный двумя периодическими координатами. По каждой координате независимо разрешены сдвиг и обращение, поэтому две раскраски считаются эквивалентными, если одну можно получить из другой такими симметриями. Разрешены только те раскраски, в которых все \(t\) цветов используются хотя бы один раз, и задача 651 просит сложить числа таких орбит по модулю \(10^9+7\).
Если \(A_q(r,s)\) обозначает число допустимых классов эквивалентности для \(q\) цветов и размеров \(r\) и \(s\), то требуется вычислить
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.$$
Полный перебор раскрасок невозможен, поэтому решение считает фиксированные раскраски для классов симметрий и усредняет их по лемме Бёрнсайда.
Сначала решается общая задача, а затем она подставляется для последовательных чисел Фибоначчи. Базовый объект здесь — периодическая решётка
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
Для периодической оси длины \(n\) разрешённые симметрии имеют вид
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
При \(n>2\) таких преобразований \(2n\); при \(n=1\) и \(n=2\) часть преобразований совпадает, поэтому в реализации эти малые случаи выделены отдельно.
Если \(\sigma=1\), мы получаем чистые сдвиги. Если порядок сдвига равен \(u\), то на оси он распадается на \(n/u\) циклов длины \(u\). Число сдвигов порядка \(u\) равно \(\varphi(u)\), потому что
$$u=\frac{n}{\gcd(n,t)}.$$
Значит, каждый делитель \(u\mid n\) даёт один класс сдвигов с кратностью \(\varphi(u)\) и циклическим профилем
$$u^{\,n/u}.$$
Если \(\sigma=-1\), получаются обращения. Их циклическая структура зависит только от чётности \(n\):
$$\begin{aligned} n\ \text{нечётно}&:\quad 1^1\,2^{(n-1)/2},\\ n\ \text{чётно, половина обращений}&:\quad 1^2\,2^{(n-2)/2},\\ n\ \text{чётно, другая половина}&:\quad 2^{n/2}. \end{aligned}$$
Это следует из сравнения \(2x\equiv t\pmod n\): при нечётном \(n\) решение ровно одно, а при чётном — либо два, либо ни одного в зависимости от чётности \(t\).
Пусть \(\Gamma_r\) и \(\Gamma_s\) — множества симметрий на двух осях. Раскраска — это функция
$$f:X_{r,s}\to \{1,2,\dots,q\}.$$
Для \((g,h)\in \Gamma_r\times \Gamma_s\) обозначим через \(c(g,h)\) число циклов индуцированной перестановки множества ячеек \(X_{r,s}\). Если раскраска фиксируется парой \((g,h)\), то она обязана быть постоянной на каждом цикле. Следовательно, число фиксированных раскрасок, использующих все цвета, равно числу сюръекций из множества из \(c(g,h)\) циклов на множество из \(q\) цветов.
По принципу включений-исключений это число равно
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c.$$
Тогда формула Бёрнсайда имеет вид
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q).$$
Формула точная, но быстрой она становится только после сжатия по циклическим профилям.
Пусть одна симметрия на первой оси содержит \(m_i\) циклов длины \(\ell_i\), а одна симметрия на второй оси содержит \(n_j\) циклов длины \(r_j\). На декартовом произведении одного \(\ell_i\)-цикла и одного \(r_j\)-цикла действие идёт одновременно по обеим координатам.
Длина орбиты равна \(\operatorname{lcm}(\ell_i,r_j)\), поэтому \(\ell_i r_j\) точек разбиваются на
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
циклов произведения. Суммирование по всем парам профилей даёт
$$c(g,h)=\sum_i\sum_j m_i n_j\,\gcd(\ell_i,r_j).$$
Именно эта формула переводит два одномерных циклических профиля в число циклов полного двумерного узора.
Все элементы группы с одинаковым циклическим профилем дают одинаковый вклад, поэтому сумму Бёрнсайда можно вести по классам, а не по отдельным элементам.
Для оси длины \(n\) реализации достаточно всего
$$\tau(n)+O(1)$$
различных профилей: по одному классу сдвигов на каждый делитель \(n\) и ещё один или два класса обращений в зависимости от чётности. Кратности равны \(\varphi(u)\) для сдвигов и очевидным числам, зависящим от чётности, для обращений.
Именно это сжатие делает метод быстрым. Для реальных входов Фибоначчи число пар классов крошечно по сравнению с сырым размером всей группы симметрий.
Это значение используется в реализации как контрольный тест и достаточно мало для ручного вычисления.
Для длины \(2\) есть два класса:
$$1^2\ \text{с кратностью }1,\qquad 2^1\ \text{с кратностью }1.$$
Для длины \(3\) есть три класса:
$$1^3\ \text{с кратностью }1,\qquad 3^1\ \text{с кратностью }2,\qquad 1^1 2^1\ \text{с кратностью }3.$$
Поскольку \(q=2\), число сюръекций упрощается до
$$\operatorname{Surj}(c,2)=2^c-2.$$
По формуле циклов произведения для шести пар классов получаем
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
Следовательно, взвешенный числитель Бёрнсайда равен
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132.$$
Так как \(|\Gamma_2|=2\) и \(|\Gamma_3|=6\), получаем
$$A_2(2,3)=\frac{132}{2\cdot 6}=11.$$
После того как найдено общее сжатое выражение \(A_q(r,s)\), задача 651 просто подставляет
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40,$$
и суммирует значения по модулю \(10^9+7\):
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они строят биномиальные коэффициенты для формулы включений-исключений и используют быстрое модульное возведение в степень для вычисления \((q-j)^c\).
Для каждой из двух периодических длин программа раскладывает число на множители, перечисляет делители, превращает их в классы сдвигов с кратностями \(\varphi(u)\), а затем добавляет классы обращений, зависящие от чётности. Малые вырожденные случаи \(1\) и \(2\) обрабатываются явно.
После этого реализация перебирает все пары классов двух осей. Для каждой пары общее число циклов вычисляется по формуле с \(\gcd\). Поскольку многие разные пары классов дают одно и то же число циклов, значение \(\operatorname{Surj}(c,q)\) кешируется по \(c\) и повторно используется.
Каждый вклад в сумму Бёрнсайда равен произведению кратностей классов, умноженному на кешированное число сюръекций. После суммирования код делит на размер группы через модульный обратный элемент и добавляет результат к общему Fibonacci-суммированию.
Для одной общей задачи \(A_q(r,s)\) факторизация двух размеров методом пробного деления в показанных реализациях стоит \(O(\sqrt{r}+\sqrt{s})\) времени. Если \(K(r)\) и \(K(s)\) обозначают числа классов симметрий на двух осях, то цикл Бёрнсайда использует \(O(K(r)K(s))\) пар классов.
Каждый профиль содержит лишь одну или две длины циклов, поэтому вычисление циклов произведения для одной пары занимает \(O(1)\). Каждое новое значение числа циклов вызывает ровно одну оценку включений-исключений за \(O(q)\), но в задаче 651 выполняется \(q\le 40\), и многие пары классов делят одно и то же значение. Память имеет порядок \(O(K(r)+K(s)+U+q^2)\), где \(U\) — число различных значений циклов в кеше. На практике это ничтожно мало по сравнению с размером пространства всех раскрасок.
لتكن \(F_1=F_2=1\). لكل \(t\) من \(4\) إلى \(40\)، ننظر إلى شبكة من الخلايا أبعادها \(F_{t-1}\times F_t\) ومفهرسة بإحداثيين دوريين. يمكن في كل محور إجراء إزاحة أو عكس بشكل مستقل، ولذلك تُعدّ تلوينتان متكافئتين إذا أمكن تحويل إحداهما إلى الأخرى بهذه التناظرات. لا تُقبل إلا التلوينات التي تستعمل جميع الألوان \(t\) مرة واحدة على الأقل، وتطلب المسألة 651 جمع أعداد هذه المدارات كلها بترديد \(10^9+7\).
إذا رمزنا بعدد أصناف التكافؤ الصالحة عند \(q\) ألوان وطولين \(r\) و\(s\) بالرمز \(A_q(r,s)\)، فإن الكمية المطلوبة هي
$$\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.$$
الفحص المباشر لكل التلوينات غير ممكن عمليًا، لذلك تعتمد الفكرة على عدّ التلوينات المثبتة تحت أصناف التناظر ثم أخذ المتوسط بواسطة لمّة برنسايد.
تقوم الخوارزمية أولًا بحل حالة عامة، ثم تطبّقها على الأزواج المتتالية من أعداد فيبوناتشي. الجسم الأساسي هو الشبكة الدورية
$$X_{r,s}=\mathbb{Z}/r\mathbb{Z}\times \mathbb{Z}/s\mathbb{Z}.$$
على محور دوري طوله \(n\)، تكون التناظرات المسموح بها هي التحويلات التآلفية
$$x\mapsto \sigma x+t \pmod n,\qquad \sigma\in\{1,-1\},\ t\in \mathbb{Z}/n\mathbb{Z}.$$
عندما يكون \(n>2\)، فإن عدد هذه التحويلات يساوي \(2n\). أما عند \(n=1\) و\(n=2\)، فإن بعض التحويلات تتطابق، ولذلك تتعامل معها الخوارزمية بشكل صريح ومنفصل.
إذا كان \(\sigma=1\) فنحن أمام إزاحات خالصة. وإذا كانت رتبة الإزاحة هي \(u\)، فإنها تفكّك المحور إلى \(n/u\) دورات طول كل منها \(u\). وعدد الإزاحات ذات الرتبة \(u\) يساوي \(\varphi(u)\)، لأن
$$u=\frac{n}{\gcd(n,t)}.$$
لذلك يولّد كل قاسم \(u\mid n\) صنفَ إزاحةٍ بكثرة \(\varphi(u)\) وبملف دورات
$$u^{\,n/u}.$$
أما إذا كان \(\sigma=-1\) فنحصل على عمليات العكس. وإذا كان \(n\) فرديًا فملف الدورات هو \(1^1\,2^{(n-1)/2}\). وإذا كان \(n\) زوجيًا فهناك فئتان: إحداهما ذات الملف \(1^2\,2^{(n-2)/2}\)، والأخرى ذات الملف \(2^{n/2}\).
والسبب هو معادلة النقاط الثابتة \(2x\equiv t\pmod n\): إذا كان \(n\) فرديًا فلها حل وحيد، وإذا كان زوجيًا فلها حلان أو لا حل لها بحسب زوجية \(t\).
لتكن \(\Gamma_r\) و\(\Gamma_s\) مجموعتي التناظر على المحورين. والتلوين هو دالة
$$f:X_{r,s}\to \{1,2,\dots,q\}.$$
لكل \((g,h)\in \Gamma_r\times \Gamma_s\)، نرمز بـ \(c(g,h)\) إلى عدد الدورات في التبديل الناتج على مجموعة الخلايا \(X_{r,s}\). إذا كان التلوين ثابتًا تحت \((g,h)\)، فلا بد أن يكون ثابتًا على كل دورة. إذن عدد التلوينات الثابتة التي تستعمل كل الألوان هو عدد التطبيقات الشمولية من مجموعة مكوّنة من \(c(g,h)\) دورات إلى مجموعة الألوان \(q\).
وبحسب مبدأ الإدراج والاستبعاد، يكون هذا العدد
$$\operatorname{Surj}(c,q)=\sum_{j=0}^{q}(-1)^j\binom{q}{j}(q-j)^c.$$
ومن ثم تعطي لمّة برنسايد
$$A_q(r,s)=\frac{1}{|\Gamma_r|\,|\Gamma_s|}\sum_{g\in\Gamma_r}\sum_{h\in\Gamma_s}\operatorname{Surj}(c(g,h),q).$$
هذه الصيغة صحيحة تمامًا، لكن جعلها سريعة يتطلب ضغط عناصر التناظر بحسب ملفات الدورات.
افترض أن تناظرًا على المحور الأول يحتوي على \(m_i\) دورات طولها \(\ell_i\)، وأن تناظرًا على المحور الثاني يحتوي على \(n_j\) دورات طولها \(r_j\). عند النظر إلى حاصل الضرب الديكارتي لدورة بطول \(\ell_i\) مع دورة بطول \(r_j\)، فإن الحركة تتم بالتزامن على الاتجاهين.
طول المدار الواحد هو \(\operatorname{lcm}(\ell_i,r_j)\)، ولذا فإن \(\ell_i r_j\) نقطة تنقسم إلى
$$\frac{\ell_i r_j}{\operatorname{lcm}(\ell_i,r_j)}=\gcd(\ell_i,r_j)$$
دورات في فضاء الضرب. وبجمع ذلك على جميع الأزواج نحصل على
$$c(g,h)=\sum_i\sum_j m_i n_j\,\gcd(\ell_i,r_j).$$
وهذه هي الصيغة المحورية التي تحوّل ملفي دورات أحاديي البعد إلى عدد الدورات في النمط الثنائي البعد كاملًا.
جميع عناصر المجموعة التي تملك ملف الدورات نفسه تعطي العدد نفسه من التلوينات الثابتة، ولذلك يمكن إعادة كتابة مجموع برنسايد على مستوى الأصناف بدل العناصر المفردة.
لمحور طوله \(n\)، لا تحتاج الخوارزمية إلا إلى
$$\tau(n)+O(1)$$
من الملفات المختلفة: ملف إزاحة واحد لكل قاسم من قواسم \(n\)، ثم ملف واحد أو ملفان لعمليات العكس بحسب الزوجية. وتكون الكثرات \(\varphi(u)\) في أصناف الإزاحة، أما في أصناف العكس فتُستنتج مباشرة من الحالة الفردية أو الزوجية.
هذا الضغط هو سبب السرعة الحقيقية للطريقة. ففي المدخلات الفعلية المبنية على فيبوناتشي، يكون عدد أزواج الأصناف صغيرًا جدًا مقارنةً بالحجم الخام لمجموعة التناظرات.
تظهر هذه القيمة كنقطة تحقق داخل التنفيذ، وهي صغيرة بما يكفي للحساب اليدوي الكامل.
عندما يكون الطول \(2\)، توجد فئتان: الملف \(1^2\) بكثرة \(1\)، والملف \(2^1\) بكثرة \(1\).
وعندما يكون الطول \(3\)، توجد ثلاث فئات: الملف \(1^3\) بكثرة \(1\)، والملف \(3^1\) بكثرة \(2\)، والملف \(1^1 2^1\) بكثرة \(3\).
ولأن \(q=2\)، فإن عدد التطبيقات الشمولية يختزل إلى
$$\operatorname{Surj}(c,2)=2^c-2.$$
وباستخدام صيغة دورات الضرب، نحصل على الأزواج الستة التالية:
$$\begin{aligned} c(1^2,1^3)&=6, & \operatorname{mult}&=1,\\ c(1^2,3^1)&=2, & \operatorname{mult}&=2,\\ c(1^2,1^1 2^1)&=4, & \operatorname{mult}&=3,\\ c(2^1,1^3)&=3, & \operatorname{mult}&=1,\\ c(2^1,3^1)&=1, & \operatorname{mult}&=2,\\ c(2^1,1^1 2^1)&=3, & \operatorname{mult}&=3. \end{aligned}$$
إذن بسط متوسط برنسايد الموزون يساوي
$$1\cdot 62+2\cdot 2+3\cdot 14+1\cdot 6+2\cdot 0+3\cdot 6=132.$$
ومع \(|\Gamma_2|=2\) و\(|\Gamma_3|=6\) نحصل على
$$A_2(2,3)=\frac{132}{2\cdot 6}=11.$$
بعد الحصول على العدّ المضغوط \(A_q(r,s)\)، لا يبقى في المسألة 651 إلا التعويض بـ
$$q=t,\qquad r=F_{t-1},\qquad s=F_t,\qquad 4\le t\le 40,$$
ثم جمع القيم بترديد \(10^9+7\):
$$\boxed{\sum_{t=4}^{40} A_t(F_{t-1},F_t)\pmod{10^9+7}.}$$
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. أولًا تُبنى معاملات ثنائية الحد اللازمة لصيغة الإدراج والاستبعاد، وتُحسب القوى \((q-j)^c\) بواسطة الرفع السريع modulo.
ثم لكل طول من الطولين الدوريين، تقوم الخوارزمية بتحليل العدد إلى عوامله، وتوليد قواسمه، وتحويل هذه القواسم إلى أصناف إزاحة بكثرات \(\varphi(u)\)، ثم تضيف أصناف العكس المرتبطة بزوجية الطول. أما الحالتان الصغيرتان \(1\) و\(2\) فتعالجان بشكل صريح.
بعد ذلك تمرّ الخوارزمية على كل زوج من الأصناف الآتية من المحورين. ولكل زوج تحسب عدد الدورات الكلي باستخدام صيغة \(\gcd\). وبما أن كثيرًا من الأزواج المختلفة يعطي العدد نفسه من الدورات، فإن قيمة \(\operatorname{Surj}(c,q)\) تُخزَّن مؤقتًا بحسب \(c\) وتُعاد الاستفادة منها.
كل مساهمة في مجموع برنسايد تساوي حاصل ضرب كثرتي الصنفين في عدد التطبيقات الشمولية المخزّن. وبعد جمع جميع المساهمات، يُقسم الناتج على حجم المجموعة باستخدام المعكوس الضربي modulo، ثم يُضاف إلى المجموع النهائي عبر قيم فيبوناتشي.
في الحالة العامة \(A_q(r,s)\)، يكلف تحليل الطولين بالقسمة التجريبية في هذه التطبيقات \(O(\sqrt{r}+\sqrt{s})\) زمنًا. وإذا رمزنا بعدد أصناف التناظر على المحورين بـ \(K(r)\) و\(K(s)\)، فإن حلقة برنسايد الرئيسة تستخدم \(O(K(r)K(s))\) من أزواج الأصناف.
كل ملف صنف يحتوي على طول دورة واحد أو طولين فقط، لذلك فإن حساب دورات الضرب لزوج واحد يتم في \(O(1)\). وكل عدد دورات جديد يطلق حساب إدراج واستبعاد واحدًا بكلفة \(O(q)\)، لكن في المسألة 651 لدينا دومًا \(q\le 40\)، كما أن عددًا كبيرًا من أزواج الأصناف يشترك في القيمة نفسها. أما الذاكرة فتبلغ \(O(K(r)+K(s)+U+q^2)\)، حيث \(U\) هو عدد قيم الدورات المختلفة المخزنة مؤقتًا. عمليًا تبقى هذه الكلفة صغيرة جدًا قياسًا إلى فضاء التلوينات الخام.