The sequence is
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6.$$
We must compute the sum, modulo \(10^9+7\), over all index quadruples \(i_1<i_2<i_3<i_4\) whose values are also strictly increasing:
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}.$$
A direct \(O(n^4)\) search is hopeless. The implementation instead counts increasing subsequences by length and keeps both how many there are and what their total element-sum contribution is.
The key observation is that the final quantity is not only about counting valid quadruples. For every valid quadruple we also need the sum of its four values, so the dynamic program must track two pieces of information at every stage.
For \(t\in\{1,2,3,4\}\), let \(N_t(i)\) be the number of strictly increasing subsequences of length \(t\) that end at position \(i\). Let \(W_t(i)\) be the sum of the element-sums of all those subsequences.
For length \(1\), the only subsequence ending at \(i\) is \((a_i)\), so
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
For larger \(t\), the last element is fixed at \(a_i\), and the previous element must come from some earlier position \(j<i\) with \(a_j<a_i\).
If a valid subsequence of length \(t-1\) ends at \(j\), then appending \(a_i\) produces a valid subsequence of length \(t\) ending at \(i\) whenever \(j<i\) and \(a_j<a_i\). Therefore
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
For the weighted version, every such extension adds \(a_i\) once to each older subsequence. Hence
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
Rearranging gives the more useful form
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i).$$
Once \(W_4(i)\) is known for every \(i\), the final answer is simply
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}.$$
Let the distinct sequence values in sorted order be
$$b_1<b_2<\dots<b_m,$$
and assign each \(a_i\) its compressed rank \(r_i\in\{1,\dots,m\}\). Then
$$a_j<a_i \iff r_j<r_i.$$
This matters because the recurrence needs sums over all earlier positions whose values are smaller than the current value. After compression that becomes a prefix query over ranks \(1\) through \(r_i-1\). Using \(r_i-1\) rather than \(r_i\) enforces the strict inequality automatically, even if equal values ever appear.
While scanning the sequence from left to right, define prefix accumulators
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j).$$
At the moment we process position \(i\), these contain information from earlier positions only, so the index condition \(j<i\) is already built in. The recurrences become
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4.$$
Each pair \((F_t,G_t)\) can be maintained by a Fenwick tree over ranks, so every query and update costs \(O(\log m)\).
To compute length \(4\), the implementation only needs prefix information for lengths \(1\), \(2\), and \(3\). After calculating \(W_4(i)\), that contribution is added directly to the answer; no later step ever needs subsequences of length \(4\) as input. Therefore the data structure layer stores only the first three levels.
This keeps the scan compact:
$$\text{query length 1}\rightarrow \text{build length 2},$$
$$\text{query length 2}\rightarrow \text{build length 3},$$
$$\text{query length 3}\rightarrow \text{build length 4 contribution}.$$
The first six generated values are
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
After sorting these six distinct values, their compressed ranks are
$$1,\ 2,\ 4,\ 5,\ 3,\ 6.$$
The valid increasing quadruples are
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
Their individual value-sums are
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616,$$
so the total is
$$94513710.$$
The DP sees the same structure incrementally. At the fourth term, there is exactly one eligible length-\(3\) subsequence before it, so it contributes \(11585394\). The fifth term has rank \(3\), so no earlier length-\(3\) subsequence ends below that rank and it contributes \(0\). The sixth term can extend five earlier length-\(3\) subsequences, and its combined contribution is
$$13039514+17438192+10434634+20996360+21019616=82928316.$$
Adding the fourth and sixth term contributions gives
$$11585394+82928316=94513710,$$
which matches the exact small-prefix check.
The C++, Python, and Java implementations follow the same pipeline. First they generate the \(10^6\) sequence values iteratively modulo \(10000019\). Next they sort the distinct values and replace each sequence element by its compressed rank.
During the main left-to-right pass, the implementation maintains three Fenwick structures, one for each subsequence length \(1\), \(2\), and \(3\). Every structure stores two prefix aggregates at once: counts of increasing subsequences ending in each rank range, and the total sum of all element-sums of those subsequences.
For a new value, it queries only smaller ranks, which simultaneously enforces the value condition \(a_j<a_i\) and, because the scan is left to right, the index condition \(j<i\). From the queried length-\(1\) data it builds the length-\(2\) contribution, from length \(2\) it builds length \(3\), and from length \(3\) it computes the length-\(4\) contribution that is added straight into the final answer. After that, the newly created length-\(1\), length-\(2\), and length-\(3\) data are inserted back into the Fenwick structures at the current rank.
All arithmetic is reduced modulo \(10^9+7\) as the scan proceeds, so intermediate weighted sums never need arbitrary-precision storage.
Let \(n=10^6\) and let \(m\) be the number of distinct generated values. Building the sequence costs \(O(n)\). Coordinate compression requires sorting, so it costs \(O(n\log n)\). The dynamic scan performs only a constant number of Fenwick prefix queries and updates per element, each in \(O(\log m)\), for a total of \(O(n\log m)\) after compression.
Since \(m\le n\), the end-to-end running time is \(O(n\log n)\). The implementations store the sequence, its sorted distinct copy, the compressed ranks, and three Fenwick layers, so memory usage is \(O(n+m)\), which is \(O(n)\) in this problem.
Die Folge lautet
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6.$$
Gesucht ist die Summe aller Viererindizes \(i_1<i_2<i_3<i_4\), deren Werte ebenfalls streng ansteigen:
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}.$$
Ein direkter \(O(n^4)\)-Ansatz ist unbrauchbar. Deshalb zählt die Lösung steigende Teilfolgen nach ihrer Länge und speichert zusätzlich die Summe aller zugehörigen Wertbeiträge.
Die Zielgröße hängt nicht nur davon ab, wie viele gültige Viererfolgen existieren. Für jede gültige Viererfolge muss auch die Summe ihrer vier Werte mitgeführt werden. Deshalb braucht die dynamische Programmierung an jeder Stelle zwei Zustandsgrößen.
Für \(t\in\{1,2,3,4\}\) sei \(N_t(i)\) die Anzahl streng steigender Teilfolgen der Länge \(t\), die an Position \(i\) enden. Außerdem sei \(W_t(i)\) die Summe der Elementsummen all dieser Teilfolgen.
Für Länge \(1\) gibt es an Position \(i\) nur die Teilfolge \((a_i)\), also
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
Für größere \(t\) ist das letzte Element fest \(a_i\), und das vorherige Element muss von einer früheren Position \(j<i\) mit \(a_j<a_i\) kommen.
Endet eine gültige Teilfolge der Länge \(t-1\) an Position \(j\), dann liefert das Anhängen von \(a_i\) genau dann eine gültige Teilfolge der Länge \(t\), wenn \(j<i\) und \(a_j<a_i\) gilt. Daher
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
Für die gewichtete Variante addiert jede Verlängerung den Wert \(a_i\) genau einmal zu jeder älteren Teilfolge. Also
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
Umgestellt ergibt das
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i).$$
Ist \(W_4(i)\) für alle \(i\) bekannt, dann ist die gesuchte Antwort
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}.$$
Seien die verschiedenen Folgenglieder in sortierter Reihenfolge
$$b_1<b_2<\dots<b_m,$$
und jeder Wert \(a_i\) erhalte seinen komprimierten Rang \(r_i\in\{1,\dots,m\}\). Dann gilt
$$a_j<a_i \iff r_j<r_i.$$
Die Rekurrenz verlangt Summen über alle früheren Positionen mit kleinerem Wert. Nach der Kompression ist das genau eine Präfixabfrage über die Ränge \(1\) bis \(r_i-1\). Das Intervall endet bewusst bei \(r_i-1\), damit die Ungleichung streng bleibt.
Beim Links-nach-rechts-Durchlauf definieren wir
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j).$$
Zum Zeitpunkt der Verarbeitung von Position \(i\) enthalten diese Größen nur frühere Positionen und kodieren damit die Bedingung \(j<i\) automatisch. Die Rekurrenz wird zu
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4.$$
Jedes Paar \((F_t,G_t)\) lässt sich mit einem Fenwick-Baum über den Rängen verwalten, also kostet jede Abfrage und jedes Update \(O(\log m)\).
Für die Berechnung von Länge \(4\) werden nur Präfixinformationen zu den Längen \(1\), \(2\) und \(3\) benötigt. Sobald \(W_4(i)\) berechnet ist, wird dieser Beitrag direkt zur Antwort addiert; spätere Schritte verwenden keine Teilfolgen der Länge \(4\) mehr als Eingabe. Deshalb speichert die Implementierung nur die ersten drei Ebenen.
Der Ablauf ist also
$$\text{Abfrage Länge 1}\rightarrow \text{baue Länge 2},$$
$$\text{Abfrage Länge 2}\rightarrow \text{baue Länge 3},$$
$$\text{Abfrage Länge 3}\rightarrow \text{erzeuge Längen-4-Beitrag}.$$
Die ersten sechs erzeugten Werte sind
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
Die komprimierten Ränge dieser sechs Werte lauten
$$1,\ 2,\ 4,\ 5,\ 3,\ 6.$$
Die gültigen steigenden Viererfolgen sind
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
Ihre Wertesummen sind
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616,$$
also insgesamt
$$94513710.$$
Die dynamische Sicht liefert dasselbe Ergebnis schrittweise. Beim vierten Wert gibt es genau eine zulässige Teilfolge der Länge \(3\) davor, also entsteht der Beitrag \(11585394\). Der fünfte Wert hat Rang \(3\), daher endet keine frühere Teilfolge der Länge \(3\) unterhalb dieses Rangs und sein Beitrag ist \(0\). Der sechste Wert kann fünf frühere Teilfolgen der Länge \(3\) verlängern; sein Gesamtbeitrag ist
$$13039514+17438192+10434634+20996360+21019616=82928316.$$
Zusammen ergibt das
$$11585394+82928316=94513710,$$
genau den exakten Kontrollwert für dieses Präfix.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst erzeugen sie die \(10^6\) Folgenglieder iterativ modulo \(10000019\). Danach werden die verschiedenen Werte sortiert und jedes Folgenglied durch seinen komprimierten Rang ersetzt.
Im anschließenden Links-nach-rechts-Durchlauf hält die Implementierung drei Fenwick-Strukturen, je eine für Teilfolgen der Länge \(1\), \(2\) und \(3\). Jede Struktur speichert zugleich zwei Präfixaggregate: die Anzahl steigender Teilfolgen im jeweiligen Rangbereich und die Summe aller zugehörigen Elementsummen.
Für einen neuen Wert werden nur kleinere Ränge abgefragt. Dadurch ist die Bedingung \(a_j<a_i\) sofort erfüllt, und weil der Durchlauf von links nach rechts erfolgt, ist auch \(j<i\) automatisch gewährleistet. Aus den Daten der Länge \(1\) wird der Beitrag für Länge \(2\) gebaut, aus Länge \(2\) der Beitrag für Länge \(3\), und aus Länge \(3\) der Beitrag für Länge \(4\), der direkt in die Endsumme eingeht. Anschließend werden die neu entstandenen Daten der Längen \(1\), \(2\) und \(3\) an der aktuellen Rangposition zurück in die Fenwick-Strukturen geschrieben.
Alle Rechnungen werden laufend modulo \(10^9+7\) reduziert, sodass keine übergroßen Zwischenwerte gespeichert werden müssen.
Sei \(n=10^6\) und \(m\) die Anzahl verschiedener erzeugter Werte. Das Erzeugen der Folge kostet \(O(n)\). Die Rangkompression benötigt wegen des Sortierens \(O(n\log n)\). Der dynamische Durchlauf führt pro Element nur konstant viele Fenwick-Abfragen und -Updates aus, jeweils in \(O(\log m)\), also insgesamt \(O(n\log m)\) nach der Kompression.
Da \(m\le n\) gilt, ist die Gesamtlaufzeit \(O(n\log n)\). Die Implementierungen speichern die Folge, eine sortierte eindeutige Kopie, die komprimierten Ränge und drei Fenwick-Ebenen. Der Speicherbedarf ist daher \(O(n+m)\), also hier \(O(n)\).
Dizi
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6$$
şeklinde üretiliyor. Bizden, hem indisleri hem de değerleri sıkı artan tüm dörtlüler için
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}$$
değerini hesaplamamız gerekiyor. Doğrudan \(O(n^4)\) tarama imkansız olduğundan, çözüm artan alt dizileri uzunluğa göre sayıyor ve aynı anda bu alt dizilerin toplam katkısını da tutuyor.
Buradaki zorluk sadece geçerli dörtlülerin kaç tane olduğunu bulmak değildir. Her geçerli dörtlü için dört elemanın toplamı da cevaba eklendiği için, dinamik programlamada her seviyede iki ayrı nicelik taşımamız gerekir.
\(t\in\{1,2,3,4\}\) için \(N_t(i)\), \(i\) indeksinde biten uzunluğu \(t\) olan sıkı artan alt dizilerin sayısı olsun. \(W_t(i)\) ise bu alt dizilerin eleman toplamlarının toplamı olsun.
Uzunluk \(1\) için tek olasılık \((a_i)\) olduğundan
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
Daha büyük uzunluklarda son eleman sabit olarak \(a_i\)'dir; bir önceki eleman ise \(j<i\) ve \(a_j<a_i\) şartını sağlayan daha erken bir konumdan gelmelidir.
Uzunluğu \(t-1\) olan geçerli bir alt dizi \(j\) konumunda bitiyorsa, buna \(a_i\) eklenince \(j<i\) ve \(a_j<a_i\) koşulları altında uzunluğu \(t\) olan yeni bir artan alt dizi elde edilir. Bu yüzden
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
Ağırlıklı toplam için, her uzatma işlemi eski alt dizinin toplamına bir kez daha \(a_i\) ekler. Dolayısıyla
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
Bunu yeniden düzenlersek
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i)$$
elde edilir. Tüm \(i\) için \(W_4(i)\) hesaplandıktan sonra nihai cevap
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}$$
olur.
Dizide görülen farklı değerleri sıralı biçimde
$$b_1<b_2<\dots<b_m$$
olarak yazalım ve her \(a_i\)'ye sıkıştırılmış rank \(r_i\in\{1,\dots,m\}\) verelim. O zaman
$$a_j<a_i \iff r_j<r_i.$$
Bağıntıda ihtiyacımız olan şey, değeri mevcut elemandan küçük olan önceki konumlar üzerindeki toplamdır. Rank sıkıştırmasından sonra bu, \(1\) ile \(r_i-1\) arasındaki bir prefix sorgusuna dönüşür. Özellikle \(r_i\) değil \(r_i-1\) kullanılması, eşit değerlerin yanlışlıkla kabul edilmesini engeller ve sıkı artışı korur.
Diziyi soldan sağa gezerken
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j)$$
tanımlarını kullanalım. \(i\) anında bu büyüklükler yalnızca daha önce görülen indisleri içerdiğinden, \(j<i\) şartı zaten otomatik olarak sağlanır. Böylece bağıntılar
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4$$
şekline iner. Her \((F_t,G_t)\) çifti ranklar üzerinde bir Fenwick ağacıyla tutulabildiği için her sorgu ve güncelleme \(O(\log m)\) sürer.
Uzunluk \(4\) katkısını hesaplamak için sadece uzunluk \(1\), \(2\) ve \(3\) hakkındaki prefix bilgileri gerekir. \(W_4(i)\) elde edildiği anda bu katkı doğrudan cevaba eklenir; sonraki adımlar uzunluk \(4\) alt dizilerini giriş olarak kullanmaz. Bu yüzden veri yapısı tarafında yalnızca ilk üç seviye saklanır.
Akış şu şekildedir:
$$\text{uzunluk 1'i sorgula}\rightarrow \text{uzunluk 2'yi kur},$$
$$\text{uzunluk 2'yi sorgula}\rightarrow \text{uzunluk 3'ü kur},$$
$$\text{uzunluk 3'ü sorgula}\rightarrow \text{uzunluk 4 katkısını hesapla}.$$
Üretilen ilk altı değer şunlardır:
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
Bu altı değerin sıralı rankları ise
$$1,\ 2,\ 4,\ 5,\ 3,\ 6$$
olur. Geçerli artan dörtlüler şunlardır:
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
Bu dörtlülerin değer toplamları
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616$$
olduğu için toplam
$$94513710$$
çıkar. Dinamik programlama da aynı yapıyı adım adım görür. Dördüncü terimde öncesinde tam bir uzunluk-\(3\) aday vardır, dolayısıyla katkı \(11585394\) olur. Beşinci terimin rankı \(3\) olduğu için onun altında biten hiçbir uzunluk-\(3\) alt dizi yoktur ve katkı \(0\)'dır. Altıncı terim ise önceki beş uzunluk-\(3\) alt diziyi uzatabilir; bu noktadaki toplu katkı
$$13039514+17438192+10434634+20996360+21019616=82928316$$
eder. Böylece
$$11585394+82928316=94513710$$
sonucuna ulaşılır; bu da küçük önek için elde edilen tam değerle aynıdır.
C++, Python ve Java implementasyonları aynı hattı izler. Önce \(10^6\) terim, \(10000019\) modunda art arda üretilir. Ardından farklı değerler sıralanır ve her terim sıkıştırılmış rankına çevrilir.
Ana soldan-sağa geçiş sırasında implementasyon üç Fenwick yapısı tutar; bunlar sırasıyla uzunluk \(1\), \(2\) ve \(3\) artan alt dizilere karşılık gelir. Her yapıda iki prefix toplamı birlikte tutulur: ilgili rank aralığında biten artan alt dizi sayısı ve bu alt dizilerin eleman toplamlarının toplamı.
Yeni bir değer işlendiğinde yalnızca daha küçük ranklar sorgulanır. Böylece değer şartı \(a_j<a_i\) doğrudan sağlanır; tarama soldan sağa yapıldığı için indis şartı \(j<i\) de otomatik olur. Uzunluk \(1\) bilgilerinden uzunluk \(2\), uzunluk \(2\) bilgilerinden uzunluk \(3\), uzunluk \(3\) bilgilerinden de doğrudan cevapta kullanılacak uzunluk \(4\) katkısı üretilir. Sonrasında oluşan yeni uzunluk \(1\), \(2\) ve \(3\) verileri mevcut rank konumuna geri yazılır.
Tüm aritmetik işlem boyunca \(10^9+7\) modunda indirgeme yapılır; böylece ara toplamlarda taşma kontrol altında tutulur.
\(n=10^6\) ve farklı değer sayısı \(m\) olsun. Diziyi üretmek \(O(n)\) sürer. Rank sıkıştırması için sıralama gerektiğinden bu aşama \(O(n\log n)\) zaman alır. Dinamik geçişte her eleman için sabit sayıda Fenwick prefix sorgusu ve güncellemesi yapılır; bunların her biri \(O(\log m)\) olduğundan sıkıştırma sonrasındaki toplam maliyet \(O(n\log m)\) olur.
\(m\le n\) olduğundan uçtan uca zaman karmaşıklığı \(O(n\log n)\) seviyesindedir. Implementasyonlar dizi değerlerini, sıralı benzersiz kopyayı, rankları ve üç Fenwick katmanını tuttuğu için bellek kullanımı \(O(n+m)\), yani bu problemde \(O(n)\)'dir.
La sucesión es
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6.$$
Debemos calcular, módulo \(10^9+7\), la suma sobre todas las cuádruplas de índices \(i_1<i_2<i_3<i_4\) cuyos valores también crecen estrictamente:
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}.$$
Un recorrido directo \(O(n^4)\) es inviable. La solución cuenta subsecuencias crecientes por longitud y, al mismo tiempo, acumula la contribución total de los valores contenidos en esas subsecuencias.
La dificultad no es solo contar cuántas cuádruplas válidas existen. Cada cuádrupla aporta también la suma de sus cuatro valores, así que el estado dinámico debe registrar tanto cantidades como sumas ponderadas.
Para \(t\in\{1,2,3,4\}\), sea \(N_t(i)\) el número de subsecuencias estrictamente crecientes de longitud \(t\) que terminan en la posición \(i\). Sea \(W_t(i)\) la suma de las sumas de elementos de todas esas subsecuencias.
Para longitud \(1\), la única subsecuencia que termina en \(i\) es \((a_i)\), de modo que
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
Para \(t>1\), el último elemento es \(a_i\), y el elemento anterior debe provenir de una posición previa \(j<i\) con \(a_j<a_i\).
Si una subsecuencia válida de longitud \(t-1\) termina en \(j\), entonces al añadir \(a_i\) obtenemos una subsecuencia válida de longitud \(t\) que termina en \(i\) siempre que \(j<i\) y \(a_j<a_i\). Por tanto,
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
Para la versión ponderada, cada extensión añade \(a_i\) una vez a cada subsecuencia previa. Entonces
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
Reagrupando, queda
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i).$$
Una vez calculados todos los \(W_4(i)\), la respuesta final es
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}.$$
Sea
$$b_1<b_2<\dots<b_m$$
la lista ordenada de valores distintos presentes en la sucesión. A cada \(a_i\) le asignamos su rango comprimido \(r_i\in\{1,\dots,m\}\). Entonces
$$a_j<a_i \iff r_j<r_i.$$
La recurrencia necesita sumar sobre posiciones anteriores con valor menor que el actual. Después de comprimir, eso se convierte en una consulta de prefijo sobre los rangos \(1\) hasta \(r_i-1\). Usar \(r_i-1\) en lugar de \(r_i\) es exactamente lo que mantiene la desigualdad estricta.
Mientras recorremos la sucesión de izquierda a derecha, definimos
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j).$$
En el instante de procesar la posición \(i\), estas cantidades contienen únicamente posiciones anteriores, así que la condición \(j<i\) ya está incorporada. La recurrencia queda
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4.$$
Cada par \((F_t,G_t)\) se puede mantener con un árbol Fenwick sobre los rangos, lo que da \(O(\log m)\) por consulta o actualización.
Para construir contribuciones de longitud \(4\) solo se necesita información de prefijos para longitudes \(1\), \(2\) y \(3\). En cuanto se obtiene \(W_4(i)\), esa cantidad se suma directamente a la respuesta; ninguna etapa posterior necesita subsecuencias de longitud \(4\) como entrada. Por eso la implementación guarda solo tres niveles.
El flujo es
$$\text{consultar longitud 1}\rightarrow \text{construir longitud 2},$$
$$\text{consultar longitud 2}\rightarrow \text{construir longitud 3},$$
$$\text{consultar longitud 3}\rightarrow \text{obtener la contribución de longitud 4}.$$
Los seis primeros valores generados son
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
Sus rangos comprimidos son
$$1,\ 2,\ 4,\ 5,\ 3,\ 6.$$
Las cuádruplas crecientes válidas son
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
Sus sumas individuales de valores son
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616,$$
y por tanto el total es
$$94513710.$$
La visión dinámica produce exactamente lo mismo. En el cuarto término existe una única subsecuencia válida de longitud \(3\) antes de él, así que aporta \(11585394\). El quinto término tiene rango \(3\), por lo que no hay ninguna subsecuencia previa de longitud \(3\) que termine por debajo de ese rango, y su contribución es \(0\). El sexto término puede extender cinco subsecuencias anteriores de longitud \(3\), con contribución total
$$13039514+17438192+10434634+20996360+21019616=82928316.$$
Entonces
$$11585394+82928316=94513710,$$
en perfecto acuerdo con la comprobación exacta sobre ese prefijo pequeño.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero generan iterativamente los \(10^6\) valores de la sucesión módulo \(10000019\). Después ordenan los valores distintos y sustituyen cada elemento por su rango comprimido.
En el recorrido principal de izquierda a derecha, la implementación mantiene tres estructuras Fenwick, una para subsecuencias de longitud \(1\), otra para longitud \(2\) y otra para longitud \(3\). Cada una guarda simultáneamente dos agregados de prefijo: el número de subsecuencias crecientes que terminan en cada intervalo de rangos y la suma total de las sumas de elementos de esas subsecuencias.
Para un nuevo valor, solo se consultan rangos menores. Eso fuerza la condición \(a_j<a_i\); y como el recorrido es de izquierda a derecha, la condición \(j<i\) también queda satisfecha. A partir de la información de longitud \(1\) se construye la de longitud \(2\), a partir de longitud \(2\) se construye la de longitud \(3\), y a partir de longitud \(3\) se calcula la contribución de longitud \(4\), que se añade directamente a la respuesta final. Luego las nuevas contribuciones de longitudes \(1\), \(2\) y \(3\) se insertan en la posición del rango actual.
Toda la aritmética se reduce continuamente módulo \(10^9+7\), por lo que las sumas ponderadas intermedias permanecen controladas.
Sea \(n=10^6\) y \(m\) el número de valores distintos generados. Construir la sucesión cuesta \(O(n)\). La compresión de coordenadas necesita ordenación y por ello cuesta \(O(n\log n)\). El barrido dinámico hace solo un número constante de consultas y actualizaciones Fenwick por elemento, cada una en \(O(\log m)\), así que esa fase cuesta \(O(n\log m)\).
Como \(m\le n\), el tiempo total de extremo a extremo es \(O(n\log n)\). Las implementaciones almacenan la sucesión, una copia ordenada sin repetidos, los rangos comprimidos y tres capas Fenwick, de modo que la memoria usada es \(O(n+m)\), es decir, \(O(n)\) en este problema.
数列定义为
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6.$$
要求计算所有满足下标严格递增且数值也严格递增的四元组之贡献和，并对 \(10^9+7\) 取模：
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}.$$
如果直接枚举四重循环，复杂度是 \(O(n^4)\)，对 \(n=10^6\) 完全不可行。真正可行的做法是按“递增子序列长度”做动态规划，同时分别维护“个数”和“这些子序列所有元素和的总贡献”。
这道题不能只做普通计数，因为每个合法四元组要向答案贡献四个数的和，而不是单纯贡献 \(1\)。因此每个动态规划层级都必须同时记录两个量：有多少个可行子序列，以及这些子序列的元素和总共是多少。
对于 \(t\in\{1,2,3,4\}\)，定义 \(N_t(i)\) 为“以位置 \(i\) 结尾、长度为 \(t\) 的严格递增子序列个数”。再定义 \(W_t(i)\) 为“这些子序列的元素和之总和”。
当 \(t=1\) 时，以 \(i\) 结尾的子序列只有一个，就是 \((a_i)\)。所以
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
当 \(t\ge 2\) 时，最后一个元素固定为 \(a_i\)。它前面的元素必须来自某个更早的位置 \(j<i\)，并且还要满足数值条件 \(a_j<a_i\)。
如果某个长度为 \(t-1\) 的合法递增子序列在位置 \(j\) 结束，那么只要 \(j<i\) 且 \(a_j<a_i\)，就可以把 \(a_i\) 接在后面，得到一个长度为 \(t\) 的合法子序列。因此
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
对于带权版本，每次把 \(a_i\) 接到旧子序列后面时，旧子序列的元素和会整体保留，同时还要额外加上一次 \(a_i\)。于是
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
把式子整理一下，就得到更适合实现的形式：
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i).$$
最终答案就是所有长度为 \(4\) 且以任意位置结束的贡献之和：
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}.$$
把序列中出现过的不同值排序，记为
$$b_1<b_2<\dots<b_m,$$
再把每个 \(a_i\) 映射为它的压缩秩 \(r_i\in\{1,\dots,m\}\)。这样就有
$$a_j<a_i \iff r_j<r_i.$$
原始递推需要对所有更早且更小的元素求和。秩压缩之后，这就等价于对秩区间 \(1\) 到 \(r_i-1\) 做一次前缀查询。这里必须取到 \(r_i-1\)，而不能取到 \(r_i\)，因为题目要求的是严格上升，不能把相等值也算进去。
按下标从左到右扫描时，定义
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j).$$
在处理第 \(i\) 个位置时，这两个前缀量只包含更早的位置，因此下标条件 \(j<i\) 已经自动满足。于是递推式变成
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4.$$
每一对 \((F_t,G_t)\) 都可以用一棵按秩建立的 Fenwick 树来维护，因此单次前缀查询或单点更新都是 \(O(\log m)\)。
要构造长度为 \(4\) 的答案贡献，只需要知道长度 \(1\)、\(2\)、\(3\) 的前缀信息。一旦 \(W_4(i)\) 被算出来，它就会立刻加入最终答案，后续步骤不再需要把“长度为 \(4\) 的子序列”拿去继续延长。因此实现只保存前三层。
整体流程可以概括成
$$\text{查询长度 1}\rightarrow \text{构造长度 2},$$
$$\text{查询长度 2}\rightarrow \text{构造长度 3},$$
$$\text{查询长度 3}\rightarrow \text{得到长度 4 的贡献}.$$
这也是为什么实现里只需要三组前缀结构，而不需要第四组。
前六个生成值是
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
把这六个值从小到大排序后，可得到对应秩
$$1,\ 2,\ 4,\ 5,\ 3,\ 6.$$
满足下标递增且数值递增的四元组共有六个：
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
它们各自的数值和分别是
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616,$$
因此总和为
$$94513710.$$
动态规划对这个前缀的理解也非常清楚。处理到第四项时，前面恰好存在一个长度为 \(3\) 的合法递增子序列，所以第四项产生的长度 \(4\) 贡献就是 \(11585394\)。处理到第五项时，它的秩是 \(3\)，在更小秩里并不存在任何长度为 \(3\) 的前缀状态，因此它对四元组答案的新增贡献为 \(0\)。处理到第六项时，前面有五个可延长的长度 \(3\) 子序列，所以它一次性贡献
$$13039514+17438192+10434634+20996360+21019616=82928316.$$
把第四项和第六项的长度 \(4\) 贡献加起来，得到
$$11585394+82928316=94513710,$$
与精确枚举结果完全一致。
C++、Python 和 Java 三个实现都遵循同一条流程。首先按给定递推在模 \(10000019\) 下生成 \(10^6\) 个序列值。然后把所有不同值排序，并把每个位置替换成压缩后的秩。
在主循环中，程序从左到右扫描整个序列，并维护三层 Fenwick 结构，分别对应长度 \(1\)、\(2\)、\(3\) 的递增子序列。每层都同时保存两类前缀信息：在某个秩前缀内结束的子序列个数，以及这些子序列所有元素和的总和。
当一个新值到来时，程序只查询更小的秩。这样一来，数值条件 \(a_j<a_i\) 被自然满足；而由于扫描方向是从左到右，下标条件 \(j<i\) 也天然成立。接着利用长度 \(1\) 的前缀信息构造长度 \(2\) 状态，利用长度 \(2\) 构造长度 \(3\)，再利用长度 \(3\) 得到当前元素作为末尾时的长度 \(4\) 贡献，并直接加到最终答案中。最后再把新产生的长度 \(1\)、\(2\)、\(3\) 状态写回当前秩的位置。
所有中间计算都持续对 \(10^9+7\) 取模，因此即使贡献和很大，也不会失去可控性。
设 \(n=10^6\)，不同值个数为 \(m\)。生成序列需要 \(O(n)\) 时间。做秩压缩时要排序，因此这一阶段需要 \(O(n\log n)\) 时间。之后的动态扫描对每个元素只做常数次 Fenwick 前缀查询和单点更新，每次都是 \(O(\log m)\)，所以扫描阶段总共需要 \(O(n\log m)\) 时间。
由于 \(m\le n\)，整个算法的总时间复杂度是 \(O(n\log n)\)。实现中需要保存原序列、去重排序后的数组、压缩秩数组，以及三层 Fenwick 结构，因此空间复杂度为 \(O(n+m)\)，在这里可以写成 \(O(n)\)。
Последовательность задается формулой
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6.$$
Нужно вычислить по модулю \(10^9+7\) сумму по всем четверкам индексов \(i_1<i_2<i_3<i_4\), для которых значения также возрастают строго:
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}.$$
Прямой перебор с трудоемкостью \(O(n^4)\) здесь невозможен. Поэтому решение строит динамику по длине возрастающей подпоследовательности и параллельно хранит суммарный вклад ее элементов.
Здесь недостаточно просто сосчитать число допустимых четверок. Каждая допустимая четверка добавляет в ответ сумму четырех значений, поэтому на каждом уровне динамики нужно хранить не только количество состояний, но и суммарный вес этих состояний.
Для \(t\in\{1,2,3,4\}\) обозначим через \(N_t(i)\) число строго возрастающих подпоследовательностей длины \(t\), заканчивающихся в позиции \(i\). Через \(W_t(i)\) обозначим сумму сумм элементов всех таких подпоследовательностей.
Для длины \(1\) возможна только подпоследовательность \((a_i)\), поэтому
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
Если \(t\ge 2\), то последний элемент фиксирован и равен \(a_i\), а предыдущий элемент должен стоять в некоторой более ранней позиции \(j<i\) и удовлетворять условию \(a_j<a_i\).
Если допустимая подпоследовательность длины \(t-1\) заканчивается в \(j\), то, добавляя к ней \(a_i\), мы получаем допустимую подпоследовательность длины \(t\), если \(j<i\) и \(a_j<a_i\). Следовательно,
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
Для взвешенной версии каждая такая операция добавляет \(a_i\) к каждой старой подпоследовательности ровно один раз. Поэтому
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
После перегруппировки получаем
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i).$$
Итоговый ответ равен
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}.$$
Пусть различные значения последовательности в отсортированном виде равны
$$b_1<b_2<\dots<b_m,$$
а каждому \(a_i\) сопоставлен его сжатый ранг \(r_i\in\{1,\dots,m\}\). Тогда
$$a_j<a_i \iff r_j<r_i.$$
В рекуррентных формулах требуется суммировать по всем более ранним позициям с меньшим значением. После сжатия координат это превращается в запрос суммы по префиксу рангов от \(1\) до \(r_i-1\). Именно граница \(r_i-1\) обеспечивает строгое неравенство и не пропускает равные значения.
При проходе слева направо введем
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j).$$
В момент обработки позиции \(i\) эти величины уже учитывают только более ранние позиции, так что условие \(j<i\) встроено автоматически. Тогда рекуррентные формулы принимают вид
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4.$$
Каждую пару \((F_t,G_t)\) можно поддерживать деревом Фенвика по рангам, поэтому один запрос или одно обновление стоят \(O(\log m)\).
Чтобы вычислить вклад подпоследовательностей длины \(4\), нужны только префиксные данные для длин \(1\), \(2\) и \(3\). Как только найдено \(W_4(i)\), этот вклад сразу прибавляется к ответу, и никакие подпоследовательности длины \(4\) больше не используются как промежуточное состояние. Поэтому реализация хранит только три уровня.
Схема вычислений такова:
$$\text{запрос длины 1}\rightarrow \text{построение длины 2},$$
$$\text{запрос длины 2}\rightarrow \text{построение длины 3},$$
$$\text{запрос длины 3}\rightarrow \text{получение вклада длины 4}.$$
Первые шесть сгенерированных значений таковы:
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
Их сжатые ранги равны
$$1,\ 2,\ 4,\ 5,\ 3,\ 6.$$
Допустимые возрастающие четверки индексов:
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
Их суммы значений равны
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616,$$
поэтому общий итог равен
$$94513710.$$
Динамика видит то же самое пошагово. На четвертом элементе перед ним существует ровно одна допустимая подпоследовательность длины \(3\), поэтому возникает вклад \(11585394\). У пятого элемента ранг равен \(3\), а подпоследовательностей длины \(3\), заканчивающихся на меньшем ранге, нет, значит вклад равен \(0\). Шестой элемент может продолжить пять более ранних подпоследовательностей длины \(3\), поэтому его общий вклад равен
$$13039514+17438192+10434634+20996360+21019616=82928316.$$
Следовательно,
$$11585394+82928316=94513710,$$
что полностью совпадает с точной проверкой на этом небольшом префиксе.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала итеративно генерируются \(10^6\) членов последовательности по модулю \(10000019\). Затем все различные значения сортируются, и каждый элемент заменяется своим сжатым рангом.
Во время основного прохода слева направо поддерживаются три структуры Фенвика: для подпоследовательностей длины \(1\), \(2\) и \(3\). В каждой структуре хранятся сразу два префиксных агрегата: количество возрастающих подпоследовательностей, заканчивающихся в данном диапазоне рангов, и суммарная сумма элементов по всем таким подпоследовательностям.
Для нового значения выполняются запросы только по меньшим рангам. Тем самым автоматически обеспечивается условие \(a_j<a_i\), а из-за левого-направо обхода автоматически выполняется и \(j<i\). Из данных длины \(1\) строятся вклады длины \(2\), из длины \(2\) строятся вклады длины \(3\), а из длины \(3\) вычисляется вклад длины \(4\), который сразу добавляется в окончательный ответ. После этого новые состояния длины \(1\), \(2\) и \(3\) записываются обратно в структуры по текущему рангу.
Все арифметические действия выполняются с постоянным взятием остатка по модулю \(10^9+7\), поэтому промежуточные суммы не выходят из-под контроля.
Пусть \(n=10^6\), а \(m\) — число различных значений последовательности. Генерация последовательности стоит \(O(n)\). Сжатие координат требует сортировки и поэтому занимает \(O(n\log n)\). Основной динамический проход делает лишь константное число запросов и обновлений дерева Фенвика на каждый элемент, по \(O(\log m)\) каждое, так что после этапа сжатия эта часть стоит \(O(n\log m)\).
Поскольку \(m\le n\), полная временная сложность равна \(O(n\log n)\). Реализации хранят саму последовательность, отсортированную копию без повторов, массив рангов и три слоя структур Фенвика, поэтому расход памяти равен \(O(n+m)\), то есть здесь \(O(n)\).
المتتالية معرفة بالعلاقة
$$a_i \equiv 153^i \pmod{10000019},\qquad 1 \le i \le 10^6.$$
والمطلوب حساب مجموع جميع الرباعيات ذات الفهارس المتزايدة والقيم المتزايدة أيضًا، مع أخذ الناتج بترديد \(10^9+7\):
$$S=\sum_{\substack{1\le i_1<i_2<i_3<i_4\le 10^6\\a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}}}\left(a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}\right)\pmod{10^9+7}.$$
العد المباشر من نوع \(O(n^4)\) غير ممكن عمليًا عند \(n=10^6\). لذلك تعتمد الخوارزمية على عدّ المتتاليات الجزئية الصاعدة حسب طولها، مع الاحتفاظ في الوقت نفسه بإجمالي مساهمة القيم داخل هذه المتتاليات.
الصعوبة هنا ليست في معرفة عدد الرباعيات الصحيحة فقط، بل في أن كل رباعية تضيف مجموع عناصرها الأربعة إلى الجواب. لهذا السبب يجب أن تخزن البرمجة الديناميكية نوعين من المعلومات معًا: عدد الحالات، ومجموع الأوزان الناتجة عنها.
لكل \(t\in\{1,2,3,4\}\)، لنعرّف \(N_t(i)\) على أنه عدد المتتاليات الجزئية الصاعدة تمامًا بطول \(t\) والتي تنتهي عند الموضع \(i\). ولنعرّف \(W_t(i)\) على أنه مجموع مجاميع عناصر جميع هذه المتتاليات الجزئية.
عندما يكون \(t=1\)، فالمتتالية الوحيدة المنتهية عند \(i\) هي \((a_i)\)، ولذلك
$$N_1(i)=1,\qquad W_1(i)=a_i.$$
أما عندما \(t\ge 2\)، فإن العنصر الأخير ثابت ويساوي \(a_i\)، ويجب أن يأتي العنصر السابق من موضع أسبق \(j<i\) يحقق الشرط \(a_j<a_i\).
إذا كانت هناك متتالية جزئية صالحة بطول \(t-1\) تنتهي عند \(j\)، فإن إلحاق \(a_i\) بها يعطي متتالية صالحة بطول \(t\) تنتهي عند \(i\) متى تحقق \(j<i\) و\(a_j<a_i\). لذلك
$$N_t(i)=\sum_{\substack{j<i\\a_j<a_i}} N_{t-1}(j),\qquad t\ge 2.$$
وبالنسبة إلى المجموع الموزون، فإن كل عملية إلحاق تضيف \(a_i\) مرة واحدة إلى كل متتالية قديمة. ومن ثم
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}}\left(W_{t-1}(j)+a_i\,N_{t-1}(j)\right),\qquad t\ge 2.$$
وبإعادة الترتيب نحصل على الصيغة
$$W_t(i)=\sum_{\substack{j<i\\a_j<a_i}} W_{t-1}(j)+a_i\,N_t(i).$$
وبعد حساب جميع قيم \(W_4(i)\)، يكون الجواب النهائي
$$S=\sum_{i=1}^{10^6} W_4(i)\pmod{10^9+7}.$$
لنرتب القيم المختلفة في المتتالية على الصورة
$$b_1<b_2<\dots<b_m,$$
ثم نعطي كل قيمة \(a_i\) رتبتها المضغوطة \(r_i\in\{1,\dots,m\}\). عندئذٍ يصبح
$$a_j<a_i \iff r_j<r_i.$$
العلاقة التكرارية تحتاج إلى مجموع على جميع المواضع السابقة التي تحمل قيمة أصغر من القيمة الحالية. بعد ضغط القيم، يتحول هذا إلى استعلام بادئة على الرتب من \(1\) حتى \(r_i-1\). واستخدام \(r_i-1\) بالذات هو ما يحافظ على شرط الزيادة الصارمة ويمنع إدخال القيم المتساوية.
أثناء المسح من اليسار إلى اليمين، نعرّف
$$F_t(x)=\sum_{\substack{j<i\\r_j\le x}} N_t(j),\qquad G_t(x)=\sum_{\substack{j<i\\r_j\le x}} W_t(j).$$
وعند معالجة الموضع \(i\)، تكون هذه الكميات قد جمعت معلومات المواضع السابقة فقط، لذلك يكون شرط \(j<i\) متحققًا ضمنيًا. وعليه تصبح العلاقات
$$N_1(i)=1,\qquad W_1(i)=a_i,$$
$$N_t(i)=F_{t-1}(r_i-1),\qquad W_t(i)=G_{t-1}(r_i-1)+a_i\,N_t(i),\qquad t=2,3,4.$$
ويمكن تمثيل كل زوج \((F_t,G_t)\) بشجرة Fenwick على فضاء الرتب، وبذلك تصبح كل عملية استعلام أو تحديث في \(O(\log m)\).
لحساب مساهمة الطول \(4\)، نحتاج فقط إلى معلومات بادئية للأطوال \(1\) و\(2\) و\(3\). وما إن تُحسب \(W_4(i)\) حتى تُضاف مباشرة إلى الجواب النهائي، ولا توجد خطوة لاحقة تستخدم متتاليات بطول \(4\) كمدخل جديد. لهذا السبب تخزن البنية التنفيذية ثلاث طبقات فقط.
ويصبح سير العمل كالتالي:
أولًا: نقرأ بيانات الطول \(1\) من البادئات الأصغر ثم نبني مساهمة الطول \(2\).
ثانيًا: نقرأ بيانات الطول \(2\) بالطريقة نفسها ثم نبني مساهمة الطول \(3\).
ثالثًا: نقرأ بيانات الطول \(3\) ونستخرج منها مباشرة مساهمة الطول \(4\).
أول ست قيم مولدة هي
$$153,\ 23409,\ 3581577,\ 7980255,\ 976697,\ 9434375.$$
وبعد ضغطها إلى رتب نحصل على
$$1,\ 2,\ 4,\ 5,\ 3,\ 6.$$
الرباعيات الصاعدة الصحيحة هي
$$\begin{aligned} &(1,2,3,4),\quad (1,2,3,6),\quad (1,2,4,6),\\ &(1,2,5,6),\quad (1,3,4,6),\quad (2,3,4,6). \end{aligned}$$
ومجاميع قيمها الفردية هي
$$11585394,\ 13039514,\ 17438192,\ 10434634,\ 20996360,\ 21019616,$$
ومن ثم يكون المجموع الكلي
$$94513710.$$
وتظهر البرمجة الديناميكية الصورة نفسها بالتدرج. عند الحد الرابع يوجد قبله متتالية جزئية صاعدة وحيدة بطول \(3\)، لذا تكون مساهمته \(11585394\). أما الحد الخامس فرتبته \(3\)، ولا توجد قبله أي متتالية بطول \(3\) تنتهي عند رتبة أصغر من ذلك، فتكون مساهمته \(0\). وعند الحد السادس يمكن تمديد خمس متتاليات جزئية سابقة بطول \(3\)، فينتج مجموع إضافي مقداره
$$13039514+17438192+10434634+20996360+21019616=82928316.$$
وبالتالي
$$11585394+82928316=94513710,$$
وهو نفس ناتج الفحص الدقيق على هذه السابقة الصغيرة.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا يتم توليد \(10^6\) قيمة من المتتالية تكراريًا بترديد \(10000019\). بعد ذلك تُرتب القيم المختلفة، ويُستبدل كل عنصر برتبته المضغوطة.
في المرور الرئيسي من اليسار إلى اليمين، تحتفظ الخوارزمية بثلاث طبقات من بنية Fenwick، تمثل المتتاليات الجزئية الصاعدة ذات الأطوال \(1\) و\(2\) و\(3\). وكل طبقة تخزن معًا نوعين من المجاميع البادئية: عدد المتتاليات المنتهية ضمن مجال معين من الرتب، ومجموع مجاميع عناصر تلك المتتاليات.
عند وصول قيمة جديدة، لا يُستعلم إلا عن الرتب الأصغر منها. وهكذا يتحقق شرط \(a_j<a_i\) مباشرة، وبما أن المعالجة تسير من اليسار إلى اليمين فإن شرط \(j<i\) يكون مضمونًا كذلك. ومن معلومات الطول \(1\) تُبنى مساهمة الطول \(2\)، ومن الطول \(2\) تُبنى مساهمة الطول \(3\)، ومن الطول \(3\) تُستخرج مساهمة الطول \(4\) التي تُضاف مباشرة إلى الجواب النهائي. بعد ذلك تُحدَّث طبقات الأطوال \(1\) و\(2\) و\(3\) عند الرتبة الحالية.
وجميع العمليات الحسابية تُختزل باستمرار بترديد \(10^9+7\)، لذلك تبقى المجاميع الوسيطة ضمن حدود يمكن التحكم بها.
إذا رمزنا إلى عدد الحدود بـ \(n=10^6\)، وإلى عدد القيم المختلفة بـ \(m\)، فإن توليد المتتالية يحتاج إلى \(O(n)\). أما ضغط القيم فيحتاج إلى فرز، ولذلك يكلف \(O(n\log n)\). ثم إن المرور الديناميكي ينفذ عددًا ثابتًا من استعلامات وتحديثات Fenwick لكل عنصر، وكل عملية منها تكلف \(O(\log m)\)، فتكون كلفة هذه المرحلة \(O(n\log m)\).
وبما أن \(m\le n\)، فإن التعقيد الزمني الكلي من البداية إلى النهاية هو \(O(n\log n)\). وتخزن التطبيقات المتتالية الأصلية، ونسخة مرتبة بلا تكرار، ورتب العناصر، وثلاث طبقات من بنية Fenwick، لذا يكون استهلاك الذاكرة \(O(n+m)\)، أي \(O(n)\) في هذه المسألة.