An \(n\)-sequence is a word of length \(n\) over the alphabet \(\{1,2,\dots,n\}\), so the total number of such sequences is \(n^n\). For a sequence \(S\), let \(L(S)\) denote the length of its longest contiguous run of equal values. The target quantity is
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
Direct enumeration is hopeless for the actual input \(n=7{,}500{,}000\), so the implementations reorganize the problem into a counting question: for each \(k\), how many sequences satisfy \(L(S)\le k\)?
Define
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
For a fixed sequence with \(L(S)=\ell\), the inequality \(\ell\le k\) is true for exactly \(n-\ell\) integers \(k\in\{1,2,\dots,n-1\}\). Therefore
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
Summing this identity over all \(n^n\) sequences gives
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n).$$
So the whole task reduces to computing \(N_k(n)\) efficiently for every \(1\le k\le n-1\).
Fix the first symbol. Any valid sequence with longest run at most \(k\) can be written as \(r\) consecutive runs with lengths
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k.$$
Once the first run value is fixed, each later run may use any symbol different from the previous one, so it contributes a factor \(n-1\). Hence a composition into \(r\) parts contributes \((n-1)^{r-1}\) sequences for each fixed first symbol.
Let \(G_k(M)\) be the number of valid continuations of length \(M\) after fixing the first position. Then \(N_k(n)=n\,G_k(n-1)\), and
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
where \([x^m]\) denotes the coefficient of \(x^m\).
Set
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}.$$
Then the run decomposition becomes a geometric series:
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
Substituting the closed form for \(R_k(x)\) yields
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}.$$
Therefore, with \(M=n-1\),
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
It is convenient to define
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}.$$
Then
$$G_k(M)=A_{M,k}-A_{M-k,k},$$
with the convention \(A_{M,k}=0\) for \(M<0\).
Expand the denominator as a geometric series:
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
Inside the \(t\)-th power, choose \(p\) factors of \(-(n-1)x^{k+1}\) and \(t-p\) factors of \(nx\). The total exponent of \(x\) is then \(t+pk\). To obtain the coefficient of \(x^M\), we must have \(t=M-pk\). This gives
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p.$$
The alternating sign is exactly the correction that one also sees from inclusion-exclusion on overlong runs; the generating-function derivation packages the same cancellation into a compact formula.
Hence
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
and therefore
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
This is exactly the formula evaluated by the C++, Python, and Java implementations.
There are \(3^3=27\) sequences in total.
For \(k=1\), every run must have length \(1\), so adjacent values must always change. With the first symbol fixed, each of the next two positions has \(2\) choices, giving \(2^2=4\) continuations. Thus
$$N_1(3)=3\cdot 4=12.$$
For \(k=2\), the only forbidden sequences are the constant ones \(111\), \(222\), and \(333\). Therefore
$$N_2(3)=27-3=24.$$
Now apply the tail-sum formula:
$$f(3)=3\cdot 27-12-24=45.$$
This matches the checkpoint used by the implementations. They also verify \(f(7)=1403689\) and \(f(11)=496890792\).
The implementations precompute factorials and inverse factorials modulo \(10^9+9\), so every binomial coefficient in the closed form can be obtained in \(O(1)\) time. They also precompute the powers \(n^q\) and \((-(n-1))^q\) that appear throughout the sum.
For each \(k\), the implementation evaluates the two coefficient sums corresponding to \(A_{n-1,k}\) and \(A_{n-1-k,k}\), converts them into \(N_k(n)\), accumulates all these values, and finally subtracts the total from \(n^{n+1}\). The C++ version parallelizes the outer loop over \(k\), while the Python and Java versions follow the same mathematics without changing the formula.
Precomputing factorials, inverse factorials, and power tables costs \(O(n)\) time and \(O(n)\) memory. For a fixed \(k\), the inner summation over \(p\) has \(\lfloor (n-1)/(k+1)\rfloor+1\) terms. Summing over all \(k\) gives
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n).$$
So the overall method runs in \(O(n\log n)\) time and \(O(n)\) memory, which is dramatically smaller than the impossible \(O(n^n)\) brute-force search.
Eine \(n\)-Sequenz ist ein Wort der Länge \(n\) über dem Alphabet \(\{1,2,\dots,n\}\). Insgesamt gibt es also \(n^n\) solche Sequenzen. Für eine Sequenz \(S\) bezeichne \(L(S)\) die Länge ihres längsten zusammenhängenden Blocks gleicher Werte. Gesucht ist
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
Direktes Durchprobieren ist bei \(n=7{,}500{,}000\) völlig unmöglich. Deshalb zählen die Implementierungen für jedes \(k\), wie viele Sequenzen die Bedingung \(L(S)\le k\) erfüllen, und rekonstruieren daraus die Summe.
Wir definieren
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
Für eine feste Sequenz mit \(L(S)=\ell\) gilt die Ungleichung \(\ell\le k\) für genau \(n-\ell\) Werte \(k\in\{1,2,\dots,n-1\}\). Also
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
Summiert man dies über alle \(n^n\) Sequenzen, so erhält man
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n).$$
Damit reduziert sich das Problem vollständig auf eine effiziente Berechnung von \(N_k(n)\).
Fixieren wir das erste Symbol. Jede zulässige Sequenz mit maximaler Blocklänge \(k\) zerfällt in \(r\) aufeinanderfolgende Läufe mit Längen
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k.$$
Ist der Wert des ersten Laufs fest, dann kann jeder weitere Lauf einen beliebigen der \(n-1\) vom Vorgänger verschiedenen Werte annehmen. Eine Zerlegung in \(r\) Teile trägt also \((n-1)^{r-1}\) Sequenzen pro festem Anfangssymbol bei.
Sei \(G_k(M)\) die Anzahl zulässiger Fortsetzungen der Länge \(M\), nachdem die erste Position festgelegt wurde. Dann gilt \(N_k(n)=n\,G_k(n-1)\) und
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
wobei \([x^m]\) den Koeffizienten von \(x^m\) bezeichnet.
Setze
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}.$$
Dann wird die Summe über alle möglichen Laufzahlen zu einer geometrischen Reihe:
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
Einsetzen der geschlossenen Form von \(R_k(x)\) liefert
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}.$$
Für \(M=n-1\) folgt also
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
Praktisch ist die Hilfsgröße
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}.$$
Dann gilt
$$G_k(M)=A_{M,k}-A_{M-k,k},$$
wobei für \(M<0\) die Konvention \(A_{M,k}=0\) verwendet wird.
Den Nenner entwickeln wir als geometrische Reihe:
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
Im \(t\)-ten Term wählen wir \(p\) Faktoren \(-(n-1)x^{k+1}\) und \(t-p\) Faktoren \(nx\). Die Potenz von \(x\) ist dann \(t+pk\). Um den Koeffizienten von \(x^M\) zu treffen, muss also \(t=M-pk\) gelten. Daraus folgt
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p.$$
Das alternierende Vorzeichen ist genau dieselbe Korrektur, die man auch über Inklusion-Exklusion bei zu langen Läufen erhält; die erzeugende Funktion fasst diese Auslöschung nur kompakter zusammen.
Somit
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
und daher
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
Genau diese Formel werten die C++-, Python- und Java-Implementierungen aus.
Insgesamt gibt es \(3^3=27\) Sequenzen.
Für \(k=1\) muss jeder Lauf Länge \(1\) haben, also müssen benachbarte Werte stets verschieden sein. Bei festem ersten Symbol gibt es für jede der beiden folgenden Positionen \(2\) Möglichkeiten, also \(2^2=4\) Fortsetzungen. Daher
$$N_1(3)=3\cdot 4=12.$$
Für \(k=2\) sind nur die konstanten Sequenzen \(111\), \(222\) und \(333\) verboten. Also
$$N_2(3)=27-3=24.$$
Mit der Schwanzsumme folgt
$$f(3)=3\cdot 27-12-24=45.$$
Das ist exakt der Kontrollwert aus den Implementierungen. Zusätzlich werden dort \(f(7)=1403689\) und \(f(11)=496890792\) überprüft.
Die Implementierungen berechnen Fakultäten und inverse Fakultäten modulo \(10^9+9\) vor, sodass jeder Binomialkoeffizient der geschlossenen Formel in \(O(1)\) verfügbar ist. Ebenso werden die Potenzen \(n^q\) und \((-(n-1))^q\) vorab gespeichert.
Für jedes \(k\) werden dann die beiden Koeffizientensummen für \(A_{n-1,k}\) und \(A_{n-1-k,k}\) ausgewertet, daraus \(N_k(n)\) gebildet, alles aufsummiert und schließlich von \(n^{n+1}\) abgezogen. Die C++-Version parallelisiert die äußere Schleife über \(k\); mathematisch arbeiten aber alle drei Sprachfassungen identisch.
Die Vorberechnung von Fakultäten, inversen Fakultäten und Potenztabellen benötigt \(O(n)\) Zeit und \(O(n)\) Speicher. Für festes \(k\) hat die innere Summe über \(p\) genau \(\lfloor (n-1)/(k+1)\rfloor+1\) Terme. Insgesamt ergibt sich also
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n).$$
Damit läuft das Verfahren in \(O(n\log n)\) Zeit und \(O(n)\) Speicher und ist damit um Größenordnungen effizienter als eine brute-forceartige Enumeration aller \(n^n\) Sequenzen.
Bir \(n\)-sequence, alfabesi \(\{1,2,\dots,n\}\) olan uzunluğu \(n\) bir dizidir; dolayısıyla toplam \(n^n\) tane dizi vardır. Bir dizi \(S\) için \(L(S)\), aynı değerin en uzun ardışık bloğunun uzunluğunu göstersin. Aranan büyüklük
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
Gerçek girdi olan \(n=7{,}500{,}000\) için doğrudan sayım imkansızdır. Bu yüzden implementasyonlar her \(k\) için \(L(S)\le k\) koşulunu sağlayan dizi sayısını bulur ve toplamı buradan yeniden kurar.
Şunu tanımlayalım:
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
Sabit bir dizi için \(L(S)=\ell\) olsun. O zaman \(\ell\le k\) eşitsizliği, \(k\in\{1,2,\dots,n-1\}\) arasında tam olarak \(n-\ell\) kez doğrudur. Bu nedenle
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
Bunu tüm \(n^n\) dizi üzerinde toplarsak
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n)$$
elde edilir. Yani asıl iş, her \(k\) için \(N_k(n)\) değerini hızlı hesaplamaktır.
İlk sembolü sabitleyelim. En uzun koşusu en fazla \(k\) olan her uygun dizi, uzunlukları
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k$$
olan \(r\) adet ardışık koşuya ayrılır. İlk koşunun değeri sabitlendikten sonra, sonraki her koşu bir önceki değerden farklı olmak şartıyla \(n-1\) seçenek getirir. Bu yüzden \(r\) parçalı her bileşim, sabit ilk sembol için \((n-1)^{r-1}\) dizi üretir.
İlk konum sabitken kalan \(M\) uzunluklu devamların sayısına \(G_k(M)\) diyelim. O halde \(N_k(n)=n\,G_k(n-1)\) ve
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
burada \([x^m]\), \(x^m\) katsayısını gösterir.
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}$$
olsun. O zaman koşu sayısı üzerindeki toplam geometrik seriye dönüşür:
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
\(R_k(x)\)'in kapalı biçimini yerine koyunca
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}$$
çıkar. Dolayısıyla \(M=n-1\) için
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
Şimdi
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}$$
tanımını yaparsak
$$G_k(M)=A_{M,k}-A_{M-k,k}$$
olur. Burada \(M<0\) için \(A_{M,k}=0\) kabul edilir.
Paydadaki ifade geometrik seri olarak açılır:
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
\(t\). kuvvette \(p\) tane \(-(n-1)x^{k+1}\) ve \(t-p\) tane \(nx\) seçildiğinde \(x\)'in üssü \(t+pk\) olur. \(x^M\) katsayısını almak için \(t=M-pk\) olmalıdır. Böylece
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p$$
elde edilir. İşaretteki alternans, fazla uzun koşuların dahil etme-hariç tutma ile düzeltilmesinin aynısıdır; üreteç fonksiyonu yaklaşımı aynı iptalleri daha sıkı bir biçimde toplar.
Sonuç olarak
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
ve dolayısıyla
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
C++, Python ve Java implementasyonlarının hesapladığı formül tam olarak budur.
Toplam dizi sayısı \(3^3=27\)'dir.
\(k=1\) için her koşu uzunluğu \(1\) olmak zorundadır; yani komşu değerler her zaman değişmelidir. İlk sembol sabitken sonraki iki pozisyonun her biri için \(2\) seçenek vardır; toplam \(2^2=4\) devam elde edilir. Bu yüzden
$$N_1(3)=3\cdot 4=12.$$
\(k=2\) için yasak olan tek diziler sabit diziler \(111\), \(222\) ve \(333\)'tür. Dolayısıyla
$$N_2(3)=27-3=24.$$
Kuyruk toplamı formülüyle
$$f(3)=3\cdot 27-12-24=45$$
bulunur. Bu, implementasyonların kullandığı kontrol noktasıyla aynıdır. Aynı kod ayrıca \(f(7)=1403689\) ve \(f(11)=496890792\) değerlerini de doğrular.
İmplementasyonlar önce \(10^9+9\) modunda faktöriyel ve ters faktöriyel tablolarını önceden hesaplar; böylece kapalı formdaki her binom katsayısı \(O(1)\) zamanda elde edilir. Aynı şekilde \(n^q\) ve \((-(n-1))^q\) kuvvetleri de önceden hazırlanır.
Daha sonra her \(k\) için \(A_{n-1,k}\) ve \(A_{n-1-k,k}\) toplamları hesaplanır, buradan \(N_k(n)\) üretilir, tüm bu değerler toplanır ve sonuç \(n^{n+1}\)'den çıkarılır. C++ sürümü dıştaki \(k\) döngüsünü paralelleştirir; ancak üç dilde de matematik ve formül aynıdır.
Faktöriyel, ters faktöriyel ve üs tablolarının ön hesabı \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Sabit bir \(k\) için iç toplamda \(\lfloor (n-1)/(k+1)\rfloor+1\) terim vardır. Toplam iş yükü
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n)$$
olur. Böylece yöntem \(O(n\log n)\) zamanda ve \(O(n)\) bellekte çalışır; bu da \(O(n^n)\) düzeyindeki doğrudan taramaya göre devasa bir iyileşmedir.
Una \(n\)-secuencia es una palabra de longitud \(n\) sobre el alfabeto \(\{1,2,\dots,n\}\), así que existen \(n^n\) secuencias en total. Para una secuencia \(S\), sea \(L(S)\) la longitud de su bloque contiguo más largo formado por valores iguales. Queremos calcular
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
Enumerar directamente todas las secuencias es imposible para \(n=7{,}500{,}000\). La idea es contar, para cada \(k\), cuántas secuencias satisfacen \(L(S)\le k\), y luego reconstruir la suma total.
Definimos
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
Para una secuencia fija con \(L(S)=\ell\), la desigualdad \(\ell\le k\) es cierta para exactamente \(n-\ell\) valores de \(k\) dentro de \(\{1,2,\dots,n-1\}\). Por tanto,
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
Al sumar sobre las \(n^n\) secuencias obtenemos
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n).$$
Así, todo el problema queda reducido a calcular \(N_k(n)\) de forma eficiente.
Fijemos el primer símbolo. Toda secuencia válida cuyo bloque máximo tenga longitud a lo sumo \(k\) se descompone en \(r\) rachas consecutivas de longitudes
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k.$$
Una vez fijado el valor de la primera racha, cada racha posterior puede tomar cualquiera de los \(n-1\) símbolos distintos del anterior. Por eso, una composición con \(r\) partes aporta \((n-1)^{r-1}\) secuencias para cada símbolo inicial fijo.
Sea \(G_k(M)\) el número de continuaciones válidas de longitud \(M\) después de fijar la primera posición. Entonces \(N_k(n)=n\,G_k(n-1)\), y
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
donde \([x^m]\) denota el coeficiente de \(x^m\).
Tomemos
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}.$$
Entonces la suma sobre el número de rachas se convierte en una serie geométrica:
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
Sustituyendo la forma cerrada de \(R_k(x)\) se obtiene
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}.$$
Por lo tanto, si \(M=n-1\),
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
Es útil definir
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}.$$
Entonces
$$G_k(M)=A_{M,k}-A_{M-k,k},$$
con la convención \(A_{M,k}=0\) para \(M<0\).
Desarrollamos el denominador como serie geométrica:
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
En la potencia \(t\), elegimos \(p\) factores \(-(n-1)x^{k+1}\) y \(t-p\) factores \(nx\). El exponente total de \(x\) pasa a ser \(t+pk\). Para obtener el coeficiente de \(x^M\), debe cumplirse \(t=M-pk\). Así llegamos a
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p.$$
El signo alternante es la misma corrección que aparece al aplicar inclusión-exclusión a las rachas demasiado largas; la función generadora empaqueta esa cancelación en una sola fórmula.
En consecuencia,
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
y por tanto
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
Ésa es exactamente la fórmula que evalúan las implementaciones en C++, Python y Java.
En total hay \(3^3=27\) secuencias.
Para \(k=1\), todas las rachas deben tener longitud \(1\), así que valores vecinos siempre deben cambiar. Con el primer símbolo fijo, cada una de las dos posiciones restantes tiene \(2\) opciones, es decir, \(2^2=4\) continuaciones. Luego
$$N_1(3)=3\cdot 4=12.$$
Para \(k=2\), las únicas secuencias prohibidas son las constantes \(111\), \(222\) y \(333\). Por lo tanto,
$$N_2(3)=27-3=24.$$
Aplicando la identidad de suma de cola,
$$f(3)=3\cdot 27-12-24=45.$$
Ese valor coincide con el punto de control de las implementaciones. También se verifican \(f(7)=1403689\) y \(f(11)=496890792\).
Las implementaciones precalculan factoriales e inversos factoriales módulo \(10^9+9\), de modo que cada coeficiente binomial de la fórmula cerrada se obtiene en \(O(1)\). Además, precalculan las potencias \(n^q\) y \((-(n-1))^q\) necesarias en la suma.
Para cada \(k\), la implementación evalúa las dos sumas de coeficientes asociadas a \(A_{n-1,k}\) y \(A_{n-1-k,k}\), construye \(N_k(n)\), acumula todos esos valores y finalmente resta el total de \(n^{n+1}\). La versión en C++ paraleliza el bucle exterior sobre \(k\), pero la matemática es la misma en los tres lenguajes.
El precálculo de factoriales, inversos factoriales y tablas de potencias cuesta \(O(n)\) tiempo y \(O(n)\) memoria. Para un \(k\) fijo, la suma interior sobre \(p\) tiene \(\lfloor (n-1)/(k+1)\rfloor+1\) términos. Al sumar sobre todos los \(k\), obtenemos
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n).$$
Así, el método completo corre en \(O(n\log n)\) tiempo y \(O(n)\) memoria, muy por debajo del inabordable \(O(n^n)\) de una enumeración directa.
\(n\)-序列是一个长度为 \(n\) 的词，每个位置都从 \(\{1,2,\dots,n\}\) 中取值，因此总共有 \(n^n\) 个序列。对任意序列 \(S\)，记 \(L(S)\) 为其中最长连续相同数字段的长度。目标是计算
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
当 \(n=7{,}500{,}000\) 时，直接枚举全部序列完全不可行，所以实现改为先统计每个 \(k\) 下满足 \(L(S)\le k\) 的序列数，再由这些计数反推出总和。
定义
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
对一个固定序列，若 \(L(S)=\ell\)，那么在 \(k\in\{1,2,\dots,n-1\}\) 中，不等式 \(\ell\le k\) 恰好成立 \(n-\ell\) 次。因此
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
把这个恒等式对所有 \(n^n\) 个序列求和，就得到
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n).$$
所以整个问题都归结为如何高效计算每个 \(N_k(n)\)。
先固定第一个符号。任何满足最长连续段不超过 \(k\) 的序列，都可以唯一分解为 \(r\) 个连续相同值段，其长度满足
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k.$$
第一个连续段的值一旦固定，后面每一段都只需与前一段不同，因此各有 \(n-1\) 种选择。于是，一个由 \(r\) 个部分组成的分解，对固定首项贡献 \((n-1)^{r-1}\) 个序列。
设 \(G_k(M)\) 表示在首项固定后，后面长度为 \(M\) 的合法延拓数。那么 \(N_k(n)=n\,G_k(n-1)\)，并且
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
其中 \([x^m]\) 表示取 \(x^m\) 的系数。
记
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}.$$
那么对连续段个数的求和就是一个几何级数：
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
把 \(R_k(x)\) 的闭式代入后，得到
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}.$$
因此令 \(M=n-1\)，便有
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
为了书写方便，定义
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}.$$
于是
$$G_k(M)=A_{M,k}-A_{M-k,k},$$
并约定当 \(M<0\) 时 \(A_{M,k}=0\)。
把分母按几何级数展开：
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
在第 \(t\) 次幂中，若选出 \(p\) 个 \(-(n-1)x^{k+1}\) 因子和 \(t-p\) 个 \(nx\) 因子，那么 \(x\) 的总指数就是 \(t+pk\)。为了得到 \(x^M\) 的系数，必须满足 \(t=M-pk\)。因此
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p.$$
这里的交替符号，本质上就是对“连续段过长”情况进行容斥修正时出现的抵消；生成函数只是把这种抵消压缩成了一个紧凑公式。
于是
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
最终得到
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
这正是 C++、Python 和 Java 实现所计算的公式。
总共有 \(3^3=27\) 个序列。
当 \(k=1\) 时，每个连续段都只能长度为 \(1\)，也就是相邻位置必须变化。固定首项后，后面两个位置各有 \(2\) 种选择，所以共有 \(2^2=4\) 个合法延拓。于是
$$N_1(3)=3\cdot 4=12.$$
当 \(k=2\) 时，唯一不合法的是三个常值序列 \(111\)、\(222\)、\(333\)。因此
$$N_2(3)=27-3=24.$$
代回尾和公式可得
$$f(3)=3\cdot 27-12-24=45.$$
这与实现中的校验值一致。实现还会验证 \(f(7)=1403689\) 和 \(f(11)=496890792\)。
实现会先在模 \(10^9+9\) 下预计算阶乘和逆阶乘，因此闭式中的每个二项式系数都能在 \(O(1)\) 时间得到。与此同时，还会预计算公式所需的 \(n^q\) 与 \((-(n-1))^q\) 幂表。
随后对每个 \(k\)，程序分别计算 \(A_{n-1,k}\) 和 \(A_{n-1-k,k}\) 两个系数和，将其组合成 \(N_k(n)\)，累加所有这些值，最后再从 \(n^{n+1}\) 中减去。C++ 版本会把最外层的 \(k\) 循环并行化，但三个语言版本使用的是同一套数学公式。
预计算阶乘、逆阶乘和幂表需要 \(O(n)\) 时间与 \(O(n)\) 空间。对固定的 \(k\)，内层关于 \(p\) 的求和共有 \(\lfloor (n-1)/(k+1)\rfloor+1\) 项。把所有 \(k\) 加起来，总工作量为
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n).$$
因此整体算法的时间复杂度是 \(O(n\log n)\)，空间复杂度是 \(O(n)\)，相对于不可能实现的 \(O(n^n)\) 暴力枚举，提升极大。
\(n\)-последовательность — это слово длины \(n\) над алфавитом \(\{1,2,\dots,n\}\), поэтому всего таких последовательностей \(n^n\). Для последовательности \(S\) обозначим через \(L(S)\) длину её самого длинного непрерывного блока одинаковых значений. Требуется вычислить
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
При \(n=7{,}500{,}000\) прямой перебор невозможен. Поэтому реализации сначала считают, сколько последовательностей удовлетворяет условию \(L(S)\le k\) для каждого \(k\), а затем восстанавливают искомую сумму.
Определим
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
Если для фиксированной последовательности \(L(S)=\ell\), то неравенство \(\ell\le k\) верно ровно для \(n-\ell\) значений \(k\) из множества \(\{1,2,\dots,n-1\}\). Значит,
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
Суммируя это равенство по всем \(n^n\) последовательностям, получаем
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n).$$
Итак, задача полностью сводится к быстрому вычислению \(N_k(n)\).
Зафиксируем первый символ. Любая допустимая последовательность, у которой максимальная длина серии не превосходит \(k\), единственным образом разбивается на \(r\) последовательных серий длины
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k.$$
Когда значение первой серии уже выбрано, каждая следующая серия может взять любой из \(n-1\) символов, отличных от предыдущего. Поэтому разбиение на \(r\) частей даёт \((n-1)^{r-1}\) последовательностей при фиксированном первом символе.
Пусть \(G_k(M)\) — число допустимых продолжений длины \(M\) после фиксации первой позиции. Тогда \(N_k(n)=n\,G_k(n-1)\), и
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
где \([x^m]\) обозначает коэффициент при \(x^m\).
Обозначим
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}.$$
Тогда суммирование по числу серий превращается в геометрический ряд:
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
После подстановки явной формы \(R_k(x)\) получаем
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}.$$
Следовательно, при \(M=n-1\)
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
Удобно ввести величину
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}.$$
Тогда
$$G_k(M)=A_{M,k}-A_{M-k,k},$$
где для \(M<0\) принимается соглашение \(A_{M,k}=0\).
Разложим знаменатель в геометрический ряд:
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
В \(t\)-й степени выберем \(p\) множителей \(-(n-1)x^{k+1}\) и \(t-p\) множителей \(nx\). Тогда суммарная степень \(x\) равна \(t+pk\). Чтобы получить коэффициент при \(x^M\), необходимо \(t=M-pk\). Отсюда следует
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p.$$
Чередующийся знак здесь соответствует той же самой коррекции, которая возникает при включении-исключении для слишком длинных серий; производящая функция просто собирает эти сокращения в компактный вид.
Следовательно,
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
и потому
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
Именно эту формулу вычисляют реализации на C++, Python и Java.
Всего существует \(3^3=27\) последовательностей.
При \(k=1\) каждая серия обязана иметь длину \(1\), то есть соседние значения всегда должны отличаться. Если первый символ фиксирован, то для двух оставшихся позиций есть по \(2\) варианта, всего \(2^2=4\) продолжения. Значит,
$$N_1(3)=3\cdot 4=12.$$
При \(k=2\) запрещены только постоянные последовательности \(111\), \(222\) и \(333\). Поэтому
$$N_2(3)=27-3=24.$$
Подставляя в формулу хвостовой суммы, получаем
$$f(3)=3\cdot 27-12-24=45.$$
Это совпадает с контрольным значением в реализациях. Там же дополнительно проверяются \(f(7)=1403689\) и \(f(11)=496890792\).
Реализации заранее вычисляют факториалы и обратные факториалы по модулю \(10^9+9\), поэтому любой биномиальный коэффициент из закрытой формулы получается за \(O(1)\). Также заранее строятся таблицы степеней \(n^q\) и \((-(n-1))^q\).
Далее для каждого \(k\) программа вычисляет две коэффициентные суммы для \(A_{n-1,k}\) и \(A_{n-1-k,k}\), превращает их в \(N_k(n)\), суммирует все такие значения и вычитает итог из \(n^{n+1}\). Версия на C++ распараллеливает внешний цикл по \(k\), но математическая схема во всех трёх языках одинакова.
Предвычисление факториалов, обратных факториалов и степеней требует \(O(n)\) времени и \(O(n)\) памяти. Для фиксированного \(k\) внутренняя сумма по \(p\) содержит \(\lfloor (n-1)/(k+1)\rfloor+1\) слагаемых. В сумме по всем \(k\) получаем
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n).$$
Следовательно, весь метод работает за \(O(n\log n)\) времени и использует \(O(n)\) памяти, что несравнимо лучше недостижимого прямого перебора \(O(n^n)\).
تسلسل \(n\)-sequence هو كلمة طولها \(n\) على الأبجدية \(\{1,2,\dots,n\}\)، ولذلك يوجد \(n^n\) تسلسلًا ممكنًا. لكل تسلسل \(S\)، نرمز بـ \(L(S)\) إلى طول أطول كتلة متجاورة من القيم المتساوية. المطلوب هو حساب
$$f(n)=\sum_S L(S)\pmod{10^9+9}.$$
عندما يكون \(n=7{,}500{,}000\) يستحيل العد المباشر لكل التسلسلات، لذلك تعتمد التطبيقات على عدّ التسلسلات التي تحقق \(L(S)\le k\) لكل \(k\)، ثم إعادة تركيب المجموع النهائي من هذه الأعداد.
نعرّف
$$N_k(n)=\#\{S:\,L(S)\le k\}.$$
إذا كان لدينا تسلسل ثابت يحقق \(L(S)=\ell\)، فإن المتباينة \(\ell\le k\) تصح بالضبط لعدد \(n-\ell\) من القيم \(k\) داخل المجموعة \(\{1,2,\dots,n-1\}\). ومن ثم
$$\ell=n-\sum_{k=1}^{n-1}\mathbf{1}_{\ell\le k}.$$
وبجمع هذه الهوية على جميع التسلسلات وعددها \(n^n\) نحصل على
$$f(n)=n\cdot n^n-\sum_{k=1}^{n-1}N_k(n)=n^{n+1}-\sum_{k=1}^{n-1}N_k(n).$$
إذن فالمهمة الأساسية هي إيجاد \(N_k(n)\) بكفاءة لكل \(k\).
لنثبت الرمز الأول. أي تسلسل صالح لا يتجاوز فيه طول أطول كتلة القيمة \(k\) يمكن كتابته على صورة \(r\) كتل متتالية أطوالها
$$\ell_1+\ell_2+\cdots+\ell_r=n,\qquad 1\le \ell_i\le k.$$
بعد تثبيت قيمة الكتلة الأولى، تستطيع كل كتلة لاحقة أن تختار أي رمز من \(n-1\) رموز يختلف عن الكتلة السابقة. لذلك فإن كل تركيب إلى \(r\) أجزاء يساهم بعدد \((n-1)^{r-1}\) من التسلسلات عندما يكون الرمز الأول مثبتًا.
لنرمز بـ \(G_k(M)\) إلى عدد الامتدادات الصالحة ذات الطول \(M\) بعد تثبيت الموضع الأول. عندئذٍ \(N_k(n)=n\,G_k(n-1)\)، ولدينا
$$G_k(n-1)=\sum_{r\ge 1}(n-1)^{r-1}[x^n]\bigl(x+x^2+\cdots+x^k\bigr)^r,$$
حيث ترمز \([x^m]\) إلى معامل \(x^m\).
لنضع
$$R_k(x)=x+x^2+\cdots+x^k=\frac{x(1-x^k)}{1-x}.$$
عندئذٍ يصبح الجمع على عدد الكتل سلسلة هندسية:
$$\sum_{r\ge 1}(n-1)^{r-1}R_k(x)^r=\frac{R_k(x)}{1-(n-1)R_k(x)}.$$
وبالتعويض عن الصيغة المغلقة لـ \(R_k(x)\) نحصل على
$$\frac{x(1-x^k)}{1-nx+(n-1)x^{k+1}}.$$
إذًا إذا أخذنا \(M=n-1\)، فإن
$$G_k(M)=[x^M]\frac{1-x^k}{1-nx+(n-1)x^{k+1}}.$$
ومن المناسب أن نعرّف
$$A_{M,k}=[x^M]\frac{1}{1-nx+(n-1)x^{k+1}}.$$
وبذلك
$$G_k(M)=A_{M,k}-A_{M-k,k},$$
مع الاتفاق على أن \(A_{M,k}=0\) عندما يكون \(M<0\).
نوسّع المقام كسلسلة هندسية:
$$\frac{1}{1-nx+(n-1)x^{k+1}}=\sum_{t\ge 0}\bigl(nx-(n-1)x^{k+1}\bigr)^t.$$
في القوة رقم \(t\)، إذا اخترنا \(p\) عوامل من النوع \(-(n-1)x^{k+1}\) و\(t-p\) عوامل من النوع \(nx\)، فإن أس \(x\) يصبح \(t+pk\). ولكي نصل إلى معامل \(x^M\)، يجب أن يتحقق \(t=M-pk\). ومن هنا نحصل على
$$A_{M,k}=\sum_{p=0}^{\lfloor M/(k+1)\rfloor}\binom{M-pk}{p}\,n^{M-p(k+1)}\bigl(-(n-1)\bigr)^p.$$
وتعاقب الإشارات هنا هو نفس التصحيح الذي يظهر عند استخدام مبدأ الاحتواء والاستبعاد لمعالجة الكتل الأطول من المسموح؛ غير أن اشتقاق الدالة المولدة يجمع هذه الإلغاءات في صيغة واحدة موجزة.
وبالتالي
$$N_k(n)=n\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr),$$
ومن ثم
$$\boxed{f(n)=n^{n+1}-n\sum_{k=1}^{n-1}\bigl(A_{n-1,k}-A_{n-1-k,k}\bigr)\pmod{10^9+9}.}$$
وهذه هي بالضبط الصيغة التي تنفذها تطبيقات C++ وPython وJava.
العدد الكلي للتسلسلات هو \(3^3=27\).
عندما \(k=1\)، يجب أن يكون طول كل كتلة مساويًا لـ \(1\)، أي إن القيم المتجاورة يجب أن تختلف دائمًا. وإذا ثبتنا الرمز الأول، صار لكل من الموضعين الباقيين \(2\) خيارين، أي \(2^2=4\) امتدادات صالحة. لذلك
$$N_1(3)=3\cdot 4=12.$$
وعندما \(k=2\)، تكون التسلسلات الممنوعة الوحيدة هي \(111\) و\(222\) و\(333\). إذن
$$N_2(3)=27-3=24.$$
وباستخدام هوية مجموع الذيل نجد
$$f(3)=3\cdot 27-12-24=45.$$
وهذا يطابق قيمة التحقق الموجودة في التطبيقات. كما تتحقق أيضًا القيمتان \(f(7)=1403689\) و\(f(11)=496890792\).
تقوم التطبيقات أولًا بتهيئة جداول للعوامل والمعكوسات الضربية للعوامل تحت modulo \(10^9+9\)، بحيث يصبح كل معامل ثنائي في الصيغة المغلقة متاحًا في زمن \(O(1)\). كما تهيئ مسبقًا القوى \(n^q\) و\((-(n-1))^q\) اللازمة في المجموع.
بعد ذلك، ولكل \(k\)، تحسب الشيفرة مجموعي المعاملات الموافقين لـ \(A_{n-1,k}\) و\(A_{n-1-k,k}\)، ثم تبني منهما \(N_k(n)\)، وتجمع كل هذه القيم، وفي النهاية تطرح الناتج من \(n^{n+1}\). إصدار C++ يوازي الحلقة الخارجية على \(k\)، لكن البنية الرياضية واحدة في اللغات الثلاث.
تهيئة العوامل والمعكوسات وجداول القوى تكلف \(O(n)\) زمنًا و\(O(n)\) ذاكرة. ولـ \(k\) ثابت، يحتوي المجموع الداخلي على \(\lfloor (n-1)/(k+1)\rfloor+1\) حدًا. وبجمع ذلك على جميع قيم \(k\) نحصل على
$$\sum_{k=1}^{n-1} O\!\left(\frac{n}{k+1}\right)=O(n\log n).$$
إذًا تعمل الطريقة كلها في \(O(n\log n)\) زمنًا و\(O(n)\) ذاكرة، وهو تحسن هائل مقارنة بالعد المباشر المستحيل من رتبة \(O(n^n)\).