Place \(n\) bowls in a circle, with one bean in each bowl. Starting from a chosen bowl, Peter removes all beans from the current bowl and drops them one by one into successive bowls clockwise. The next move starts from the bowl that received the last bean. Let \(M(n)\) be the number of moves required until the initial all-ones configuration appears again. The problem asks for
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$$
A direct simulation is easy for small \(n\), but the upper limit \(10^{18}\) makes brute force completely infeasible. The solution therefore isolates a closed form for the special arguments \(2^k+1\), then sums that formula as three geometric series.
Number the bowls \(0,1,\dots,n-1\), let \(b_i\) be the bean count in bowl \(i\), and let \(p\) be the current bowl. If the current bowl contains \(t=b_p\) beans, one move performs
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
The initial state is \((1,1,\dots,1)\). The helper routine simulate_M in the C++ source implements
exactly this rule and repeats it until the all-ones state reappears. This gives a literal definition of
\(M(n)\).
The nontrivial combinatorial ingredient used by the solver is the identity
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
The code treats this as the central lemma and verifies it against explicit simulation for small \(k\). The first values are:
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
which match
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53.$$
The implementation also checks the statement values \(M(5)=15\) and \(M(100)=10920\) by direct simulation before computing the final answer.
Set
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$$
Substituting the closed form and splitting the sum termwise gives
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$$
So the original process problem is reduced to three standard geometric sums.
For any ratio \(r\neq 1\),
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$$
Applying this identity to the three terms:
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
Therefore
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
This is the exact closed form the code evaluates, with \(E=10^{18}\).
The required modulus is
$$m=7^9=40{,}353{,}607.$$
Because \(m\) is odd and not divisible by \(3\), both \(2\) and \(3\) are invertible modulo \(m\). Thus the divisions in the geometric-series formula can be replaced by multiplication with modular inverses:
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
The only large quantities left are \(2^{E+1}\), \(3^{E+1}\), and \(4^{E+1}\) modulo \(m\). These are computed by binary exponentiation, so the huge exponent \(10^{18}+1\) is handled in \(O(\log E)\) multiplications rather than \(O(E)\).
The C++ file has two clearly separated parts. First, simulate_M and run_validations
perform checkpoint verification on small inputs, including the statement values and the formula
\(M(2^k+1)=2^{k+1}+4^k-3^k\) for \(k=0,\dots,8\). Second, solve() computes the modular inverses of
\(2\) and \(3\), evaluates
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$$
forms the three partial sums sum_2, sum_4, and sum_3, and combines them as
(sum_2 + sum_4 - sum_3) mod m. The Python version mirrors the same mathematics using
pow(base, exp, mod) and Python's built-in modular inverse. The Java version uses the same repeated
squaring logic and obtains inverses through BigInteger.modInverse.
The final computation needs only three modular exponentiations and a constant number of modular arithmetic operations, so it runs in \(O(\log E)\) time and \(O(1)\) memory. Directly simulating the bean process up to \(10^{18}\) terms would be hopelessly too slow; simulation appears only in the fixed-size validation phase.
Es gibt \(n\) Schalen in einem Kreis, anfangs mit jeweils einer Bohne. Peter nimmt aus der aktuellen Schale alle Bohnen heraus und legt sie einzeln im Uhrzeigersinn in die folgenden Schalen. Der naechste Zug beginnt bei der Schale, in die die letzte Bohne gefallen ist. Mit \(M(n)\) bezeichnen wir die Anzahl der Zuege, bis die Anfangskonfiguration aus lauter Einsen wieder erscheint. Gesucht ist
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$$
Fuer kleine \(n\) kann man die Definition direkt simulieren. Fuer die Grenze \(10^{18}\) muss man die Aufgabe jedoch auf eine geschlossene Formel fuer die Spezialwerte \(2^k+1\) und anschliessend auf geometrische Reihen reduzieren.
Nummeriere die Schalen mit \(0,1,\dots,n-1\), sei \(b_i\) die Bohnenzahl in Schale \(i\) und \(p\) die aktuelle Position. Befinden sich in der aktuellen Schale \(t=b_p\) Bohnen, dann besteht ein Zug aus
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
Der Startzustand ist \((1,1,\dots,1)\). Die Hilfsfunktion simulate_M in C++ implementiert genau diese
Vorschrift und wiederholt sie so lange, bis die Eins-Konfiguration erneut erreicht ist. Damit wird \(M(n)\) direkt
definiert.
Der nichttriviale kombinatorische Kern der Loesung ist die Identitaet
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
Der Code verwendet diese Formel als zentrales Lemma und prueft sie fuer kleine \(k\) explizit gegen die Simulation. Die ersten Werte sind
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
und sie stimmen mit
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53$$
ueberein. Zusaetzlich validiert die Implementierung die Aufgabenwerte \(M(5)=15\) und \(M(100)=10920\) durch direkte Simulation.
Setze
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$$
Nach Einsetzen der geschlossenen Formel und termweiser Aufspaltung ergibt sich
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$$
Damit wird das urspruengliche Prozessproblem auf drei Standardreihen reduziert.
Fuer \(r\neq 1\) gilt
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$$
Also
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
Daraus folgt
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
Genau diese geschlossene Form wertet das Programm fuer \(E=10^{18}\) aus.
Der geforderte Modul lautet
$$m=7^9=40{,}353{,}607.$$
Da \(m\) weder durch \(2\) noch durch \(3\) teilbar ist, besitzen beide Zahlen modulare Inverse modulo \(m\). Die Divisionen werden daher ersetzt durch
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
Es muessen also nur noch \(2^{E+1}\), \(3^{E+1}\) und \(4^{E+1}\) modulo \(m\) berechnet werden. Das geschieht per binaerer Exponentiation in \(O(\log E)\) statt durch lineares Hochmultiplizieren.
Die C++-Loesung besteht aus zwei klaren Teilen. Zuerst pruefen simulate_M und
run_validations kleine Testfaelle, darunter die Aufgabenwerte sowie die Formel
\(M(2^k+1)=2^{k+1}+4^k-3^k\) fuer \(k=0,\dots,8\). Danach berechnet solve() die modularen Inversen
von \(2\) und \(3\), bestimmt
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$$
bildet daraus sum_2, sum_4 und sum_3 und kombiniert alles zu
(sum_2 + sum_4 - sum_3) mod m. Python verwendet dieselbe Mathematik ueber
pow(base, exp, mod); Java nutzt dieselbe Potenzierung per Quadrieren und
BigInteger.modInverse fuer die modularen Inversen.
Die eigentliche Endberechnung benoetigt nur drei modulare Potenzen und konstant viele weitere Operationen, also \(O(\log E)\) Zeit und \(O(1)\) Speicher. Die direkte Simulation wird nur fuer eine feste kleine Menge von Validierungstests eingesetzt.
\(n\) tane kap bir çember üzerine diziliyor ve her kapta başlangıçta bir fasulye bulunuyor. Peter bulunduğu kaptaki bütün fasulyeleri alıp saat yönünde ilerleyerek sonraki kaplara birer birer bırakıyor. Son bıraktığı fasulyenin düştüğü kap, bir sonraki hamlenin başlangıç noktası oluyor. Başlangıçtaki tüm kapların birer fasulye içerdiği durum yeniden ortaya çıkana kadar geçen hamle sayısına \(M(n)\) diyelim. Sorulan ifade
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}$$
değeridir. Klasik simülasyon küçük \(n\) için mümkündür; fakat \(10^{18}\) gibi bir üst sınırda tek çözüm yolu, \(2^k+1\) biçimindeki girdiler için kapalı form bulup bunu geometrik serilere indirgemektir.
Kapları \(0,1,\dots,n-1\) ile numaralandıralım, \(b_i\) kap \(i\)'deki fasulye sayısı, \(p\) ise mevcut konum olsun. Eğer mevcut kapta \(t=b_p\) fasulye varsa, bir hamle şu dönüşümü yapar:
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
Başlangıç durumu \((1,1,\dots,1)\)'dir. C++ kaynağındaki simulate_M yordamı tam olarak bu kuralı
uygular ve tüm kaplar yeniden birer fasulyeye dönene kadar devam eder. Böylece \(M(n)\) doğrudan tanımından
hesaplanmış olur.
Çözümün asıl, zor ama güçlü gözlemi şu özdeşliktir:
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
Kod bu özdeşliği temel lemma olarak kullanıyor ve küçük \(k\) değerlerinde doğrudan simülasyonla doğruluyor. İlk birkaç değer şöyledir:
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
ve bunlar
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53$$
ile birebir uyuşur. Ayrıca kod, problem metninde verilen \(M(5)=15\) ve \(M(100)=10920\) değerlerini de simülasyonla kontrol eder.
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1)$$
olsun. Kapalı formu yerine koyup terim terim ayırırsak
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k$$
elde edilir. Yani fasulye süreci artık üç adet standart geometrik seri toplamına indirgenmiştir.
\(r\neq 1\) için klasik formül
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}$$
olduğundan
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
Dolayısıyla
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
Kodun gerçekten hesapladığı ifade tam olarak budur.
İstenen modül
$$m=7^9=40{,}353{,}607$$
olduğundan ve \(m\), ne \(2\)'ye ne de \(3\)'e bölündüğünden, bu iki sayının modüler tersi vardır. Böylece kesirli görünen terimler modüler aritmetikte şu hale gelir:
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
Geriye yalnızca \(2^{E+1}\), \(3^{E+1}\) ve \(4^{E+1}\) üslerini mod \(m\) altında bulmak kalır. Bunlar ikili üs alma ile \(O(\log E)\) çarpımda hesaplanır; bu yüzden \(E=10^{18}\) olması pratikte sorun yaratmaz.
C++ çözümü iki parçaya ayrılır. İlk parçada simulate_M ve run_validations, hem problem
metnindeki örnekleri hem de \(M(2^k+1)=2^{k+1}+4^k-3^k\) formülünü \(k=0,\dots,8\) için doğrular. İkinci parçada
solve(), \(2\) ve \(3\)'ün modüler terslerini bulur, sonra
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m$$
değerlerini hesaplar; bunlardan sum_2, sum_4 ve sum_3 terimlerini üretir ve
sonucu (sum_2 + sum_4 - sum_3) mod m olarak birleştirir. Python sürümü aynı matematiği
pow(base, exp, mod) ve yerleşik modüler ters desteğiyle yürütür. Java sürümü de aynı hızlı üs alma
mantığını kullanır; modüler ters için BigInteger.modInverse çağrılır.
Son çözüm yalnızca üç modüler üs alma ve sabit sayıda modüler işlem içerir; dolayısıyla zaman karmaşıklığı \(O(\log E)\), bellek karmaşıklığı \(O(1)\)'dir. Doğrudan fasulye simülasyonu sadece küçük sabit doğrulama örneklerinde kullanılır.
Se colocan \(n\) cuencos en un circulo, cada uno con un frijol. Desde un cuenco actual, Peter toma todos los frijoles de ese cuenco y los va dejando uno por uno en los cuencos siguientes en sentido horario. El siguiente movimiento comienza en el cuenco que recibe el ultimo frijol. Sea \(M(n)\) el numero de movimientos necesarios para que reaparezca la configuracion inicial de unos en todos los cuencos. Se pide calcular
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$$
Para \(n\) pequeno puede hacerse una simulacion directa. Para el limite \(10^{18}\), la unica estrategia viable es usar una formula cerrada para \(2^k+1\) y luego sumar esa expresion mediante series geometricas.
Numeremos los cuencos como \(0,1,\dots,n-1\), sea \(b_i\) la cantidad de frijoles del cuenco \(i\) y \(p\) la posicion actual. Si el cuenco actual contiene \(t=b_p\) frijoles, un movimiento realiza
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
El estado inicial es \((1,1,\dots,1)\). La funcion simulate_M de C++ implementa literalmente esta
regla y repite el proceso hasta que la configuracion de todos unos reaparece. Asi se obtiene la definicion directa
de \(M(n)\).
El ingrediente combinatorio central usado por la solucion es
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
El programa toma esta identidad como lema principal y la verifica por simulacion para valores pequenos de \(k\). Los primeros casos son
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
que coinciden con
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53.$$
Ademas, la implementacion comprueba por simulacion los valores del enunciado \(M(5)=15\) y \(M(100)=10920\).
Sea
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$$
Sustituyendo la formula cerrada y separando terminos, obtenemos
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$$
El problema original queda convertido en tres sumas geometricas estandar.
Para cualquier \(r\neq 1\),
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$$
Por tanto,
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
Luego
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
Esa es exactamente la expresion que evaluan los tres programas.
El modulo requerido es
$$m=7^9=40{,}353{,}607.$$
Como \(m\) no es divisible ni por \(2\) ni por \(3\), ambos tienen inverso modular. Asi, las divisiones se reemplazan por multiplicaciones:
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
Solo hace falta calcular \(2^{E+1}\), \(3^{E+1}\) y \(4^{E+1}\) modulo \(m\). Eso se hace con exponenciacion binaria en \(O(\log E)\), no en tiempo lineal.
La version en C++ separa validacion y solucion final. simulate_M y run_validations
comprueban ejemplos pequenos, incluyendo los datos del enunciado y la formula \(M(2^k+1)=2^{k+1}+4^k-3^k\) para
\(k=0,\dots,8\). Despues, solve() calcula los inversos modulares de \(2\) y \(3\), obtiene
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$$
construye sum_2, sum_4 y sum_3, y combina todo como
(sum_2 + sum_4 - sum_3) mod m. Python usa la misma matematica con
pow(base, exp, mod); Java mantiene la misma logica y usa BigInteger.modInverse para los
inversos.
La parte final requiere tres potenciaciones modulares y unas pocas operaciones adicionales, asi que cuesta \(O(\log E)\) tiempo y \(O(1)\) memoria. La simulacion directa solo aparece en una fase de verificacion de tamano fijo.
把 \(n\) 个碗排成一个圆圈，每个碗里先放 1 颗豆子。Peter 每一步都会取出当前碗中的全部豆子，然后按顺时针方向把这些豆子一颗一颗放入后续碗中。下一步从最后一颗豆子落入的碗开始。记 \(M(n)\) 为初始的全 1 配置再次出现所需的步数。题目要求计算
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$$
对小规模 \(n\) 可以直接模拟，但上界 \(10^{18}\) 使暴力法完全不可行。因此解法的核心是先对特殊输入 \(2^k+1\) 建立闭式，再把总和化成三个几何级数。
把碗编号为 \(0,1,\dots,n-1\)，设 \(b_i\) 是第 \(i\) 个碗中的豆子数，\(p\) 是当前位置。若当前碗中有 \(t=b_p\) 颗豆子，则一步操作为
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
初始状态是 \((1,1,\dots,1)\)。C++ 中的 simulate_M 逐字实现了这一定义，并不断重复，直到全
1 状态再次出现，因此它给出了 \(M(n)\) 的直接计算方式。
程序依赖的核心组合恒等式是
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
代码把它作为关键引理，并对小 \(k\) 用显式模拟验证。前几个值是
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
恰好对应
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53.$$
实现还额外验证了题面给出的 \(M(5)=15\) 与 \(M(100)=10920\)。
记
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$$
代入闭式并按项分组，可得
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$$
原问题于是完全化为三个标准几何级数。
对任意 \(r\neq 1\)，
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$$
因此
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
于是得到
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
这就是程序最终计算的精确公式。
题目要求模
$$m=7^9=40{,}353{,}607$$
计算。由于 \(m\) 与 \(2,3\) 都互素，所以 \(2\) 和 \(3\) 在模 \(m\) 下都有逆元，因此上式中的除法可写成
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
接下来只需计算 \(2^{E+1}\)、\(3^{E+1}\)、\(4^{E+1}\) 在模 \(m\) 下的值。代码通过快速幂完成这一点，所以总成本 是 \(O(\log E)\)，而不是 \(O(E)\)。
C++ 程序分成两部分。第一部分是 simulate_M 与 run_validations，用于检查题面样例和
\(M(2^k+1)=2^{k+1}+4^k-3^k\) 在 \(k=0,\dots,8\) 时的正确性。第二部分是 solve()，它先求出
\(2\) 和 \(3\) 的模逆，再计算
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$$
然后构造 sum_2、sum_4、sum_3 并返回
(sum_2 + sum_4 - sum_3) mod m。Python 版本使用同样的数学公式和
pow(base, exp, mod)；Java 版本也采用同样的快速幂逻辑，并通过
BigInteger.modInverse 求逆元。
最终求值只包含三次模幂和常数次模运算，因此时间复杂度是 \(O(\log E)\)，空间复杂度是 \(O(1)\)。直接模拟只在 固定规模的小型校验阶段出现。
Есть \(n\) чаш, расположенных по кругу, и в каждой изначально лежит по одной фасолине. На каждом ходе Peter забирает все фасолины из текущей чаши и раскладывает их по одной в следующие чаши по часовой стрелке. Следующий ход начинается из чаши, в которую упала последняя фасолина. Обозначим через \(M(n)\) число ходов до повторного появления исходной конфигурации из одних единиц. Требуется найти
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$$
Для малых \(n\) процесс можно моделировать напрямую, но при верхней границе \(10^{18}\) это невозможно. Поэтому решение использует замкнутую формулу для значений вида \(2^k+1\), а затем суммирует ее как три геометрические прогрессии.
Нумеруем чаши как \(0,1,\dots,n-1\), пусть \(b_i\) — число фасолин в чаше \(i\), а \(p\) — текущая позиция. Если в текущей чаше находится \(t=b_p\) фасолин, один ход имеет вид
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
Начальное состояние равно \((1,1,\dots,1)\). Функция simulate_M в C++ буквально реализует это правило
и повторяет его до тех пор, пока конфигурация из одних единиц не появится снова. Тем самым она напрямую вычисляет
\(M(n)\).
Главный нетривиальный комбинаторный факт, на котором построено решение, таков:
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
Код использует эту формулу как основную лемму и проверяет ее на малых \(k\) с помощью явной симуляции. Первые значения:
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
и они совпадают с
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53.$$
Дополнительно программа сверяет приведенные в условии значения \(M(5)=15\) и \(M(100)=10920\).
Положим
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$$
Подставляя замкнутую формулу и разбивая сумму по слагаемым, получаем
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$$
Исходная задача о процессе полностью сводится к трем стандартным геометрическим прогрессиям.
Для любого \(r\neq 1\) верно
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$$
Следовательно,
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
Поэтому
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
Именно эту формулу вычисляет программа при \(E=10^{18}\).
Требуемый модуль равен
$$m=7^9=40{,}353{,}607.$$
Так как \(m\) взаимно прост с \(2\) и \(3\), обе величины имеют обратные элементы по модулю \(m\). Поэтому деления в формуле переписываются как умножения:
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
Остается найти \(2^{E+1}\), \(3^{E+1}\) и \(4^{E+1}\) по модулю \(m\). Это делается бинарным возведением в степень, то есть за \(O(\log E)\), а не за линейное время.
В C++-версии есть две части. simulate_M и run_validations проверяют малые тесты, включая
значения из условия и формулу \(M(2^k+1)=2^{k+1}+4^k-3^k\) для \(k=0,\dots,8\). Затем функция solve()
находит обратные элементы к \(2\) и \(3\), вычисляет
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$$
формирует величины sum_2, sum_4, sum_3 и возвращает
(sum_2 + sum_4 - sum_3) mod m. В Python используется та же математика через
pow(base, exp, mod); в Java — тот же алгоритм быстрого возведения в степень и
BigInteger.modInverse для обратных элементов.
Финальное вычисление состоит из трех модульных степеней и константного числа остальных операций, так что его сложность равна \(O(\log E)\) по времени и \(O(1)\) по памяти. Прямая симуляция используется только в небольшой фазе проверки.
لدينا \(n\) أوعية مرتبة على دائرة، وفي كل وعاء حبة واحدة في البداية. في كل حركة يأخذ Peter كل الحبوب من الوعاء الحالي ثم يوزعها واحدة واحدة على الأوعية التالية باتجاه عقارب الساعة. تبدأ الحركة التالية من الوعاء الذي استقبل آخر حبة. نرمز بـ \(M(n)\) إلى عدد الحركات اللازمة حتى تعود البنية الابتدائية التي تحتوي على حبة واحدة في كل وعاء. المطلوب هو حساب
$$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$$
المحاكاة المباشرة ممكنة عندما يكون \(n\) صغيرًا، لكن الحد \(10^{18}\) يجعل القوة الغاشمة مستحيلة. لذلك تعتمد الخوارزمية على صيغة مغلقة للقيم الخاصة \(2^k+1\)، ثم تجمعها على شكل ثلاث متتاليات هندسية.
لنرقم الأوعية بـ \(0,1,\dots,n-1\)، ولتكن \(b_i\) عدد الحبوب في الوعاء \(i\)، و\(p\) هو الموضع الحالي. إذا كان الوعاء الحالي يحتوي على \(t=b_p\) حبة، فإن حركة واحدة تحقق
$$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$$
الحالة الابتدائية هي \((1,1,\dots,1)\). الدالة simulate_M في C++ تطبق هذه القاعدة حرفيًا، وتكررها
حتى تعود حالة الواحدات من جديد، ولذلك فهي تمثل التعريف المباشر لـ \(M(n)\).
الحقيقة التوافقية الأساسية التي يبني عليها الحل هي
$$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$$
يتعامل الكود مع هذه العلاقة على أنها اللمّة الرئيسية، ثم يتحقق منها بالمحاكاة عند قيم صغيرة من \(k\). القيم الأولى هي
$$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$$
وهي تطابق
$$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53.$$
كما أن التنفيذ يتحقق أيضًا من القيم المذكورة في نص المسألة: \(M(5)=15\) و\(M(100)=10920\).
لنضع
$$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$$
بالتعويض عن الصيغة المغلقة ثم فصل الحدود نحصل على
$$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$$
وهكذا تتحول المسألة الأصلية كلها إلى ثلاث سلاسل هندسية قياسية.
إذا كان \(r\neq 1\)، فإن
$$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$$
وبالتالي
$$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$$
$$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$$
إذن
$$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$$
وهذه هي الصيغة الدقيقة التي يحسبها البرنامج عند \(E=10^{18}\).
المودولو المطلوب هو
$$m=7^9=40{,}353{,}607.$$
وبما أن \(m\) غير قابل للقسمة على \(2\) ولا على \(3\)، فلكل من \(2\) و\(3\) معكوس ضربي modulo \(m\). لذلك يمكن كتابة الحدود الكسرية بالشكل
$$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$$
المطلوب الآن هو فقط حساب \(2^{E+1}\) و\(3^{E+1}\) و\(4^{E+1}\) modulo \(m\). ويتم ذلك بواسطة الأس السريع، لذا تكون الكلفة \(O(\log E)\) بدلًا من \(O(E)\).
ملف C++ مقسوم إلى مرحلتين. أولًا، تتحقق simulate_M وrun_validations من الحالات الصغيرة،
بما في ذلك قيم المسألة والصيغة \(M(2^k+1)=2^{k+1}+4^k-3^k\) عندما \(k=0,\dots,8\). ثم تأتي الدالة
solve() لتحسب معكوسي \(2\) و\(3\)، وبعد ذلك تحسب
$$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$$
وتبني منها القيم sum_2 وsum_4 وsum_3، ثم تعيد
(sum_2 + sum_4 - sum_3) mod m. نسخة Python تستخدم الرياضيات نفسها مع
pow(base, exp, mod). أما Java فتستخدم المنطق نفسه للأس السريع وتستخرج المعكوسات عبر
BigInteger.modInverse.
الحساب النهائي يحتاج فقط إلى ثلاث عمليات أس معيارية وعدد ثابت من العمليات الأخرى، ولذلك يكون زمن التنفيذ \(O(\log E)\) والذاكرة \(O(1)\). أما المحاكاة المباشرة فلا تظهر إلا في مرحلة تحقق صغيرة وثابتة الحجم.