Let \(A(n,k)\) be the number of length-\(n\) sequences \((a_1,\dots,a_n)\) such that every term divides \(n\) and
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
The answer is required modulo \(10^9\). Since \(n\) can be enormous, the solution does not build sequences directly. Instead, it compresses the divisor set of \(n\) by residue modulo \(k\), then raises that residue distribution to the \(n\)-th power under cyclic convolution.
Write \(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\), and let \(M=10^9\). The key observation is that only residues modulo \(k\) matter, so the entire counting problem lives inside the cyclic group \(\mathbb{Z}_k\).
For each residue \(r\in\{0,1,\dots,k-1\}\), define
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|.$$
The vector \(\mathbf{c}=(c_0,\dots,c_{k-1})\) records how many one-step choices land in each residue class. This loses no relevant information, because any future sum is reduced modulo \(k\).
Suppose \(\mathbf{f}\) and \(\mathbf{g}\) describe the residue distributions of two independent blocks of choices. If the first block contributes residue \(i\) and the second contributes residue \(j\), then the combined residue is \(i+j \pmod{k}\). Therefore
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
This is circular convolution on \(\mathbb{Z}_k\). After one pick the distribution is \(\mathbf{c}\); after two picks it is \(\mathbf{c}\star\mathbf{c}\); after \(m\) picks it is \(\mathbf{c}^{\star m}\).
The required sequences satisfy
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
So the residue index to extract is
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k.$$
Hence the desired count is
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}.$$
Encode the residue vector as
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
inside the ring \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\). There, \(x^a x^b=x^{(a+b)\bmod k}\), so polynomial multiplication is exactly cyclic convolution. Therefore the coefficient of \(x^t\) in \(P(x)^n\) counts length-\(n\) divisor sequences whose sum is congruent to \(t \pmod{k}\). The answer is the coefficient of \(x^{t^\ast}\).
A direct dynamic program would perform one convolution per position and cost \(O(nk^2)\), which is impossible for the real input. Because convolution is associative, repeated squaring works: compute \(\mathbf{c}, \mathbf{c}^{\star 2}, \mathbf{c}^{\star 4}, \dots\), and combine only the powers corresponding to the set bits of \(n\). This reduces the main cost to \(O(k^2\log n)\).
The divisors of \(3\) are \(1\) and \(3\), so modulo \(4\) the one-step vector is
$$\mathbf{c}=(0,1,0,1).$$
One more convolution gives
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
and the third choice gives
$$\mathbf{c}^{\star 3}=(0,4,0,4).$$
Since
$$t^\ast=(-3)\bmod 4=1,$$
the required component is \(4\). Equivalently, every term is either \(1\) or \(3\), and the total is \(1 \pmod 4\) exactly when an odd number of terms are \(3\), giving \(\binom31+\binom33=4\).
The C++ and Java implementations first factor \(n\) by trial division and then enumerate every divisor recursively from the prime factorization. Those divisors are collapsed into a length-\(k\) count vector according to their residues modulo \(k\).
Next, the implementation performs circular convolution between two length-\(k\) vectors, always reducing arithmetic modulo \(10^9\). The compiled implementations use wider temporary accumulators and reduce periodically so that intermediate products remain safe.
Repeated squaring raises the one-step residue vector to the \(n\)-th convolution power, and the final answer is the component at residue \((-n)\bmod k\). The Python implementation returns the same value by delegating to the compiled solver, so the C++, Python, and Java implementations all follow the same mathematical method.
Factoring \(n\) by trial division costs \(O(\sqrt{n})\) time in the worst case. If \(\tau(n)\) is the number of divisors of \(n\), then enumerating all divisors and filling the residue-count vector costs \(O(\tau(n))\) time and \(O(\tau(n))\) storage.
Each circular convolution of two vectors of length \(k\) costs \(O(k^2)\) time and \(O(k)\) additional working memory. Binary exponentiation uses \(O(\log n)\) such convolutions, so the full method runs in
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
time and uses
$$O\!\left(k+\tau(n)\right)$$
memory. For the actual input size, the convolution phase is the dominant cost.
Sei \(A(n,k)\) die Anzahl der Folgen \((a_1,\dots,a_n)\) der Länge \(n\), bei denen jedes Glied ein Teiler von \(n\) ist und
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
Gesucht ist das Ergebnis modulo \(10^9\). Da \(n\) sehr groß sein kann, zählt die Lösung die Folgen nicht direkt, sondern komprimiert zuerst die Teiler von \(n\) nach ihren Restklassen modulo \(k\) und potenziert diese Restklassenverteilung dann unter zyklischer Faltung.
Schreibe \(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\) und \(M=10^9\). Die zentrale Beobachtung ist, dass für die Endbedingung nur die Reste modulo \(k\) relevant sind. Deshalb lebt das gesamte Problem in der zyklischen Gruppe \(\mathbb{Z}_k\).
Für jeden Rest \(r\in\{0,1,\dots,k-1\}\) definieren wir
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|.$$
Der Vektor \(\mathbf{c}=(c_0,\dots,c_{k-1})\) speichert also, wie viele Ein-Schritt-Wahlen in jede Restklasse fallen. Für die spätere Summenbedingung geht dabei keine Information verloren.
Seien \(\mathbf{f}\) und \(\mathbf{g}\) die Restverteilungen zweier unabhängiger Blöcke. Liefert der erste Block den Rest \(i\) und der zweite den Rest \(j\), dann hat die Gesamtsumme den Rest \(i+j \pmod{k}\). Daher gilt
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
Das ist genau die zirkuläre Faltung auf \(\mathbb{Z}_k\). Nach einer Wahl ist die Verteilung \(\mathbf{c}\), nach zwei Wahlen \(\mathbf{c}\star\mathbf{c}\), nach \(m\) Wahlen \(\mathbf{c}^{\star m}\).
Gesucht sind genau die Folgen mit
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
Also muss am Ende die Komponente mit Index
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k$$
ausgelesen werden. Damit ist
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}.$$
Man kann \(\mathbf{c}\) auch als
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
im Ring \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\) auffassen. Dort gilt \(x^a x^b=x^{(a+b)\bmod k}\), also entspricht Polynom-Multiplikation exakt der zyklischen Faltung. Folglich zählt der Koeffizient von \(x^t\) in \(P(x)^n\) die Folgen der Länge \(n\), deren Summe \(t \pmod{k}\) ist. Gesucht ist also der Koeffizient von \(x^{t^\ast}\).
Eine direkte Dynamik würde für jede Position eine Faltung ausführen und damit \(O(nk^2)\) kosten. Wegen der Assoziativität der Faltung kann man aber wiederholtes Quadrieren verwenden: \(\mathbf{c}\), \(\mathbf{c}^{\star 2}\), \(\mathbf{c}^{\star 4}\), \(\dots\) werden sukzessive aufgebaut, und nur die Potenzen zu gesetzten Bits von \(n\) werden miteinander kombiniert. Dadurch sinken die Hauptkosten auf \(O(k^2\log n)\).
Die Teiler von \(3\) sind \(1\) und \(3\). Modulo \(4\) ergibt das den Ein-Schritt-Vektor
$$\mathbf{c}=(0,1,0,1).$$
Nach einer weiteren Faltung erhält man
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
und nach der dritten Wahl
$$\mathbf{c}^{\star 3}=(0,4,0,4).$$
Weil
$$t^\ast=(-3)\bmod 4=1,$$
ist die gesuchte Komponente gleich \(4\). Direkt kombinatorisch sieht man dasselbe: Jedes Glied ist entweder \(1\) oder \(3\), und die Gesamtsumme ist genau dann \(1 \pmod 4\), wenn eine ungerade Anzahl der Glieder gleich \(3\) ist. Das liefert \(\binom31+\binom33=4\).
Die C++- und Java-Implementierungen zerlegen \(n\) zunächst per Probedivision in Primfaktoren und erzeugen daraus rekursiv alle Teiler. Diese Teiler werden anschließend nach ihren Resten modulo \(k\) in einem Vektor der Länge \(k\) zusammengefasst.
Danach führt die Implementierung zirkuläre Faltungen zwischen zwei Vektoren der Länge \(k\) aus, wobei stets modulo \(10^9\) reduziert wird. Die kompilierten Implementierungen verwenden breitere temporäre Akkumulatoren und reduzieren zwischendurch, damit die Zwischenprodukte sicher bleiben.
Mit wiederholtem Quadrieren wird der Ein-Schritt-Vektor auf die \(n\)-te Faltungspotenz gebracht, und am Ende wird die Komponente zu \((-n)\bmod k\) ausgelesen. Die Python-Implementierung liefert denselben Wert, indem sie dieselbe kompilierte Rechenmethode nutzt; mathematisch arbeiten also alle drei Sprachvarianten identisch.
Die Faktorisierung von \(n\) per Probedivision kostet im Worst Case \(O(\sqrt{n})\) Zeit. Bezeichnet \(\tau(n)\) die Anzahl der Teiler von \(n\), dann benötigen das Auflisten aller Teiler und das Füllen des Restklassenvektors \(O(\tau(n))\) Zeit und \(O(\tau(n))\) Speicher.
Jede zyklische Faltung zweier Vektoren der Länge \(k\) kostet \(O(k^2)\) Zeit und \(O(k)\) zusätzlichen Arbeitsraum. Die binäre Potenzierung verwendet \(O(\log n)\) solcher Faltungen. Insgesamt ergibt das
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
Zeit und
$$O\!\left(k+\tau(n)\right)$$
Speicher. Für die echten Parameter dominiert die Faltungsphase.
\(A(n,k)\), uzunluğu \(n\) olan \((a_1,\dots,a_n)\) dizilerinin sayısı olsun; burada her terim \(n\)'in bir bölenidir ve
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
Sonuç \(10^9\) modunda istenir. \(n\) çok büyük olabildiği için çözüm dizileri tek tek üretmez. Bunun yerine önce \(n\)'in bölenlerini \(k\) modundaki artık sınıflarına göre toplar, sonra bu dağılımı döngüsel konvolüsyon altında \(n\)-inci kuvvete yükseltir.
\(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\) ve \(M=10^9\) olsun. Ana gözlem şudur: son koşul yalnızca \(k\) modundaki artıklarla ilgilidir. Bu yüzden tüm sayım problemi \(\mathbb{Z}_k\) çevrimsel grubunda ifade edilebilir.
Her \(r\in\{0,1,\dots,k-1\}\) için
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|$$
tanımını yapalım. \(\mathbf{c}=(c_0,\dots,c_{k-1})\) vektörü, tek adımda kaç seçimin hangi artık sınıfına düştüğünü gösterir. Toplamlar sonunda yine \(k\) moduna indirgeneceği için bu özetleme hiçbir gerekli bilgiyi kaybettirmez.
\(\mathbf{f}\) ve \(\mathbf{g}\) iki bağımsız seçim bloğunun artık dağılımları olsun. İlk blok \(i\), ikinci blok \(j\) artığını veriyorsa toplam artık \(i+j \pmod{k}\) olur. Dolayısıyla
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
Bu, \(\mathbb{Z}_k\) üzerindeki dairesel konvolüsyondur. Bir seçim sonrası dağılım \(\mathbf{c}\), iki seçim sonrası \(\mathbf{c}\star\mathbf{c}\), \(m\) seçim sonrası ise \(\mathbf{c}^{\star m}\) olur.
Aranan diziler tam olarak
$$a_1+\cdots+a_n \equiv -n \pmod{k}$$
koşulunu sağlar. Bu yüzden okunacak hedef indis
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k$$
olur. Demek ki cevap
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}$$
şeklindedir.
\(\mathbf{c}\) vektörünü
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
polinomu ile \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\) halkasında temsil edebiliriz. Burada \(x^a x^b=x^{(a+b)\bmod k}\) olduğundan polinom çarpımı tam olarak döngüsel konvolüsyona karşılık gelir. O halde \(P(x)^n\) içindeki \(x^t\) katsayısı, toplamı \(t \pmod{k}\) olan uzunluğu \(n\) dizilerin sayısıdır. Aranan katsayı \(x^{t^\ast}\) katsayısıdır.
Doğrudan bir dinamik program her konum için bir konvolüsyon yapar ve \(O(nk^2)\) maliyet çıkarır. Gerçek girdiler için bu kabul edilemez. Konvolüsyon birleşmeli olduğu için tekrar kare alma kullanılır: \(\mathbf{c}\), \(\mathbf{c}^{\star 2}\), \(\mathbf{c}^{\star 4}\), \(\dots\) sırasıyla hesaplanır; sonra sadece \(n\)'in ikili açılımında 1 olan bitlere karşılık gelen kuvvetler birleştirilir. Böylece ana maliyet \(O(k^2\log n)\)'ye iner.
\(3\)'ün bölenleri \(1\) ve \(3\)'tür. Bunların \(4\) modundaki bir-adım vektörü
$$\mathbf{c}=(0,1,0,1)$$
olur. Bir konvolüsyon daha yapınca
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
üçüncü seçimden sonra ise
$$\mathbf{c}^{\star 3}=(0,4,0,4)$$
elde edilir. Çünkü
$$t^\ast=(-3)\bmod 4=1,$$
aranan bileşen \(4\)'tür. Aynı şeyi doğrudan da görebiliriz: her terim ya \(1\) ya \(3\) olur; toplamın \(1 \pmod 4\) olması ancak \(3\) değerinin tek sayıda seçilmesiyle mümkündür. Bu da \(\binom31+\binom33=4\) verir.
C++ ve Java implementasyonları önce \(n\)'i deneme bölmesiyle asal çarpanlara ayırır, ardından bu ayrışımdan tüm bölenleri özyinelemeli olarak üretir. Sonra bölenler, \(k\) modundaki artıklarına göre uzunluğu \(k\) olan bir sayım vektörüne dönüştürülür.
Daha sonra implementasyon, uzunluğu \(k\) olan iki vektör arasında dairesel konvolüsyon uygular ve tüm aritmetiği \(10^9\) modunda tutar. Derlenmiş sürümler taşma riskini azaltmak için daha geniş geçici toplayıcılar kullanır ve ara adımlarda periyodik mod indirgemesi yapar.
Tekrar kare alma yöntemiyle tek-adım vektörü \(n\)-inci konvolüsyon kuvvetine çıkarılır, ardından \((-n)\bmod k\) artık sınıfındaki bileşen okunur. Python implementasyonu da aynı sonucu derlenmiş çözücüye başvurarak döndürdüğü için C++, Python ve Java yolları aynı matematiği uygular.
\(n\)'in deneme bölmesiyle çarpanlara ayrılması en kötü durumda \(O(\sqrt{n})\) zaman alır. \(\tau(n)\), \(n\)'in bölen sayısı olsun. Tüm bölenleri üretmek ve artık sayım vektörünü doldurmak \(O(\tau(n))\) zaman ve \(O(\tau(n))\) bellek gerektirir.
Uzunluğu \(k\) olan iki vektörün her dairesel konvolüsyonu \(O(k^2)\) zaman ve \(O(k)\) ek çalışma alanı ister. İkili üs alma \(O(\log n)\) adet böyle konvolüsyon kullanır. Sonuç olarak toplam karmaşıklık
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
zaman ve
$$O\!\left(k+\tau(n)\right)$$
bellektir. Gerçek parametrelerde baskın terim konvolüsyon aşamasıdır.
Sea \(A(n,k)\) el número de secuencias \((a_1,\dots,a_n)\) de longitud \(n\) tales que cada término divide a \(n\) y
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
La respuesta se pide módulo \(10^9\). Como \(n\) puede ser gigantesco, la solución no enumera secuencias una por una. En su lugar, agrupa primero los divisores de \(n\) por su residuo módulo \(k\) y luego eleva esa distribución al exponente \(n\) usando convolución cíclica.
Escribamos \(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\) y \(M=10^9\). La observación clave es que solo importan los residuos módulo \(k\), así que todo el problema se traslada al grupo cíclico \(\mathbb{Z}_k\).
Para cada residuo \(r\in\{0,1,\dots,k-1\}\), definimos
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|.$$
El vector \(\mathbf{c}=(c_0,\dots,c_{k-1})\) indica cuántas elecciones de un solo paso caen en cada clase residual. Esa compresión es suficiente porque al final todas las sumas se consideran módulo \(k\).
Sean \(\mathbf{f}\) y \(\mathbf{g}\) las distribuciones de residuos de dos bloques independientes. Si el primer bloque produce residuo \(i\) y el segundo residuo \(j\), entonces el bloque total produce \(i+j \pmod{k}\). Por tanto
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
Esta es la convolución circular en \(\mathbb{Z}_k\). Tras una elección la distribución es \(\mathbf{c}\); tras dos elecciones, \(\mathbf{c}\star\mathbf{c}\); tras \(m\) elecciones, \(\mathbf{c}^{\star m}\).
Las secuencias buscadas satisfacen
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
Luego el índice que debemos leer al final es
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k.$$
En consecuencia, la cantidad pedida es
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}.$$
También podemos codificar \(\mathbf{c}\) mediante
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
dentro del anillo cociente \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\). Allí se cumple \(x^a x^b=x^{(a+b)\bmod k}\), así que multiplicar polinomios es exactamente lo mismo que aplicar convolución cíclica. Por eso el coeficiente de \(x^t\) en \(P(x)^n\) cuenta cuántas secuencias de longitud \(n\) tienen suma congruente con \(t \pmod{k}\). La respuesta es el coeficiente de \(x^{t^\ast}\).
Un DP directo haría una convolución por posición y costaría \(O(nk^2)\), algo inviable cuando \(n\) es enorme. Como la convolución es asociativa, se usa potenciación rápida: se calculan \(\mathbf{c}\), \(\mathbf{c}^{\star 2}\), \(\mathbf{c}^{\star 4}\), \(\dots\), y solo se combinan las potencias correspondientes a los bits activos de \(n\). Así, el coste dominante baja a \(O(k^2\log n)\).
Los divisores de \(3\) son \(1\) y \(3\), de modo que módulo \(4\) obtenemos
$$\mathbf{c}=(0,1,0,1).$$
Una convolución más da
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
y la tercera elección produce
$$\mathbf{c}^{\star 3}=(0,4,0,4).$$
Como
$$t^\ast=(-3)\bmod 4=1,$$
la componente requerida vale \(4\). También puede verse de forma directa: cada término es \(1\) o \(3\), y la suma es \(1 \pmod 4\) exactamente cuando aparece un número impar de treses. Eso ocurre en \(\binom31+\binom33=4\) secuencias.
Las implementaciones en C++ y Java primero factorizan \(n\) por división de prueba y luego generan recursivamente todos sus divisores a partir de esa factorización prima. Después agrupan esos divisores en un vector de longitud \(k\) según su residuo módulo \(k\).
A continuación, la implementación realiza convoluciones circulares entre vectores de longitud \(k\), siempre trabajando módulo \(10^9\). Las versiones compiladas usan acumuladores temporales más anchos y reducciones periódicas para mantener seguras las multiplicaciones intermedias.
La exponenciación binaria eleva el vector de un paso a la potencia de convolución \(n\), y al final se lee la componente correspondiente a \((-n)\bmod k\). La implementación en Python devuelve el mismo valor delegando en el solucionador compilado, de modo que C++, Python y Java siguen exactamente el mismo método matemático.
Factorizar \(n\) por división de prueba cuesta \(O(\sqrt{n})\) tiempo en el peor caso. Si \(\tau(n)\) es el número de divisores de \(n\), enumerarlos todos y rellenar el vector de residuos cuesta \(O(\tau(n))\) tiempo y \(O(\tau(n))\) memoria.
Cada convolución circular entre dos vectores de longitud \(k\) cuesta \(O(k^2)\) tiempo y \(O(k)\) memoria auxiliar. La exponenciación binaria necesita \(O(\log n)\) convoluciones de ese tipo. Por tanto, el método completo ejecuta
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
operaciones y usa
$$O\!\left(k+\tau(n)\right)$$
memoria. En la entrada real, la fase dominante es la de convolución.
设 \(A(n,k)\) 表示长度为 \(n\) 的序列 \((a_1,\dots,a_n)\) 的个数，其中每一项都必须是 \(n\) 的因子，并且满足
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
答案对 \(10^9\) 取模。由于 \(n\) 可以非常大，程序不可能逐个构造所有序列。真正可行的做法是先把 \(n\) 的全部因子按照模 \(k\) 的余数分类，再在循环卷积的意义下把这个“单步分布”提升到第 \(n\) 次幂。
记 \(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\)，并令 \(M=10^9\)。关键观察是：最终条件只关心总和对 \(k\) 的余数，因此所有计数都可以放到循环群 \(\mathbb{Z}_k\) 上来处理。
对于每个余数 \(r\in\{0,1,\dots,k-1\}\)，定义
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|.$$
于是得到向量 \(\mathbf{c}=(c_0,\dots,c_{k-1})\)。这个向量的含义非常直接：如果只选一个因子，那么落在余数 \(r\) 的选择一共有 \(c_r\) 个。因为以后所有和都只在模 \(k\) 意义下比较，所以把具体因子值压缩成余数频数不会丢失任何与答案有关的信息。
设 \(\mathbf{f}\) 和 \(\mathbf{g}\) 分别表示两个独立选择块的余数分布。如果前一块的总余数是 \(i\)，后一块的总余数是 \(j\)，那么合并后的总余数就是 \(i+j \pmod{k}\)。因此合并规则为
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
这就是 \(\mathbb{Z}_k\) 上的循环卷积。于是，选一次时的分布是 \(\mathbf{c}\)，选两次时的分布是 \(\mathbf{c}\star\mathbf{c}\)，选 \(m\) 次时的分布就是 \(\mathbf{c}^{\star m}\)。换句话说，原问题已经从“计数序列”转化成了“计算卷积幂”。
我们只关心满足
$$a_1+\cdots+a_n \equiv -n \pmod{k}$$
的序列，所以最后要读取的目标下标是
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k.$$
因此答案可以简洁地写成
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}.$$
到这里为止，问题的数学结构已经完全清楚：一切都取决于“单步余数分布” \(\mathbf{c}\) 的第 \(n\) 次循环卷积幂。
把 \(\mathbf{c}\) 编码成多项式
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
并在商环 \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\) 中进行运算。在这个环里，\(x^k=1\)，所以
$$x^a x^b=x^{(a+b)\bmod k}.$$
这恰好和模 \(k\) 的余数相加完全一致。因此，\(P(x)^n\) 中 \(x^t\) 的系数，正是长度为 \(n\) 的因子序列中“总和同余于 \(t \pmod{k}\)”的序列个数。我们最后只需取出 \(x^{t^\ast}\) 的系数即可。
如果直接按位置做动态规划，那么每增加一个位置就要做一次长度 \(k\) 的卷积，总时间会变成 \(O(nk^2)\)。当 \(n\) 极大时，这显然不可行。由于循环卷积满足结合律，我们可以像普通乘方那样使用二进制快速幂：依次构造 \(\mathbf{c}\)、\(\mathbf{c}^{\star 2}\)、\(\mathbf{c}^{\star 4}\)、\(\mathbf{c}^{\star 8}\) 等幂，然后只把对应于 \(n\) 的二进制展开中为 1 的那些幂卷积起来。这样，核心计算量就从与 \(n\) 线性相关，降到了 \(O(k^2\log n)\)。
当 \(n=3\) 时，因子只有 \(1\) 和 \(3\)。模 \(4\) 后得到的单步分布是
$$\mathbf{c}=(0,1,0,1).$$
卷积一次以后，得到
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
再卷积一次，得到
$$\mathbf{c}^{\star 3}=(0,4,0,4).$$
而目标余数是
$$t^\ast=(-3)\bmod 4=1,$$
所以答案就是第 1 项，即 \(4\)。也可以直接验证：每个位置只能取 \(1\) 或 \(3\)，总和模 \(4\) 等于 \(1\) 当且仅当序列中 \(3\) 的个数为奇数，所以共有 \(\binom31+\binom33=4\) 个序列。
C++ 和 Java 实现先用试除法分解 \(n\) 的质因数，再根据质因数分解递归生成全部因子。随后把这些因子按模 \(k\) 的余数汇总成一个长度为 \(k\) 的计数向量。
接下来，程序在两个长度为 \(k\) 的向量之间执行循环卷积，并且所有运算都在模 \(10^9\) 下进行。编译型实现会使用更宽的临时累加器，并在中间阶段定期取模，以避免乘法累积造成溢出风险。
之后用二进制快速幂把单步向量提升为第 \(n\) 次卷积幂，最后读取下标 \((-n)\bmod k\) 对应的分量。Python 实现返回相同的结果，它调用的是同一套编译求解逻辑，因此三种语言版本遵循的是完全一致的数学算法。
用试除法分解 \(n\) 在最坏情况下需要 \(O(\sqrt{n})\) 时间。若 \(\tau(n)\) 表示 \(n\) 的因子个数，那么生成全部因子并构造余数计数向量需要 \(O(\tau(n))\) 时间和 \(O(\tau(n))\) 存储。
长度为 \(k\) 的两个向量做一次循环卷积需要 \(O(k^2)\) 时间和 \(O(k)\) 额外工作空间。二进制快速幂总共要做 \(O(\log n)\) 次这样的卷积，因此整体复杂度是
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
时间，以及
$$O\!\left(k+\tau(n)\right)$$
空间。对实际输入而言，真正主导运行时间的是卷积幂阶段。
Пусть \(A(n,k)\) обозначает число последовательностей \((a_1,\dots,a_n)\) длины \(n\), в которых каждый элемент является делителем числа \(n\), и при этом
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
Ответ требуется по модулю \(10^9\). Поскольку \(n\) может быть очень большим, решение не строит последовательности напрямую. Вместо этого оно сначала группирует делители \(n\) по остаткам modulo \(k\), а затем возводит полученное распределение в \(n\)-ю степень относительно циклической свертки.
Обозначим \(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\) и положим \(M=10^9\). Основная идея состоит в том, что для условия на сумму важны только остатки по модулю \(k\), поэтому всю задачу можно перенести в циклическую группу \(\mathbb{Z}_k\).
Для каждого остатка \(r\in\{0,1,\dots,k-1\}\) введем
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|.$$
Вектор \(\mathbf{c}=(c_0,\dots,c_{k-1})\) показывает, сколько одношаговых выборов попадает в каждый остаток. Для дальнейшего подсчета этого достаточно, потому что в конце все суммы все равно рассматриваются только по модулю \(k\).
Пусть \(\mathbf{f}\) и \(\mathbf{g}\) описывают распределения остатков для двух независимых блоков. Если первый блок дает остаток \(i\), а второй остаток \(j\), то вместе они дают \(i+j \pmod{k}\). Поэтому
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
Это и есть круговая свертка на \(\mathbb{Z}_k\). После одного выбора распределение равно \(\mathbf{c}\), после двух выборов оно равно \(\mathbf{c}\star\mathbf{c}\), а после \(m\) выборов получаем \(\mathbf{c}^{\star m}\).
Нас интересуют только те последовательности, для которых
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
Следовательно, в конце нужно взять компоненту с индексом
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k.$$
Тем самым ответ записывается как
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}.$$
Удобно закодировать \(\mathbf{c}\) полиномом
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
и работать в фактор-кольце \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\). В нем выполняется равенство \(x^a x^b=x^{(a+b)\bmod k}\), то есть умножение полиномов точно соответствует сложению остатков по модулю \(k\). Поэтому коэффициент при \(x^t\) в \(P(x)^n\) равен числу последовательностей длины \(n\), сумма которых сравнима с \(t\) по модулю \(k\). Нас интересует коэффициент при \(x^{t^\ast}\).
Если двигаться по позициям напрямую, пришлось бы выполнять одну свертку на каждый шаг, а это \(O(nk^2)\) времени. Для реального значения \(n\) такой подход неприемлем. Поскольку свертка ассоциативна, можно применить двоичное возведение в степень: вычислить \(\mathbf{c}\), \(\mathbf{c}^{\star 2}\), \(\mathbf{c}^{\star 4}\), \(\mathbf{c}^{\star 8}\) и так далее, а затем объединить только те степени, которые соответствуют единичным битам двоичной записи числа \(n\). Это снижает основную стоимость до \(O(k^2\log n)\).
У числа \(3\) есть только два делителя: \(1\) и \(3\). Следовательно, одношаговый вектор по модулю \(4\) равен
$$\mathbf{c}=(0,1,0,1).$$
После одной дополнительной свертки получаем
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
а после третьего выбора
$$\mathbf{c}^{\star 3}=(0,4,0,4).$$
Так как
$$t^\ast=(-3)\bmod 4=1,$$
ответ равен \(4\). Это же легко увидеть напрямую: каждый элемент равен либо \(1\), либо \(3\), а сумма дает остаток \(1\) по модулю \(4\) тогда и только тогда, когда троек выбрано нечетное число. Это дает \(\binom31+\binom33=4\).
Реализации на C++ и Java сначала раскладывают \(n\) на простые множители методом пробного деления, после чего рекурсивно строят список всех делителей. Затем эти делители агрегируются в вектор длины \(k\) по остаткам modulo \(k\).
После этого реализация выполняет циклическую свертку двух векторов длины \(k\), постоянно работая по модулю \(10^9\). Компилируемые версии используют более широкие временные аккумуляторы и периодически делают редукцию по модулю, чтобы промежуточные произведения оставались безопасными.
Далее двоичное возведение в степень строит \(n\)-ю свертку исходного одношагового вектора, а в конце считывается компонента с индексом \((-n)\bmod k\). Python-реализация возвращает то же значение, обращаясь к той же скомпилированной вычислительной схеме, поэтому все три языковые версии опираются на один и тот же алгоритм.
Разложение числа \(n\) пробным делением занимает \(O(\sqrt{n})\) времени в худшем случае. Если \(\tau(n)\) обозначает число делителей \(n\), то перечисление всех делителей и заполнение вектора частот требует \(O(\tau(n))\) времени и \(O(\tau(n))\) памяти.
Одна циклическая свертка двух векторов длины \(k\) стоит \(O(k^2)\) времени и \(O(k)\) дополнительной памяти. Двоичное возведение в степень использует \(O(\log n)\) таких сверток, так что полный метод работает за
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
и использует
$$O\!\left(k+\tau(n)\right)$$
памяти. На реальном наборе параметров основную стоимость дает именно стадия свертки.
لنرمز بـ \(A(n,k)\) إلى عدد المتتاليات \((a_1,\dots,a_n)\) ذات الطول \(n\)، بحيث يكون كل حد فيها قاسمًا للعدد \(n\)، وتحقق كذلك الشرط
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
المطلوب هو هذه القيمة بترديد \(10^9\). وبما أن \(n\) قد يكون كبيرًا جدًا، فلا يمكن تعداد جميع المتتاليات مباشرة. الفكرة العملية هي ضغط مجموعة قواسم \(n\) بحسب بواقيها modulo \(k\)، ثم رفع هذا التوزيع إلى القوة \(n\) تحت الالتفاف الدائري.
لنكتب \(D(n)=\{d\in\mathbb{Z}_{>0}: d\mid n\}\)، ولنضع \(M=10^9\). الملاحظة الأساسية هي أن الشرط النهائي لا يعتمد إلا على البواقي modulo \(k\)، ولذلك يمكن نقل المسألة كلها إلى الزمرة الدورية \(\mathbb{Z}_k\).
لكل باقٍ \(r\in\{0,1,\dots,k-1\}\) نعرّف
$$c_r=\left|\left\{d\in D(n): d\equiv r \pmod{k}\right\}\right|.$$
إذن المتجه \(\mathbf{c}=(c_0,\dots,c_{k-1})\) يخبرنا بعدد الاختيارات ذات الخطوة الواحدة التي تقع في كل فئة باقية. ولا تضيع أي معلومة مهمة هنا، لأننا في النهاية لا نقارن إلا المجاميع modulo \(k\).
إذا كان \(\mathbf{f}\) و\(\mathbf{g}\) يصفان توزّعي البواقي لكتلتين مستقلتين من الاختيارات، وكان مجموع الكتلة الأولى يعطي الباقي \(i\) والثانية تعطي الباقي \(j\)، فإن المجموع الكلي يعطي \(i+j \pmod{k}\). لذلك يكون
$$\left(\mathbf{f}\star\mathbf{g}\right)_t=\sum_{i=0}^{k-1} f_i\,g_{(t-i)\bmod k}.$$
وهذا هو الالتفاف الدائري على \(\mathbb{Z}_k\). بعد اختيار واحد يكون التوزيع هو \(\mathbf{c}\)، وبعد اختيارين يصبح \(\mathbf{c}\star\mathbf{c}\)، وبعد \(m\) اختيارات نحصل على \(\mathbf{c}^{\star m}\).
المتتاليات المطلوبة هي التي تحقق
$$a_1+\cdots+a_n \equiv -n \pmod{k}.$$
ولهذا فالمؤشر الذي نحتاج إلى قراءته في النهاية هو
$$t^\ast=(-n)\bmod k=\bigl(k-(n\bmod k)\bigr)\bmod k.$$
وبالتالي يصبح الجواب
$$A(n,k)=\left(\mathbf{c}^{\star n}\right)_{t^\ast}\pmod{M}.$$
يمكن أيضًا تمثيل \(\mathbf{c}\) على صورة
$$P(x)=\sum_{r=0}^{k-1} c_r x^r$$
داخل الحلقة القِسمية \((\mathbb{Z}/M\mathbb{Z})[x]/(x^k-1)\). في هذه الحلقة لدينا \(x^a x^b=x^{(a+b)\bmod k}\)، ولذلك يطابق ضرب كثيرات الحدود تمامًا جمع البواقي modulo \(k\). ومن ثم فإن معامل \(x^t\) في \(P(x)^n\) يساوي عدد المتتاليات ذات الطول \(n\) التي يكون مجموعها مكافئًا لـ \(t \pmod{k}\). والمطلوب هو معامل \(x^{t^\ast}\).
لو استُخدم برنامج ديناميكي مباشر، لاحتجنا إلى التفاف واحد عند كل موضع، أي إلى \(O(nk^2)\) من الزمن، وهذا غير عملي عندما يكون \(n\) ضخمًا. لكن بما أن الالتفاف تجميعي، فيمكن استعمال التربيع المتكرر: نحسب \(\mathbf{c}\)، ثم \(\mathbf{c}^{\star 2}\)، ثم \(\mathbf{c}^{\star 4}\)، وهكذا، وبعد ذلك ندمج فقط القوى التي تقابل البتات المفعّلة في التمثيل الثنائي للعدد \(n\). وبهذا تنخفض الكلفة الرئيسية إلى \(O(k^2\log n)\).
قواسم العدد \(3\) هي \(1\) و\(3\)، ولذلك يكون متجه الخطوة الواحدة modulo \(4\) هو
$$\mathbf{c}=(0,1,0,1).$$
بعد التفاف إضافي نحصل على
$$\mathbf{c}^{\star 2}=(2,0,2,0),$$
وبعد الاختيار الثالث يصبح
$$\mathbf{c}^{\star 3}=(0,4,0,4).$$
ولأن
$$t^\ast=(-3)\bmod 4=1,$$
فالجواب هو المركبة ذات الفهرس \(1\)، أي \(4\). ويمكن رؤية ذلك مباشرة أيضًا: كل حد إما \(1\) أو \(3\)، ويكون المجموع مساويًا لـ \(1 \pmod 4\) إذا وفقط إذا كان عدد الثلاثات المختارة فرديًا، وهذا يعطي \(\binom31+\binom33=4\).
تبدأ تطبيقات C++ وJava بتحليل \(n\) إلى عوامله الأولية عن طريق القسمة التجريبية، ثم توليد جميع القواسم بشكل تكراري اعتمادًا على هذا التحليل. بعد ذلك تُجمَّع القواسم في متجه طوله \(k\) بحسب بواقيها modulo \(k\).
بعدها تنفذ الشيفرة التفافًا دائريًا بين متجهين بطول \(k\)، مع إبقاء الحسابات كلها بترديد \(10^9\). وتستعمل النسخ المترجمة مجمّعات مؤقتة أوسع مع اختزال دوري أثناء الحساب حتى تبقى القيم الوسيطة ضمن المجال الآمن.
ثم يرفع الأسّ الثنائي متجه الخطوة الواحدة إلى قوة الالتفاف \(n\)، وفي النهاية تُقرأ المركبة الموافقة للباقي \((-n)\bmod k\). أما تنفيذ Python فيعيد القيمة نفسها بالاعتماد على المحلل المترجم نفسه، ولذلك تتبع تطبيقات C++ وPython وJava المنهج الرياضي ذاته.
تحليل العدد \(n\) بالقسمة التجريبية يكلف \(O(\sqrt{n})\) زمنًا في أسوأ حالة. وإذا رمزنا بعدد قواسم \(n\) بـ \(\tau(n)\)، فإن توليد جميع القواسم وبناء متجه عدادات البواقي يكلف \(O(\tau(n))\) زمنًا و\(O(\tau(n))\) تخزينًا.
كل التفاف دائري بين متجهين بطول \(k\) يكلف \(O(k^2)\) زمنًا و\(O(k)\) ذاكرة عمل إضافية. ويحتاج الأسّ الثنائي إلى \(O(\log n)\) من هذه الالتفافات. إذن تعمل الطريقة كلها بزمن
$$O\!\left(\sqrt{n}+\tau(n)+k^2\log n\right)$$
وباستخدام ذاكرة
$$O\!\left(k+\tau(n)\right).$$
وبالنسبة إلى القيم الفعلية للمسألة، فإن مرحلة قوى الالتفاف هي الجزء المسيطر من الكلفة.