Alice and \(n\) friends toss the same biased coin in a fixed cyclic order, with Alice always taking the first turn in each round. The game ends immediately when Alice gets her first Head. If the friends have accumulated head counts \(H_1,\dots,H_n\) by that moment, then
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
For fixed \(n\), this expectation turns out to be a polynomial in \(p\). Writing the coefficient of \(p^k\) as \(c(n,k)\), the target is
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}.$$
The key is to replace the stochastic process by a stopping-time variable and then identify the resulting polynomial with an Eulerian polynomial.
Let \(R\) be the number of Tails Alice sees before her first Head. Then \(R\) follows a geometric distribution:
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
If \(R=r\), then Alice has produced exactly \(r\) complete rounds before the final stopping toss. Therefore each friend has tossed exactly \(r\) times when the game ends.
Conditional on \(R=r\), the \(i\)-th friend records a head count
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p).$$
Hence
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
Once \(r\) is fixed, different friends depend on disjoint tosses and are conditionally independent, so the expected product factors:
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
Applying the law of total expectation gives
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right].$$
Substituting the previous formulas yields
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r.$$
The term \(r=0\) is harmless because \(n\ge 1\), but the expression still looks like an infinite power series. The next step shows that it actually collapses to a finite polynomial.
For every \(n\ge 1\), the power-sum generating function satisfies
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
where \(A_n(x)\) is the \(n\)-th Eulerian polynomial:
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
Substituting \(x=p\) into the series above gives
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p).$$
This is the decisive simplification: the apparent infinite series is exactly the degree-\(n\) polynomial \(pA_n(p)\).
Expanding \(pA_n(p)\) gives
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}.$$
Therefore the coefficient of \(p^k\) is
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
and \(c(n,k)=0\) outside that range. So the original probability question reduces to computing one Eulerian number.
The implementations evaluate the Eulerian number through the alternating sum
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
with \(m=k-1\). This formula is ideal for modular arithmetic because each term is a product of one binomial coefficient and one modular power.
For \(n=3\), the Eulerian polynomial is
$$A_3(x)=1+4x+x^2.$$
Hence
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
So the nonzero coefficients are
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1.$$
The same value \(c(3,2)=4\) also comes directly from the explicit sum with \(m=1\):
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
This matches the small verification built into the implementation.
The C++, Python, and Java implementations do not expand the whole polynomial. They compute only the single Eulerian number corresponding to \(m=k-1\). First they prepare modular inverses of \(1,2,\dots,m+1\), which is possible because the modulus \(10^9+7\) is prime.
Next they sweep once through \(j=0,1,\dots,m+1\). During that pass, the current binomial coefficient \(\binom{n+1}{j}\) is updated from the previous one by the standard ratio for consecutive binomial terms, so no huge factorial tables are needed. In the same loop, the power \((m+1-j)^n\) is computed by fast modular exponentiation, multiplied by the current binomial factor, and added or subtracted according to the sign \((-1)^j\).
This strategy is exactly what the mathematics suggests: evaluate the alternating formula for one Eulerian number modulo \(10^9+7\), and stop. That keeps the method practical even when \(n=10^7\).
To compute one coefficient \(c(n,k)\), the alternating sum has \(k+1\) terms because \(m=k-1\). Preparing the modular inverses costs \(O(k)\) time and \(O(k)\) memory. Each summand also needs one modular exponentiation, which costs \(O(\log n)\). Therefore the total running time is
$$O(k\log n),$$
with
$$O(k)$$
memory usage.
Alice und \(n\) Freunde werfen dieselbe verzerrte Münze in fester zyklischer Reihenfolge, wobei Alice jede Runde beginnt. Das Spiel endet sofort, sobald Alice ihr erstes Head wirft. Haben die Freunde bis dahin die Kopfzahlen \(H_1,\dots,H_n\) erreicht, so ist
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
Für festes \(n\) ist dieser Erwartungswert ein Polynom in \(p\). Bezeichnet \(c(n,k)\) den Koeffizienten von \(p^k\), so soll berechnet werden
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}.$$
Die entscheidende Umformung besteht darin, die Zufallsvariable für Alices Stoppzeit einzuführen und den entstehenden Ausdruck mit einem Euler-Polynom zu identifizieren.
Sei \(R\) die Anzahl der Tails, die Alice vor ihrem ersten Head sieht. Dann gilt die geometrische Verteilung
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
Wenn \(R=r\) eintritt, wurden genau \(r\) vollständige Freundesrunden gespielt, bevor Alice im nächsten eigenen Wurf stoppt. Also hat jeder Freund genau \(r\) Würfe ausgeführt.
Bedingt auf \(R=r\) besitzt der \(i\)-te Freund die Kopfzahl
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p).$$
Daraus folgt
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
Nach Fixierung von \(r\) beruhen die Freunde auf disjunkten Würfen und sind damit bedingt unabhängig. Deshalb faktorisiert das Produkt:
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
Mit dem Gesetz der totalen Erwartung erhält man
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right].$$
Einsetzen liefert
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r.$$
Da \(n\ge 1\) ist, stört der Term \(r=0\) nicht. Trotzdem sieht der Ausdruck zunächst wie eine unendliche Reihe aus. Der nächste Schritt zeigt, warum tatsächlich nur ein Polynom übrig bleibt.
Für jedes \(n\ge 1\) gilt die erzeugende Funktion
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
wobei \(A_n(x)\) das \(n\)-te Euler-Polynom ist:
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
Setzt man \(x=p\), so folgt
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p).$$
Damit verschwindet die scheinbar unendliche Reihe exakt, und \(e(n,p)\) ist ein Polynom vom Grad \(n\).
Aus der Entwicklung
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}$$
liest man sofort ab:
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
und außerhalb dieses Bereichs ist der Koeffizient \(0\). Das Wahrscheinlichkeitsproblem reduziert sich also auf genau eine Euler-Zahl.
Die Implementierungen verwenden dafür die alternierende Darstellung
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
wobei \(m=k-1\) gesetzt wird. Diese Form ist modular besonders bequem, weil jedes Summenglied nur aus einem Binomialkoeffizienten und einer Potenz besteht.
Für \(n=3\) lautet das Euler-Polynom
$$A_3(x)=1+4x+x^2.$$
Daher ist
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
Die nichtverschwindenden Koeffizienten sind also
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1.$$
Der Wert \(c(3,2)=4\) folgt auch direkt aus der expliziten Summe mit \(m=1\):
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
Genau dieser kleine Test wird auch von der Implementierung bestätigt.
Die C++-, Python- und Java-Implementierungen expandieren nicht das ganze Polynom, sondern berechnen nur die eine Euler-Zahl zu \(m=k-1\). Zuerst werden modulare Inversen für \(1,2,\dots,m+1\) vorbereitet; das ist möglich, weil \(10^9+7\) eine Primzahl ist.
Danach durchläuft der Code einmal die Werte \(j=0,1,\dots,m+1\). Dabei wird der aktuelle Binomialkoeffizient \(\binom{n+1}{j}\) aus dem vorherigen durch das Standardverhältnis aufeinanderfolgender Binomialterme fortgeschrieben, sodass keine riesigen Fakultätstabellen nötig sind. Im selben Durchlauf wird die Potenz \((m+1-j)^n\) per schneller modularer Exponentiation berechnet, mit dem aktuellen Binomialfaktor multipliziert und je nach Parität von \(j\) addiert oder subtrahiert.
Das Verfahren setzt die Mathematik also direkt um: eine einzige alternierende Formel für eine einzige Euler-Zahl modulo \(10^9+7\). Genau deshalb bleibt die Lösung auch für \(n=10^7\) praktikabel.
Für einen Koeffizienten \(c(n,k)\) besitzt die alternierende Summe \(k+1\) Terme, weil \(m=k-1\) gilt. Die Vorbereitung der modularen Inversen kostet \(O(k)\) Zeit und \(O(k)\) Speicher. Jedes Summenglied benötigt außerdem eine modulare Potenzierung in \(O(\log n)\). Insgesamt ergibt sich daher
$$O(k\log n)$$
Zeit bei
$$O(k)$$
Speicherverbrauch.
Alice ve \(n\) arkadaşı aynı hileli parayı sabit döngüsel sırayla atar; her turu Alice başlatır. Oyun, Alice ilk kez Head geldiği anda hemen biter. O ana kadar arkadaşların gördüğü head sayıları \(H_1,\dots,H_n\) ise
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
Sabit \(n\) için bu beklenen değer \(p\)'de bir polinomdur. \(p^k\)'nin katsayısını \(c(n,k)\) ile gösterirsek hedef
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}$$
değerini bulmaktır.
Çözümün özü, süreci Alice'in durma zamanı üzerinden yeniden yazmak ve oluşan seriyi Eulerian polinomu ile özdeşleştirmektir.
\(R\), Alice ilk Head gelmeden önce kaç kez Tail gördüğünü göstersin. O zaman
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
\(R=r\) olduğunda, Alice son durdurucu atışından önce tam \(r\) eksiksiz tur tamamlamıştır. Bu nedenle her arkadaş oyunun sonunda tam \(r\) kez para atmıştır.
\(R=r\) koşulu altında \(i\). arkadaşın head sayısı
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p)$$
dağılımına uyar. Dolayısıyla
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
\(r\) sabitlendiğinde arkadaşların atışları birbirinden ayrıdır; yani koşullu bağımsızlık vardır. Bu yüzden çarpımın beklenen değeri çarpanlara ayrılır:
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
Toplam beklenti yasasıyla
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]$$
yazılır. Önceki ifadeleri yerine koyunca
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r$$
elde edilir. \(n\ge 1\) olduğu için \(r=0\) terimi sorun çıkarmaz; yine de ifade ilk bakışta sonsuz seri gibi görünür. Bir sonraki adım bunun aslında sonlu bir polinom olduğunu gösterir.
Her \(n\ge 1\) için şu üreteç fonksiyon geçerlidir:
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
burada \(A_n(x)\), \(n\). Eulerian polinomudur:
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
\(x=p\) yazınca
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p)$$
olur. Böylece görünürdeki sonsuz seri tam olarak derece \(n\) olan bir polinoma dönüşür.
\(pA_n(p)\)'yi açarsak
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}$$
elde ederiz. O halde
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
ve bu aralığın dışında katsayı \(0\)'dır. Yani özgün olasılık problemi tek bir Eulerian sayının hesabına indirgenir.
Uygulamalar Eulerian sayıyı şu alternanslı toplamla hesaplar:
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
burada \(m=k-1\) seçilir. Bu form modüler aritmetik için uygundur; çünkü her terim bir binom katsayısı ile bir üs ifadesinin çarpımıdır.
\(n=3\) için Eulerian polinomu
$$A_3(x)=1+4x+x^2$$
olur. Dolayısıyla
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
Buradan sıfır olmayan katsayılar
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1$$
şeklindedir. Aynı \(c(3,2)=4\) değeri, \(m=1\) için açık toplamdan da çıkar:
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
Bu, uygulamadaki küçük doğrulama ile birebir örtüşür.
C++, Python ve Java implementasyonları tüm polinomu açmaz; yalnızca \(m=k-1\) için gereken Eulerian sayıyı hesaplar. İlk adımda \(1,2,\dots,m+1\) sayılarının modüler tersleri hazırlanır; bunun yapılabilmesi, modülün asal olan \(10^9+7\) olması sayesindedir.
Ardından \(j=0,1,\dots,m+1\) üzerinde tek geçiş yapılır. Bu geçiş sırasında mevcut binom katsayısı \(\binom{n+1}{j}\), art arda gelen binom terimleri arasındaki oran kullanılarak bir önceki değerden türetilir; böylece devasa faktöriyel tablolarına ihtiyaç kalmaz. Aynı döngüde \((m+1-j)^n\) değeri hızlı modüler üs alma ile bulunur, güncel binom katsayısı ile çarpılır ve \((-1)^j\) işaretine göre toplama eklenir ya da çıkarılır.
Yani kod, matematikte elde edilen alternanslı formülü doğrudan uygular ve sadece tek bir Eulerian sayıyı mod \(10^9+7\) altında hesaplar. Bu yüzden \(n=10^7\) gibi büyük değerlerde bile yöntem uygulanabilir kalır.
Bir \(c(n,k)\) katsayısı için alternanslı toplamda \(k+1\) terim vardır; çünkü \(m=k-1\) olur. Modüler terslerin hazırlanması \(O(k)\) zaman ve \(O(k)\) bellek ister. Her toplam terimi için ayrıca \(O(\log n)\) maliyetli bir modüler üs alma yapılır. Sonuç olarak toplam süre
$$O(k\log n)$$
ve bellek kullanımı
$$O(k)$$
olur.
Alice y \(n\) amigos lanzan la misma moneda sesgada en un orden cíclico fijo, comenzando siempre por Alice en cada vuelta. El proceso termina en el instante exacto en que Alice obtiene su primera cara. Si en ese momento los amigos han acumulado cuentas de caras \(H_1,\dots,H_n\), definimos
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
Para un \(n\) fijo, esta esperanza es un polinomio en \(p\). Si \(c(n,k)\) es el coeficiente de \(p^k\), el objetivo es calcular
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}.$$
La idea central es sustituir todo el proceso aleatorio por la variable que mide cuándo se detiene Alice, y después reconocer la serie resultante como un polinomio euleriano.
Sea \(R\) el número de colas que obtiene Alice antes de su primera cara. Entonces
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
Si \(R=r\), eso significa que antes del lanzamiento final de Alice se completaron exactamente \(r\) rondas enteras de amigos. Por lo tanto, cada amigo lanzó la moneda exactamente \(r\) veces.
Condicionado a \(R=r\), la cuenta de caras del amigo \(i\) satisface
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p).$$
En consecuencia,
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
Una vez fijado \(r\), los amigos dependen de lanzamientos distintos y son condicionalmente independientes. Así, la esperanza del producto se factoriza:
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
Aplicando la ley de la esperanza total, obtenemos
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right].$$
Sustituyendo las expresiones anteriores, resulta
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r.$$
Como \(n\ge 1\), el término \(r=0\) no da problemas. Aun así, la fórmula parece una serie infinita; el paso siguiente explica por qué en realidad se convierte en un polinomio finito.
Para todo \(n\ge 1\), la función generadora de las potencias cumple
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
donde \(A_n(x)\) es el \(n\)-ésimo polinomio euleriano:
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
Al sustituir \(x=p\), se obtiene
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p).$$
La cancelación es exacta. Por eso la serie aparentemente infinita se reduce al polinomio de grado \(n\) dado por \(pA_n(p)\).
Al expandir \(pA_n(p)\), aparece
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}.$$
Así, el coeficiente buscado es
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
y fuera de ese intervalo vale \(0\). En otras palabras, todo el problema probabilístico queda reducido a un único número euleriano.
Las implementaciones evalúan ese número mediante la suma alternante
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
con \(m=k-1\). Esta forma es especialmente adecuada para el cálculo modular porque cada término es el producto de un coeficiente binomial y una potencia.
Cuando \(n=3\), el polinomio euleriano es
$$A_3(x)=1+4x+x^2.$$
Por tanto,
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
Los coeficientes no nulos son
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1.$$
El mismo valor \(c(3,2)=4\) sale directamente de la fórmula explícita con \(m=1\):
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
Esto coincide con la comprobación pequeña incluida en la implementación.
Las implementaciones en C++, Python y Java no construyen el polinomio completo. Calculan solo el número euleriano asociado a \(m=k-1\). Primero preparan los inversos modulares de \(1,2,\dots,m+1\), algo posible porque el módulo \(10^9+7\) es primo.
Después recorren una sola vez los valores \(j=0,1,\dots,m+1\). En ese recorrido, el coeficiente binomial actual \(\binom{n+1}{j}\) se actualiza a partir del anterior usando la razón estándar entre términos binomiales consecutivos, con lo que se evita almacenar tablas gigantes de factoriales. Dentro del mismo bucle, se calcula \((m+1-j)^n\) mediante exponenciación modular rápida, se multiplica por el coeficiente binomial vigente y se suma o resta según el signo \((-1)^j\).
La estrategia sigue exactamente la derivación matemática: evaluar una sola suma alternante para un solo número euleriano módulo \(10^9+7\). Eso es lo que hace viable el caso extremo \(n=10^7\).
Para calcular un único coeficiente \(c(n,k)\), la suma alternante tiene \(k+1\) términos porque \(m=k-1\). Preparar los inversos modulares cuesta \(O(k)\) tiempo y \(O(k)\) memoria. Además, cada término requiere una exponenciación modular en \(O(\log n)\). En conjunto, el tiempo total es
$$O(k\log n),$$
con uso de memoria
$$O(k).$$
Alice 和 \(n\) 位朋友按固定循环顺序掷同一枚有偏硬币，而且每一轮都由 Alice 先掷。游戏在 Alice 第一次出现 Head 的瞬间立刻停止。若停止时朋友们各自得到的 Head 次数为 \(H_1,\dots,H_n\)，则定义
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
对固定的 \(n\) 来说，这个期望值实际上是关于 \(p\) 的一个多项式。记 \(p^k\) 的系数为 \(c(n,k)\)，题目要求计算
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}.$$
这道题的关键不在于直接处理整个随机过程，而在于引入一个“停止时间”变量，把期望改写成一个标准幂级数，然后再用 Eulerian 多项式恒等式把它压缩成有限多项式。
设 \(R\) 表示 Alice 在第一次出现 Head 之前看到的 Tail 次数。那么 \(R\) 服从几何分布：
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
这个定义还有一个非常重要的结构含义：如果 \(R=r\)，那么在 Alice 最终停下之前，已经完整进行了 \(r\) 轮朋友投掷。因此每一位朋友在游戏结束前都恰好掷了 \(r\) 次硬币。
一旦把 \(R=r\) 固定下来，第 \(i\) 位朋友的 Head 次数就是 \(r\) 次独立投掷中的成功次数，所以
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p).$$
于是它的条件期望为
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
更重要的是，在 \(r\) 固定之后，不同朋友依赖的是互不重叠的投掷结果，因此它们条件独立。于是乘积的条件期望可以直接分解：
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
由全期望公式可得
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right].$$
把上面的结果代入后，得到
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r.$$
由于 \(n\ge 1\)，所以 \(r=0\) 这一项不会造成麻烦。但从形式上看，这仍然像是一个无限级数。题目真正精彩的地方就在于：这个级数并不需要逐项展开，它可以被完全化简成一个有限多项式。
对于任意 \(n\ge 1\)，有如下经典恒等式：
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
其中 \(A_n(x)\) 是第 \(n\) 个 Eulerian 多项式：
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
把 \(x\) 替换成 \(p\)，前一步的式子立即化为
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p).$$
这一步完成了最重要的化简：原本看起来是无限和的表达式，实际上恰好等于次数为 \(n\) 的多项式 \(pA_n(p)\)。
将 \(pA_n(p)\) 展开，可得
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}.$$
因此 \(p^k\) 的系数就是
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
超出这个范围时系数为 \(0\)。也就是说，这道概率题最终被完全等价地改写成“求一个 Eulerian 数”的问题。
实际计算时，程序使用的是 Eulerian 数的交错求和公式：
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
其中 \(m=k-1\)。这个公式非常适合做模运算，因为每一项都只是“一个二项式系数”乘上“一个模幂”。
当 \(n=3\) 时，Eulerian 多项式为
$$A_3(x)=1+4x+x^2.$$
于是
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
所以非零系数恰好是
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1.$$
若直接代入显式公式并取 \(m=1\)，也能算出同样的结果：
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
这和实现中用来校验的小样例完全一致。
C++、Python 和 Java 的实现都没有去构造完整的多项式，更不会去生成整张 Eulerian 数三角形表。它们只计算最终需要的那一个值，也就是 \(m=k-1\) 对应的 Eulerian 数。首先，程序会预处理 \(1,2,\dots,m+1\) 在模 \(10^9+7\) 下的乘法逆元；之所以能这样做，是因为模数本身是质数。
接下来，程序对 \(j=0,1,\dots,m+1\) 做一次线性扫描。在这次扫描中，当前的二项式系数 \(\binom{n+1}{j}\) 不是通过阶乘表得到，而是利用相邻二项式系数之间的乘法递推关系从前一项更新出来。这样就避免了为 \(n=10^7\) 级别的数据建立庞大的预处理结构。
在同一轮循环里，程序还会计算 \((m+1-j)^n\) 的模幂值，将它与当前二项式系数相乘，然后按照 \((-1)^j\) 的符号决定加到答案中还是减掉。整段实现本质上就是把上面的交错公式逐项在模 \(10^9+7\) 下求值，因此结构非常直接，也与数学推导完全一致。
求单个系数 \(c(n,k)\) 时，交错求和共有 \(k+1\) 项，因为 \(m=k-1\)。预处理逆元需要 \(O(k)\) 时间和 \(O(k)\) 空间。每一项还需要一次快速模幂，代价是 \(O(\log n)\)。因此总时间复杂度为
$$O(k\log n),$$
空间复杂度为
$$O(k).$$
Alice и \(n\) друзей подбрасывают одну и ту же смещенную монету в фиксированном циклическом порядке, причем каждую новую серию бросков начинает Alice. Игра завершается немедленно, когда у Alice впервые выпадает Head. Если к этому моменту друзья набрали числа орлов \(H_1,\dots,H_n\), то
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
При фиксированном \(n\) это математическое ожидание оказывается полиномом по \(p\). Обозначая коэффициент при \(p^k\) через \(c(n,k)\), нужно найти
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}.$$
Главная идея состоит в том, чтобы свести весь случайный процесс к одной случайной величине, отвечающей за момент остановки Alice, а затем распознать полученную производящую функцию как Eulerian-полином.
Пусть \(R\) обозначает число Tail у Alice до первого Head. Тогда
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
Если \(R=r\), это означает, что до финального броска Alice успели завершиться ровно \(r\) полных раундов бросков друзей. Следовательно, каждый друг к моменту остановки бросил монету ровно \(r\) раз.
При условии \(R=r\) число орлов у \(i\)-го друга имеет распределение
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p).$$
Поэтому
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
После фиксации \(r\) друзья зависят от непересекающихся наборов бросков, то есть становятся условно независимыми. Значит, ожидание произведения раскладывается:
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
По формуле полной вероятности для ожидания получаем
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right].$$
Подстановка дает
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r.$$
Так как \(n\ge 1\), член при \(r=0\) не создает проблемы. Но выражение все еще выглядит как бесконечный ряд. Следующий шаг показывает, что этот ряд сворачивается в точный конечный полином.
Для любого \(n\ge 1\) выполнено классическое равенство
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
где \(A_n(x)\) обозначает \(n\)-й Eulerian-полином:
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
Подставляя \(x=p\), получаем
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p).$$
Именно здесь происходит решающее упрощение: бесконечный степенной ряд сокращается до полинома степени \(n\).
Раскрывая \(pA_n(p)\), имеем
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}.$$
Следовательно, коэффициент при \(p^k\) равен
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
а вне этого диапазона он равен нулю. Значит, исходная вероятностная задача полностью сводится к вычислению одного Eulerian-числа.
Для вычисления используется чередующаяся сумма
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
где \(m=k-1\). Такая запись удобна для вычислений по модулю: каждое слагаемое состоит из одного биномиального коэффициента и одной степени.
При \(n=3\) Eulerian-полином имеет вид
$$A_3(x)=1+4x+x^2.$$
Поэтому
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
Отсюда сразу видны ненулевые коэффициенты:
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1.$$
То же число \(c(3,2)=4\) получается и напрямую из явной формулы при \(m=1\):
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
Это совпадает с маленькой проверкой, которую выполняет реализация.
Реализации на C++, Python и Java не строят весь полином и не пытаются вычислить целую таблицу Eulerian-чисел. Они находят только одно нужное значение, соответствующее \(m=k-1\). Сначала подготавливаются обратные элементы по модулю для чисел \(1,2,\dots,m+1\); это возможно потому, что модуль \(10^9+7\) является простым.
Затем выполняется один линейный проход по \(j=0,1,\dots,m+1\). Внутри этого прохода текущий биномиальный коэффициент \(\binom{n+1}{j}\) получается из предыдущего по стандартному мультипликативному отношению между соседними биномиальными коэффициентами. Благодаря этому не нужны громадные таблицы факториалов.
В том же цикле вычисляется \((m+1-j)^n\) с помощью быстрого возведения в степень по модулю, затем результат умножается на текущий биномиальный коэффициент и добавляется или вычитается в зависимости от знака \((-1)^j\). То есть код буквально реализует математическую формулу для одного Eulerian-числа по модулю \(10^9+7\), и именно поэтому остается эффективным даже при \(n=10^7\).
Для вычисления одного коэффициента \(c(n,k)\) чередующаяся сумма содержит \(k+1\) слагаемых, поскольку \(m=k-1\). Подготовка обратных элементов требует \(O(k)\) времени и \(O(k)\) памяти. Кроме того, каждое слагаемое требует одного быстрого возведения в степень за \(O(\log n)\). Следовательно, итоговая асимптотика равна
$$O(k\log n),$$
а потребление памяти равно
$$O(k).$$
ترمي Alice و\(n\) من الأصدقاء العملة نفسها المنحازة بترتيب دوري ثابت، وتبدأ Alice كل دورة أولًا. تتوقف اللعبة فور حصول Alice على أول Head. إذا كانت أعداد الـ Head لدى الأصدقاء عند تلك اللحظة هي \(H_1,\dots,H_n\)، فنعرّف
$$e(n,p)=\mathbb{E}\!\left[\prod_{i=1}^{n} H_i\right],\qquad p=\Pr(\text{Tail}).$$
عند تثبيت \(n\)، تكون هذه القيمة المتوقعة كثير حدود في \(p\). وإذا رمزنا لمعامل \(p^k\) بـ \(c(n,k)\)، فالمطلوب هو حساب
$$c(10^7,4\cdot 10^6)\pmod{10^9+7}.$$
الفكرة الأساسية هي اختزال العملية العشوائية كلها إلى متغير واحد يصف زمن التوقف لدى Alice، ثم تحويل المتسلسلة الناتجة إلى كثير حدود Eulerian معروف.
لتكن \(R\) عدد مرات Tail التي تراها Alice قبل أول Head. عندئذ
$$\Pr(R=r)=p^r(1-p),\qquad r\ge 0.$$
إذا تحقق \(R=r\)، فهذا يعني أن \(r\) دورات كاملة من رميات الأصدقاء قد اكتملت قبل الرمية الأخيرة التي أوقفت اللعبة. لذلك يكون كل صديق قد رمى العملة بالضبط \(r\) مرات.
عند الشرط \(R=r\)، يكون عدد مرات Head لدى الصديق رقم \(i\) موزعًا وفق
$$H_i\mid R=r \sim \operatorname{Binomial}(r,1-p).$$
ومن ثم
$$\mathbb{E}[H_i\mid R=r]=r(1-p).$$
وبما أن \(r\) أصبح ثابتًا، فإن رميات الأصدقاء تعتمد على تجارب منفصلة، أي يوجد استقلال شرطي. لذلك يتفكك متوسط حاصل الضرب إلى حاصل ضرب المتوسطات:
$$\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right]=\prod_{i=1}^{n}\mathbb{E}[H_i\mid R=r]=\bigl(r(1-p)\bigr)^n.$$
باستخدام قانون التوقع الكلي نحصل على
$$e(n,p)=\sum_{r=0}^{\infty}\Pr(R=r)\,\mathbb{E}\!\left[\prod_{i=1}^{n} H_i \,\middle|\, R=r\right].$$
وبالتعويض ينتج
$$e(n,p)=\sum_{r=0}^{\infty} p^r(1-p)\bigl(r(1-p)\bigr)^n=(1-p)^{n+1}\sum_{r=0}^{\infty} r^n p^r.$$
وبما أن \(n\ge 1\)، فلا توجد مشكلة في الحد \(r=0\). لكن الصيغة ما تزال تبدو كسلسلة لا نهائية. الخطوة التالية تبيّن أن هذه السلسلة تختزل بدقة إلى كثير حدود منتهٍ.
لكل \(n\ge 1\) توجد الهوية الكلاسيكية
$$\sum_{r=0}^{\infty} r^n x^r=\frac{xA_n(x)}{(1-x)^{n+1}},$$
حيث إن \(A_n(x)\) هو كثير الحدود Eulerian من الرتبة \(n\):
$$A_n(x)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle x^m.$$
وعند وضع \(x=p\) نحصل على
$$e(n,p)=(1-p)^{n+1}\cdot \frac{pA_n(p)}{(1-p)^{n+1}}=pA_n(p).$$
هذه هي القفزة الأساسية في الحل: ما بدا سلسلة لا نهائية يتحول تمامًا إلى كثير حدود درجته \(n\).
بتوسيع \(pA_n(p)\) نجد
$$pA_n(p)=\sum_{m=0}^{n-1}\left\langle {n \atop m} \right\rangle p^{m+1}.$$
إذن معامل \(p^k\) هو
$$c(n,k)=\left\langle {n \atop k-1} \right\rangle,\qquad 1\le k\le n,$$
ويكون صفرًا خارج هذا المجال. وهكذا تنقلب المسألة الاحتمالية الأصلية إلى حساب عدد Eulerian واحد فقط.
تحسب التطبيقات هذا العدد بواسطة المجموع المتناوب
$$\left\langle {n \atop m} \right\rangle=\sum_{j=0}^{m+1}(-1)^j\binom{n+1}{j}(m+1-j)^n,$$
مع اختيار \(m=k-1\). هذه الصيغة مناسبة جدًا للعمل بترديد أولي، لأن كل حد فيها هو حاصل ضرب معامل ثنائي في قوة واحدة.
عندما \(n=3\)، يكون كثير الحدود Eulerian هو
$$A_3(x)=1+4x+x^2.$$
إذًا
$$e(3,p)=pA_3(p)=p+4p^2+p^3.$$
ومن ثم المعاملات غير الصفرية هي
$$c(3,1)=1,\qquad c(3,2)=4,\qquad c(3,3)=1.$$
ويمكن الحصول على القيمة نفسها \(c(3,2)=4\) مباشرة من الصيغة الصريحة عند \(m=1\):
$$\left\langle {3 \atop 1} \right\rangle=\binom{4}{0}2^3-\binom{4}{1}1^3+\binom{4}{2}0^3=8-4+0=4.$$
وهذا يطابق الاختبار الصغير الموجود داخل التنفيذ.
تنفيذات C++ وPython وJava لا تبني كثير الحدود كاملًا، ولا تبني جدولًا كاملًا لأعداد Eulerian. إنها تحسب فقط القيمة اللازمة المقابلة لـ \(m=k-1\). أولًا تُحضَّر المقلوبات الضربية للأعداد \(1,2,\dots,m+1\) بترديد \(10^9+7\)، وهذا ممكن لأن الترديد عدد أولي.
بعد ذلك تُجرى دورة واحدة على \(j=0,1,\dots,m+1\). أثناء هذه الدورة يُحدَّث المعامل الثنائي الحالي \(\binom{n+1}{j}\) انطلاقًا من السابق باستخدام النسبة القياسية بين معاملين ثنائيين متتاليين، لذلك لا توجد حاجة إلى جداول ضخمة للقيم العامليّة. وفي الحلقة نفسها تُحسب القوة \((m+1-j)^n\) بالأسّ السريع المعياري، ثم تُضرب في المعامل الثنائي الحالي، وبعد ذلك تُضاف أو تُطرح بحسب إشارة \((-1)^j\).
بعبارة أخرى، الشيفرة تطبق الصيغة الرياضية المتناوبة مباشرة تحت الترديد \(10^9+7\)، وتكتفي بحساب عدد Eulerian واحد فقط. وهذا بالضبط ما يجعل المنهج عمليًا حتى عند \(n=10^7\).
لحساب معامل واحد \(c(n,k)\)، يحتوي المجموع المتناوب على \(k+1\) حدًا لأن \(m=k-1\). تجهيز المقلوبات يحتاج إلى زمن \(O(k)\) وذاكرة \(O(k)\). وكل حد يتطلب أيضًا عملية أسّ معياري سريع بكلفة \(O(\log n)\). لذلك يكون التعقيد الزمني الكلي
$$O(k\log n),$$
أما التعقيد الحجمي فهو
$$O(k).$$