Problem 781 asks for a large modular value \(F(n)\) associated with counting Feynman-diagram configurations. The implementations reveal the structural facts that matter computationally: the modulus is \(10^9+7\), odd values of \(n\) contribute nothing, and the first nontrivial checkpoints are
$$F(4)=5,\qquad F(8)=319.$$
Instead of enumerating diagrams directly, the solution compresses the count into a one-dimensional profile that evolves only when \(n\) increases by \(2\). That recurrence is the real mathematical core of the program.
Write \(n=2m\) for even inputs. The implementation maintains a profile \(A_m(j)\) indexed by a positive integer \(j\). The zeroth slot is unused, so only \(j\ge 1\) matters. For odd inputs, the answer is immediately
$$F(2m+1)=0.$$
The base layer corresponds to \(n=2\), that is \(m=1\). At this level the profile has a single nonzero entry:
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
So the positive-index profile is simply
$$A_1=(0,1).$$
Every later even level is produced from the previous one by the same two deterministic transforms. If the current level is \(n=2m\), then the support of the profile lies in \(1\le j\le 2m\).
First, the current profile is replaced by its suffix sums. Define
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m).$$
This means each position \(j\) receives the total mass from all positions at least \(j\). In matrix terms this is an upper-triangular transform with ones on and above the diagonal. It is implemented by a single backward scan, which is why the code walks from right to left.
After the suffix pass, the new layer is extended by two additional indices. Then every old entry \(A_m(j)\) contributes an extra weighted term to position \(j+2\):
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
So the shift is not uniform; it carries the coefficient \(j+1\). This weighted injection is exactly what makes the recurrence quadratic-time rather than a trivial cumulative sum.
If we adopt the convention \(A_m(r)=0\) whenever \(r\le 0\) or \(r>2m\), then the two transforms merge into a single formula for the next even layer:
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
The first term is the suffix accumulation, and the second term is the shifted weighted injection rewritten with \(j\) as the destination index. This recurrence is the complete mathematical description of the implemented transition.
Once the target even layer has been built, the answer is the sum of the profile entries:
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
There is also a useful consistency identity for the next layer. Summing the recurrence over \(j\) gives
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j).$$
This is not how the implementation stores the state, but it is a clean way to verify that the transition and the final summation agree.
Start from
$$A_1=(0,1).$$
For \(n=4\), the suffix profile is
$$S_1=(1,1),$$
and the weighted shift adds \(3\) to the fourth position. Therefore
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
Applying the same rule again gives
$$S_2=(5,4,3,3),$$
followed by shifted additions \(2,3,0,15\) into positions \(3,4,5,6\). Hence
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
One more transition yields
$$S_3=(35,30,26,21,15,15),$$
and the extra shifted contributions are \(10,12,20,30,0,105\). Thus
$$A_4=(35,30,36,33,35,45,0,105),$$
so
$$F(8)=35+30+36+33+35+45+0+105=319,$$
exactly matching the checkpoint embedded in the implementations.
The C++ implementation stores the current even-layer profile in a dynamic array. If the requested \(n\) is odd, it returns \(0\) immediately. Otherwise it starts from the base layer for \(n=2\), repeats the transition for \(n=4,6,\dots\), and reduces every arithmetic operation modulo \(10^9+7\).
Each transition consists of four practical steps: copy the current profile, run a backward pass to convert that copy into suffix sums, enlarge the storage by two cells, and inject the weighted \((j+1)\)-scaled contributions into positions shifted by \(2\). After the last even layer is reached, the implementation sums the entire profile to obtain \(F(n)\).
The C++, Python, and Java implementations all rely on the same recurrence. The Python and Java versions act as thin wrappers around the compiled C++ computation, then parse the emitted integer. They therefore inherit the same parity rule, the same checkpoints \(F(4)=5\) and \(F(8)=319\), and the same asymptotic cost as the C++ core.
Let \(n=2m\). The profile length grows linearly: at level \(2,4,6,\dots,2m\) it has \(3,5,7,\dots,2m+1\) slots including the unused zeroth slot. A single transition processes the current layer with one backward suffix scan and one forward weighted-shift scan, so each layer costs \(O(m)\) time at its own scale. Summing over all even layers gives
$$O(1+2+\cdots+m)=O(m^2)=O(n^2).$$
Only the current layer and the next layer are stored, so the memory use is linear:
$$O(m)=O(n).$$
Problem 781 verlangt einen großen modularen Wert \(F(n)\), der mit dem Zählen von Feynman-Diagramm-Konfigurationen zusammenhängt. Aus den Implementierungen lassen sich die für die Berechnung entscheidenden Strukturmerkmale direkt ablesen: Der Modul ist \(10^9+7\), für ungerade \(n\) ist der Beitrag immer \(0\), und die ersten nichttrivialen Kontrollwerte sind
$$F(4)=5,\qquad F(8)=319.$$
Die Lösung zählt die Diagramme nicht direkt. Stattdessen komprimiert sie alle relevanten Informationen in ein eindimensionales Profil, das nur dann fortgeschrieben wird, wenn \(n\) um \(2\) steigt. Genau diese Rekursion ist der mathematische Kern des Programms.
Für gerade Eingaben schreiben wir \(n=2m\). Die Implementierung verwaltet ein Profil \(A_m(j)\), das durch einen positiven Index \(j\) parametrisiert wird. Der Index \(0\) bleibt unbenutzt, also zählt nur \(j\ge 1\). Für ungerade Eingaben gilt sofort
$$F(2m+1)=0.$$
Die Basisschicht entspricht \(n=2\), also \(m=1\). Dort besitzt das Profil genau einen von null verschiedenen Eintrag:
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
Als Liste der positiven Indizes ist das einfach
$$A_1=(0,1).$$
Jede spätere gerade Ebene entsteht aus der vorherigen durch dieselben zwei linearen Transformationen. Ist die aktuelle Ebene \(n=2m\), dann liegt der Träger des Profils in \(1\le j\le 2m\).
Zuerst wird das aktuelle Profil durch seine Suffixsummen ersetzt. Dazu definieren wir
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m).$$
Jede Position \(j\) erhält also die gesamte Masse aller Positionen \(t\ge j\). Matrixartig betrachtet ist das eine obere Dreieckstransformation mit Einsen auf und oberhalb der Diagonale. Deshalb läuft der Code in diesem Schritt von rechts nach links.
Nach dem Suffix-Schritt wird die neue Ebene um zwei weitere Indizes erweitert. Danach trägt jeder alte Wert \(A_m(j)\) zusätzlich einen gewichteten Term zur Position \(j+2\) bei:
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
Die Verschiebung ist also nicht uniform, sondern mit dem Faktor \(j+1\) gewichtet. Genau diese Einspeisung macht die Rekursion inhaltlich interessanter als eine bloße kumulative Summe.
Verwenden wir die Konvention \(A_m(r)=0\), sobald \(r\le 0\) oder \(r>2m\), dann lassen sich beide Teiloperationen in einer einzigen Formel schreiben:
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
Der erste Summand ist die Suffix-Akkumulation, der zweite Summand ist dieselbe gewichtete Verschiebung, nur in der Zielindex-Notation formuliert. Diese Rekursion beschreibt den tatsächlich implementierten Übergang vollständig.
Ist die gewünschte gerade Ebene aufgebaut, dann ist die Antwort einfach die Summe aller Profileinträge:
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
Nützlich ist außerdem eine Kontrollidentität für die nächste Ebene. Summiert man die Rekursion über alle \(j\), so erhält man
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j).$$
So sieht man kompakt, dass Übergang und Endsumme konsistent zusammenspielen.
Wir starten mit
$$A_1=(0,1).$$
Für \(n=4\) ist das Suffixprofil
$$S_1=(1,1),$$
und die gewichtete Verschiebung addiert \(3\) an der vierten Position. Also
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
Wendet man dieselbe Regel nochmals an, ergibt sich
$$S_2=(5,4,3,3),$$
gefolgt von Zusatzbeiträgen \(2,3,0,15\) in die Positionen \(3,4,5,6\). Damit
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
Ein weiterer Übergang liefert
$$S_3=(35,30,26,21,15,15),$$
und die zusätzlichen verschobenen Beiträge sind \(10,12,20,30,0,105\). Somit
$$A_4=(35,30,36,33,35,45,0,105),$$
also
$$F(8)=35+30+36+33+35+45+0+105=319,$$
genau wie im Kontrollwert der Implementierungen.
Die C++-Implementierung speichert das aktuelle Profil der geraden Ebene in einem dynamischen Array. Ist das angeforderte \(n\) ungerade, gibt sie sofort \(0\) zurück. Andernfalls beginnt sie mit der Basisschicht für \(n=2\), wiederholt den Übergang für \(n=4,6,\dots\) und reduziert jede Rechnung modulo \(10^9+7\).
Jeder Übergang besteht praktisch aus vier Schritten: Das aktuelle Profil wird kopiert, diese Kopie wird durch einen Rückwärtslauf in Suffixsummen umgewandelt, der Speicher wird um zwei Zellen erweitert, und anschließend werden die gewichteten \((j+1)\)-Beiträge in die um \(2\) verschobenen Zielpositionen eingespeist. Ist die letzte gerade Ebene erreicht, summiert die Implementierung das gesamte Profil und erhält so \(F(n)\).
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Rekursion. Die Python- und Java-Versionen sind nur schlanke Hüllen um die kompilierte C++-Berechnung und parsen anschließend die ausgegebene ganze Zahl. Dadurch teilen alle drei Sprachen dieselbe Paritätsregel, dieselben Kontrollwerte \(F(4)=5\) und \(F(8)=319\) sowie dieselbe asymptotische Komplexität.
Sei \(n=2m\). Die Profillänge wächst linear: auf den Ebenen \(2,4,6,\dots,2m\) besitzt sie einschließlich des unbenutzten Nullindex \(3,5,7,\dots,2m+1\) Einträge. Ein einzelner Übergang benötigt einen Rückwärtslauf für die Suffixsummen und einen Vorwärtslauf für die gewichtete Verschiebung, also auf seiner Ebene \(O(m)\) Zeit. Über alle geraden Ebenen summiert sich das zu
$$O(1+2+\cdots+m)=O(m^2)=O(n^2).$$
Gespeichert werden nur die aktuelle und die nächste Ebene, daher ist der Speicherverbrauch linear:
$$O(m)=O(n).$$
Problem 781, Feynman diyagramı yapılarını sayan bir fonksiyona ait büyük bir \(F(n)\) değerini modüler olarak istemektedir. Uygulamalardan doğrudan görülen hesaplama gerçekleri şunlardır: modül \(10^9+7\)'dir, tek \(n\) değerleri hiçbir katkı vermez ve ilk anlamlı kontrol değerleri
$$F(4)=5,\qquad F(8)=319.$$
Çözüm diyagramları tek tek üretmez. Bunun yerine tüm sayımı, sadece \(n\) değeri \(2\) arttığında güncellenen tek boyutlu bir profil içine sıkıştırır. Programın matematiksel özü bu yinelemedir.
Çift girdiler için \(n=2m\) yazalım. Uygulama, pozitif bir \(j\) indeksiyle tanımlanan \(A_m(j)\) profilini tutar. Sıfırıncı hücre kullanılmaz; dolayısıyla yalnızca \(j\ge 1\) önemlidir. Tek girdiler için cevap doğrudan
$$F(2m+1)=0$$
olur.
Taban katman \(n=2\), yani \(m=1\) durumudur. Bu seviyede profilin tek sıfır olmayan terimi vardır:
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
Pozitif indeksler boyunca yazarsak
$$A_1=(0,1).$$
Daha sonraki her çift katman, bundan önceki katmandan aynı iki doğrusal dönüşümle elde edilir. Mevcut seviye \(n=2m\) ise profil desteği \(1\le j\le 2m\) aralığındadır.
Önce mevcut profil sonek toplamlarına dönüştürülür. Bunun için
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m)$$
tanımını yaparız. Böylece her \(j\) konumu, kendisinden sağda veya aynı yerde duran tüm kütleyi toplar. Matris dilinde bu, köşegenin üzerinde ve üzerinde birlerle dolu üst üçgensel bir dönüşümdür. Kodun bu aşamada sağdan sola ilerlemesinin nedeni budur.
Sonek geçişinden sonra yeni katman iki ek indisle genişletilir. Ardından eski profildeki her \(A_m(j)\) değeri, \(j+2\) konumuna ağırlıklı bir katkı yapar:
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
Yani öteleme sabit değildir; katsayı \(j+1\) ile gelir. Hesabın içindeki asıl zenginlik bu ağırlıklı enjeksiyondan doğar.
\(r\le 0\) veya \(r>2m\) olduğunda \(A_m(r)=0\) kabul edersek, iki ayrı işlem tek bir formülde birleşir:
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
İlk terim sonek birikimidir; ikinci terim ise hedef indeksle yazılmış ağırlıklı ötelemedir. Programın gerçekten uyguladığı geçiş bu yinelemedir.
Hedef çift katman üretildiğinde cevap, profil terimlerinin toplamıdır:
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
Bir sonraki katman için kullanışlı bir doğrulama özdeşliği de vardır. Yinelemeyi tüm \(j\) değerleri üzerinde toplarsak
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j)$$
elde edilir. Bu, geçiş ile nihai toplamın birbiriyle tutarlı olduğunu gösteren temiz bir kontroldür.
Başlangıçta
$$A_1=(0,1)$$
vardır. \(n=4\) için sonek profili
$$S_1=(1,1)$$
olur ve ağırlıklı öteleme dördüncü konuma \(3\) ekler. Dolayısıyla
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
Aynı kuralı bir kez daha uygularsak
$$S_2=(5,4,3,3)$$
elde edilir; buna ek olarak \(3,4,5,6\) konumlarına sırasıyla \(2,3,0,15\) eklenir. Böylece
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
Bir geçiş daha sonra
$$S_3=(35,30,26,21,15,15)$$
olur ve ek ötelemeli katkılar \(10,12,20,30,0,105\) şeklindedir. Sonuçta
$$A_4=(35,30,36,33,35,45,0,105)$$
ve dolayısıyla
$$F(8)=35+30+36+33+35+45+0+105=319,$$
ki bu da uygulamadaki kontrol değeriyle aynıdır.
C++ uygulaması mevcut çift-seviye profilini dinamik bir dizide tutar. İstenen \(n\) tekse anında \(0\) döndürür. Aksi halde \(n=2\) için taban profilden başlar, \(n=4,6,\dots\) seviyeleri boyunca geçişi tekrarlar ve tüm işlemleri \(10^9+7\) modunda yapar.
Her geçiş pratikte dört adımdır: mevcut profil kopyalanır, bu kopya geriye doğru taranarak sonek toplamlarına çevrilir, depolama iki hücre büyütülür ve eski katmandan gelen ağırlıklı \((j+1)\) katkıları \(2\) ötelenmiş konumlara eklenir. Son çift katmana ulaşıldığında tüm profil toplanır ve \(F(n)\) elde edilir.
C++, Python ve Java uygulamalarının dayandığı matematik aynıdır. Python ve Java sürümleri, derlenmiş C++ hesabını çağıran ince köprülerdir ve sonunda yazdırılan tamsayıyı ayrıştırırlar. Bu yüzden üç dil de aynı parite kuralını, aynı \(F(4)=5\) ve \(F(8)=319\) kontrol noktalarını ve aynı asimptotik maliyeti paylaşır.
\(n=2m\) olsun. Profil uzunluğu doğrusal büyür: \(2,4,6,\dots,2m\) seviyelerinde, kullanılmayan sıfırıncı hücre dahil toplam uzunluk \(3,5,7,\dots,2m+1\) olur. Tek bir geçiş, bir geri sonek taraması ve bir ileri ağırlıklı öteleme taraması yaptığı için kendi ölçeğinde \(O(m)\) zaman gerektirir. Tüm çift katmanlarda toplam süre
$$O(1+2+\cdots+m)=O(m^2)=O(n^2)$$
olur. Sadece mevcut ve bir sonraki katman tutulduğu için bellek kullanımı doğrusaldır:
$$O(m)=O(n).$$
El problema 781 pide un valor modular grande \(F(n)\) asociado al conteo de configuraciones de diagramas de Feynman. Las implementaciones dejan ver los hechos estructurales que realmente importan: el módulo es \(10^9+7\), los valores impares de \(n\) no aportan nada y los primeros puntos de control no triviales son
$$F(4)=5,\qquad F(8)=319.$$
La solución no enumera diagramas de manera explícita. En su lugar comprime todo el conteo en un perfil unidimensional que solo evoluciona cuando \(n\) aumenta en \(2\). Esa recurrencia es el núcleo matemático del programa.
Para entradas pares escribimos \(n=2m\). La implementación mantiene un perfil \(A_m(j)\) indexado por un entero positivo \(j\). La posición \(0\) no se usa, de modo que solo importa \(j\ge 1\). Para entradas impares, la respuesta es inmediatamente
$$F(2m+1)=0.$$
La capa base corresponde a \(n=2\), es decir, \(m=1\). En ese nivel el perfil tiene una única entrada no nula:
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
Como lista de índices positivos, esto es
$$A_1=(0,1).$$
Cada nivel par posterior se obtiene del anterior mediante las mismas dos transformaciones lineales. Si el nivel actual es \(n=2m\), entonces el soporte del perfil está en \(1\le j\le 2m\).
Primero el perfil actual se reemplaza por sus sumas sufijas. Definimos
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m).$$
Eso significa que cada posición \(j\) recibe toda la masa situada en posiciones \(t\ge j\). En términos matriciales es una transformación triangular superior con unos en la diagonal y por encima de ella. Por eso el código ejecuta esta fase recorriendo el arreglo de derecha a izquierda.
Después de la pasada de sufijos, la nueva capa se amplía con dos índices adicionales. Entonces cada valor antiguo \(A_m(j)\) aporta un término extra ponderado a la posición \(j+2\):
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
Así, el desplazamiento no es uniforme; viene acompañado por el coeficiente \(j+1\). Esa inyección ponderada es la segunda mitad esencial de la recurrencia.
Si adoptamos la convención \(A_m(r)=0\) cuando \(r\le 0\) o \(r>2m\), entonces las dos operaciones se combinan en la fórmula
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
El primer sumando es la acumulación sufija y el segundo es el mismo desplazamiento ponderado escrito con el índice de destino. Esta ecuación describe por completo la transición usada por la implementación.
Una vez construida la capa par objetivo, la respuesta se obtiene sumando todas las entradas del perfil:
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
También hay una identidad útil de comprobación para la capa siguiente. Al sumar la recurrencia sobre todos los \(j\), resulta
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j).$$
No es la forma en que el programa almacena el estado, pero sí una manera limpia de verificar que la transición y la suma final son coherentes.
Comenzamos con
$$A_1=(0,1).$$
Para \(n=4\), el perfil de sufijos es
$$S_1=(1,1),$$
y el desplazamiento ponderado añade \(3\) en la cuarta posición. Por tanto
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
Aplicando la misma regla otra vez obtenemos
$$S_2=(5,4,3,3),$$
seguido por aportes extra \(2,3,0,15\) en las posiciones \(3,4,5,6\). Entonces
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
Una transición más produce
$$S_3=(35,30,26,21,15,15),$$
y las contribuciones desplazadas adicionales son \(10,12,20,30,0,105\). Así
$$A_4=(35,30,36,33,35,45,0,105),$$
de modo que
$$F(8)=35+30+36+33+35+45+0+105=319,$$
exactamente el valor de control codificado en las implementaciones.
La implementación en C++ guarda el perfil actual del nivel par en un arreglo dinámico. Si el \(n\) solicitado es impar, devuelve \(0\) de inmediato. En caso contrario empieza en la capa base para \(n=2\), repite la transición para \(n=4,6,\dots\) y reduce cada operación módulo \(10^9+7\).
Cada transición tiene cuatro fases prácticas: copiar el perfil actual, recorrer esa copia hacia atrás para convertirla en sumas sufijas, ampliar el almacenamiento en dos celdas y añadir las contribuciones ponderadas \((j+1)\) en las posiciones desplazadas en \(2\). Cuando se alcanza la última capa par, la implementación suma todo el perfil y obtiene \(F(n)\).
Las implementaciones en C++, Python y Java dependen de la misma recurrencia. Las versiones en Python y Java actúan como envolturas ligeras alrededor del cálculo compilado en C++ y luego extraen el entero impreso. Por eso los tres lenguajes comparten la misma regla de paridad, los mismos puntos de control \(F(4)=5\) y \(F(8)=319\), y el mismo costo asintótico que domina la solución.
Sea \(n=2m\). La longitud del perfil crece linealmente: en los niveles \(2,4,6,\dots,2m\) tiene \(3,5,7,\dots,2m+1\) posiciones contando la casilla \(0\), que no se usa. Una transición procesa la capa actual con un barrido sufijo hacia atrás y un barrido de desplazamiento ponderado hacia adelante, así que cada nivel cuesta \(O(m)\) en su propia escala. Sumando todas las capas pares se obtiene
$$O(1+2+\cdots+m)=O(m^2)=O(n^2).$$
Solo se almacenan la capa actual y la siguiente, por lo que la memoria es lineal:
$$O(m)=O(n).$$
第 781 题要求计算一个与 Feynman 图计数相关的大规模模值 \(F(n)\)。从实现本身可以直接读出真正影响算法设计的结构事实：模数固定为 \(10^9+7\)，奇数 \(n\) 的答案恒为 \(0\)，而最早的两个非平凡校验点是
$$F(4)=5,\qquad F(8)=319.$$
程序并不直接枚举所有图，而是把计数信息压缩成一个一维剖面，并且只在 \(n\) 每次增加 \(2\) 时更新这个剖面。这个偶数层递推就是整份解法的数学核心。
对于偶数输入，写成 \(n=2m\)。实现维护一个按正整数 \(j\) 编号的剖面 \(A_m(j)\)。第 \(0\) 个位置始终不用，因此只有 \(j\ge 1\) 有意义。若输入为奇数，则答案立刻是
$$F(2m+1)=0.$$
基底层对应 \(n=2\)，也就是 \(m=1\)。此时剖面只有一个非零项：
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
如果只写正下标部分，那么它就是
$$A_1=(0,1).$$
之后每一层偶数状态都由前一层通过完全相同的两步线性变换得到。若当前层是 \(n=2m\)，则剖面的支撑范围位于 \(1\le j\le 2m\)。
第一步把当前剖面替换成它的后缀和。定义
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m).$$
这表示位置 \(j\) 收集了所有下标不小于 \(j\) 的质量。若从线性代数角度看，这是一个上三角变换，主对角线及其上方全是 \(1\)。这也解释了为什么实现要从右向左扫描数组。
做完后缀和以后，新层会额外扩展出两个位置。然后旧层中的每个值 \(A_m(j)\) 都会向位置 \(j+2\) 注入一个加权贡献：
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
因此这不是简单的平移，而是带有系数 \(j+1\) 的加权平移。正是这个部分使得转移不仅仅是普通的累加，而具有更丰富的组合结构。
若约定当 \(r\le 0\) 或 \(r>2m\) 时有 \(A_m(r)=0\)，那么两步更新可以合并为一条公式：
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
第一项对应后缀累加，第二项对应用目标下标表示后的加权平移。也就是说，这条递推式已经完整描述了程序在相邻偶数层之间做的事情。
目标偶数层构造完成后，所需的值就是全部剖面项之和：
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
此外，对下一层还有一条很有用的校验恒等式。把上面的递推对所有 \(j\) 求和，可以得到
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j).$$
程序内部并不是按这个式子存状态，但它非常适合用来检查转移公式和最终求和是否彼此一致。
起始剖面为
$$A_1=(0,1).$$
当 \(n=4\) 时，后缀剖面是
$$S_1=(1,1),$$
然后加权平移会在第 \(4\) 个位置再加上 \(3\)。因此
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
再应用一次同样的规则，有
$$S_2=(5,4,3,3),$$
并且向位置 \(3,4,5,6\) 额外注入 \(2,3,0,15\)。于是
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
再做一次转移，则得到
$$S_3=(35,30,26,21,15,15),$$
额外平移贡献为 \(10,12,20,30,0,105\)。所以
$$A_4=(35,30,36,33,35,45,0,105),$$
从而
$$F(8)=35+30+36+33+35+45+0+105=319,$$
与实现中的校验值完全一致。
C++ 实现把当前偶数层的剖面保存在一个动态数组中。如果请求的 \(n\) 是奇数，就直接返回 \(0\)。否则它从 \(n=2\) 的基底剖面开始，依次推进 \(n=4,6,\dots\) 的各层，并在每一步都对 \(10^9+7\) 取模。
一次完整转移分为四个实际动作：先复制当前剖面，再从右向左把副本改写成后缀和，然后把存储空间扩展两个位置，最后把来自旧层的 \((j+1)\) 加权贡献注入到向右平移 \(2\) 的目标位置上。到达最终偶数层以后，程序把整个剖面求和，得到 \(F(n)\)。
C++、Python 和 Java 三份实现依赖的是同一套递推。Python 和 Java 版本本质上都是对编译后 C++ 计算核心的轻量封装，最后再解析输出的整数。因此三种语言共享相同的奇偶性规则、相同的校验点 \(F(4)=5\) 与 \(F(8)=319\)，以及由 C++ 核心主导的同一复杂度。
设 \(n=2m\)。剖面长度线性增长：在层 \(2,4,6,\dots,2m\) 上，连同未使用的第 \(0\) 位在内，长度分别是 \(3,5,7,\dots,2m+1\)。一次转移包含一次向后的后缀扫描和一次向前的加权平移扫描，所以在对应层级上的时间代价是 \(O(m)\)。把所有偶数层累加起来，得到
$$O(1+2+\cdots+m)=O(m^2)=O(n^2).$$
程序只保存当前层和下一层，因此空间复杂度为线性：
$$O(m)=O(n).$$
Задача 781 просит вычислить большое значение \(F(n)\) по модулю, связанное с подсчетом конфигураций диаграмм Фейнмана. Из самих реализаций можно извлечь ключевые вычислительные факты: модуль равен \(10^9+7\), для нечетных \(n\) ответ всегда равен \(0\), а первые нетривиальные контрольные значения таковы:
$$F(4)=5,\qquad F(8)=319.$$
Программа не перечисляет диаграммы напрямую. Вместо этого она сжимает всю информацию в одномерный профиль, который обновляется только при переходе от \(n\) к \(n+2\). Именно эта рекуррентная схема и является математическим ядром решения.
Для четных входов пишем \(n=2m\). Реализация хранит профиль \(A_m(j)\), индексируемый положительным целым \(j\). Нулевая позиция не используется, поэтому существенны только \(j\ge 1\). Для нечетных входов сразу имеем
$$F(2m+1)=0.$$
Базовый слой соответствует \(n=2\), то есть \(m=1\). На этом уровне у профиля только один ненулевой элемент:
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
Если записать только положительные индексы, то профиль имеет вид
$$A_1=(0,1).$$
Каждый следующий четный слой получается из предыдущего одними и теми же двумя линейными преобразованиями. Если текущий слой равен \(n=2m\), то носитель профиля лежит в диапазоне \(1\le j\le 2m\).
Сначала текущий профиль заменяется своими суффиксными суммами. Введем
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m).$$
Это означает, что позиция \(j\) получает всю массу из позиций с индексами не меньше \(j\). В матричной форме это верхнетреугольное преобразование с единицами на диагонали и выше нее. Поэтому код и выполняет этот проход справа налево.
После суффиксного прохода новый слой расширяется еще на два индекса. Затем каждое старое значение \(A_m(j)\) дает дополнительный вклад в позицию \(j+2\):
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
Следовательно, сдвиг не является равномерным: он сопровождается коэффициентом \(j+1\). Эта взвешенная инъекция и составляет вторую существенную часть перехода.
Если принять соглашение \(A_m(r)=0\) при \(r\le 0\) или \(r>2m\), то обе операции складываются в единую формулу:
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
Первое слагаемое отвечает за суффиксное накопление, второе является тем же взвешенным сдвигом, но уже записанным через целевой индекс. Эта формула полностью описывает реализованный переход.
После построения нужного четного слоя ответ равен сумме всех элементов профиля:
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
Есть и удобная проверочная формула для следующего слоя. Если просуммировать рекурсию по всем \(j\), получится
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j).$$
Программа не хранит состояние в таком виде, но эта идентичность хорошо показывает согласованность перехода и итогового суммирования.
Начинаем с
$$A_1=(0,1).$$
Для \(n=4\) суффиксный профиль равен
$$S_1=(1,1),$$
после чего взвешенный сдвиг добавляет \(3\) в четвертую позицию. Значит,
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
Еще одно применение того же правила дает
$$S_2=(5,4,3,3),$$
а дополнительные вклады в позиции \(3,4,5,6\) равны \(2,3,0,15\). Поэтому
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
Следующий переход приводит к
$$S_3=(35,30,26,21,15,15),$$
а дополнительные сдвинутые вклады равны \(10,12,20,30,0,105\). Следовательно,
$$A_4=(35,30,36,33,35,45,0,105),$$
и потому
$$F(8)=35+30+36+33+35+45+0+105=319,$$
что в точности совпадает с контрольным значением из реализаций.
Реализация на C++ хранит профиль текущего четного слоя в динамическом массиве. Если запрошенное \(n\) нечетно, она сразу возвращает \(0\). Иначе она стартует с базового слоя для \(n=2\), повторяет переход для \(n=4,6,\dots\) и на каждом шаге выполняет арифметику по модулю \(10^9+7\).
Каждый переход состоит из четырех практических действий: сначала копируется текущий профиль, затем эта копия преобразуется в суффиксные суммы одним проходом справа налево, после этого массив расширяется на две ячейки, и, наконец, в сдвинутые на \(2\) позиции добавляются взвешенные вклады с коэффициентом \((j+1)\). Когда достигнут последний четный слой, реализация суммирует весь профиль и получает \(F(n)\).
Реализации на C++, Python и Java опираются на одну и ту же рекуррентную схему. Версии на Python и Java служат тонкими оболочками вокруг скомпилированного вычисления на C++ и затем разбирают напечатанное целое число. Поэтому все три языка наследуют одно и то же правило четности, те же контрольные точки \(F(4)=5\) и \(F(8)=319\), а также одну и ту же асимптотику, задаваемую C++-ядром.
Пусть \(n=2m\). Длина профиля растет линейно: на слоях \(2,4,6,\dots,2m\) она равна \(3,5,7,\dots,2m+1\), если считать и неиспользуемый нулевой индекс. Один переход выполняет один обратный суффиксный проход и один прямой проход для взвешенного сдвига, поэтому на своем масштабе стоит \(O(m)\) времени. Суммируя по всем четным слоям, получаем
$$O(1+2+\cdots+m)=O(m^2)=O(n^2).$$
Хранятся только текущий и следующий слои, так что память линейна:
$$O(m)=O(n).$$
تطلب المسألة 781 حساب قيمة كبيرة \(F(n)\) بترديد معياري، وهي مرتبطة بعدّ تراكيب من نوع مخططات فاينمان. ويمكن استخلاص الحقائق البنيوية المهمة حسابيًا مباشرة من التنفيذات: الترديد هو \(10^9+7\)، والقيم الفردية لـ \(n\) تعطي دائمًا صفرًا، وأول قيمتي تحقق غير تافهتين هما
$$F(4)=5,\qquad F(8)=319.$$
لا يقوم الحل بتعداد المخططات واحدًا واحدًا، بل يضغط عملية العد كلها في هيئة ملف أحادي البعد يتطور فقط عندما تزداد \(n\) بمقدار \(2\). وهذه العلاقة التكرارية هي لب الفكرة الرياضية في البرنامج.
للمدخلات الزوجية نكتب \(n=2m\). يحتفظ التنفيذ بملف حالته \(A_m(j)\) المفهرس بعدد صحيح موجب \(j\). أما الخانة ذات الفهرس \(0\) فلا تُستخدم، لذلك لا يهم إلا \(j\ge 1\). وإذا كانت قيمة الإدخال فردية فإن الجواب مباشرة هو
$$F(2m+1)=0.$$
تمثل الطبقة الأساسية الحالة \(n=2\)، أي \(m=1\). وفي هذه الطبقة يوجد حد غير صفري واحد فقط:
$$A_1(2)=1,\qquad A_1(j)=0\quad (j\ne 2).$$
وعند كتابة القيم ذات الفهارس الموجبة فقط يصبح الملف
$$A_1=(0,1).$$
كل طبقة زوجية لاحقة تُبنى من الطبقة السابقة باستعمال التحويلين الخطيين نفسيهما. وإذا كانت الطبقة الحالية هي \(n=2m\)، فإن مجال الدعم غير الصفري يقع داخل \(1\le j\le 2m\).
أولًا يُستبدل الملف الحالي بمجاميعه الذيلية. نعرّف
$$S_m(j)=\sum_{t=j}^{2m} A_m(t)\qquad (1\le j\le 2m).$$
وهذا يعني أن الموضع \(j\) يستقبل كامل الكتلة الموجودة في جميع المواضع ذات الفهرس الأكبر منه أو المساوي له. وبصياغة مصفوفية فهذا تحويل مثلثي علوي تحوي قطراه وما فوقه الواحدات، ولهذا ينفذ الكود هذا الجزء بمسح عكسي من اليمين إلى اليسار.
بعد خطوة الذيل، تُزاد الطبقة الجديدة بموضعين إضافيين. ثم تساهم كل قيمة قديمة \(A_m(j)\) بمقدار موزون في الموضع \(j+2\):
$$\Delta_{m+1}(j+2)=(j+1)A_m(j).$$
إذًا ليست هذه مجرد إزاحة ثابتة، بل إزاحة مصحوبة بالمعامل \(j+1\). وهذه الإضافة الموزونة هي النصف الثاني الأساسي من الانتقال.
إذا أخذنا الاتفاقية \(A_m(r)=0\) عندما \(r\le 0\) أو \(r>2m\)، فإن العمليتين تندمجان في صيغة واحدة:
$$A_{m+1}(j)=\sum_{t=j}^{2m} A_m(t) + (j-1)A_m(j-2)\qquad (1\le j\le 2m+2).$$
الحد الأول هو تجميع الذيل، والحد الثاني هو الإزاحة الموزونة نفسها ولكن مكتوبة بدلالة فهرس الوصول. وهذه العلاقة تعطي وصفًا كاملًا للانتقال الذي يطبقه البرنامج.
بعد بناء الطبقة الزوجية المطلوبة، تكون الإجابة هي مجموع عناصر الملف:
$$F(2m)=\sum_{j=1}^{2m} A_m(j).$$
وتوجد أيضًا هوية مفيدة للتحقق من الطبقة التالية. فعند جمع العلاقة السابقة على جميع قيم \(j\) نحصل على
$$F(2m+2)=\sum_{j=1}^{2m} jA_m(j)+\sum_{j=1}^{2m}(j+1)A_m(j)=\sum_{j=1}^{2m}(2j+1)A_m(j).$$
ولا يخزن التنفيذ الحالة بهذه الصيغة، لكنها وسيلة أنيقة للتأكد من أن الانتقال والمجموع النهائي متسقان.
نبدأ من
$$A_1=(0,1).$$
عند \(n=4\) يكون ملف الذيل
$$S_1=(1,1),$$
ثم تضيف الإزاحة الموزونة القيمة \(3\) إلى الموضع الرابع. لذلك
$$A_2=(1,1,0,3),\qquad F(4)=1+1+0+3=5.$$
وبتطبيق القاعدة نفسها مرة أخرى نحصل على
$$S_2=(5,4,3,3),$$
ثم تضاف المساهمات \(2,3,0,15\) إلى المواضع \(3,4,5,6\). ومن ثم
$$A_3=(5,4,5,6,0,15),\qquad F(6)=35.$$
وبانتقال آخر نحصل على
$$S_3=(35,30,26,21,15,15),$$
أما المساهمات الإضافية المنقولة فهي \(10,12,20,30,0,105\). وعليه يصبح
$$A_4=(35,30,36,33,35,45,0,105),$$
وبالتالي
$$F(8)=35+30+36+33+35+45+0+105=319,$$
وهو تمامًا مقدار التحقق الموجود في التنفيذات.
يحفظ تنفيذ C++ ملف الطبقة الزوجية الحالية داخل مصفوفة ديناميكية. فإذا كانت قيمة \(n\) المطلوبة فردية أعاد \(0\) فورًا. وإلا بدأ من الطبقة الأساسية الموافقة لـ \(n=2\)، ثم كرر الانتقال عبر \(n=4,6,\dots\)، مع إجراء جميع العمليات بترديد \(10^9+7\).
ويتكون كل انتقال عمليًا من أربع مراحل: نسخ الملف الحالي، ثم تحويل هذه النسخة إلى مجاميع ذيلية بمسح عكسي، ثم توسيع التخزين بموضعين، ثم حقن المساهمات الموزونة بمعامل \((j+1)\) في المواضع المزاحة بمقدار \(2\). وبعد الوصول إلى آخر طبقة زوجية يجمع التنفيذ جميع عناصر الملف للحصول على \(F(n)\).
تعتمد تنفيذات C++ وPython وJava كلها على العلاقة التكرارية نفسها. أما نسختا Python وJava فهما مجرد غلافين خفيفين حول الحساب المترجم بلغة C++، ثم تقومان بتحليل العدد الصحيح المطبوع. ولهذا تشترك اللغات الثلاث في قاعدة الفردي والزوجي نفسها، وفي نقطتي التحقق \(F(4)=5\) و\(F(8)=319\)، وفي التعقيد نفسه الذي تحكمه نواة C++.
لنفرض أن \(n=2m\). طول الملف ينمو خطيًا: فعلى الطبقات \(2,4,6,\dots,2m\) يكون الطول الكلي، مع احتساب الخانة الصفرية غير المستخدمة، مساويًا لـ \(3,5,7,\dots,2m+1\). ويعالج انتقال واحد الطبقة الحالية عبر مسح ذيلي عكسي ومسح أمامي للإزاحة الموزونة، لذا تكون كلفته على حجمه \(O(m)\). وبجمع جميع الطبقات الزوجية نحصل على
$$O(1+2+\cdots+m)=O(m^2)=O(n^2).$$
ولا يُخزن إلا الملف الحالي والملف التالي، لذا يكون استهلاك الذاكرة خطيًا:
$$O(m)=O(n).$$