Let \([n]=\{1,\dots,n\}\). We choose a non-empty family \(\mathcal{F}\) of non-empty subsets of \([n]\). Its intersection graph has one vertex for each chosen subset, and two vertices are adjacent exactly when the corresponding subsets intersect. We must compute \(C(n,K)\), the number of such families whose intersection graph has exactly \(K\) connected components. The target input is \(n=10000\) and \(K=10\), so direct enumeration is completely infeasible.
The implementations solve the problem by first counting all families on a fixed label set, then extracting the connected ones with exponential generating functions.
On a ground set of size \(r\), there are \(2^r-1\) non-empty subsets. Any non-empty selection of those subsets is a valid family, so the raw count is
$$R_r=2^{2^r-1}-1.$$
Even before connectivity is considered, this quantity grows doubly exponentially, which explains why brute force is hopeless for the real parameters.
Let \(U_n\) be the number of families whose union is exactly \([n]\). Inclusion-exclusion removes families that miss at least one label. If we restrict attention to a chosen set of \(r\) labels, then every selected subset must lie inside that \(r\)-set, so there are \(R_r\) possibilities. Therefore
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
For the generating-function step we normalize by factorials:
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
The special value \(a_0=1\) represents the empty assembly of connected components; it is a standard bookkeeping convention for the exponential formula.
Consider a family whose union is all of \([n]\). If two graph components shared a label \(t\), then some chosen subset in the first component and some chosen subset in the second would both contain \(t\). Those two subsets would intersect, producing an edge between the components, which is impossible. Hence different connected components use disjoint blocks of labels.
Conversely, if we partition \([n]\) into disjoint non-empty blocks and place one connected family on each block, then the resulting intersection graph has exactly those blocks as its connected components. So families that use every label are exactly sets of connected families on disjoint labeled blocks.
Define
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
where \(h_n\) is the number of connected families using all \(n\) labels, divided by \(n!\). The exponential formula gives
$$A(x)=\exp(H(x)).$$
Differentiating \(A(x)=\exp(H(x))\) gives
$$A'(x)=H'(x)A(x).$$
Matching the coefficient of \(x^{m-1}\) yields
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}.$$
Because \(a_0=1\), this becomes the recurrence
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}.$$
Thus the connected counts can be recovered one size at a time after the all-label counts are known.
The original problem does not force every label to appear in a chosen subset. An unused label contributes no graph vertex and can be chosen independently, which gives the labeled factor
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}.$$
A set of exactly \(K\) connected components contributes
$$\frac{H(x)^K}{K!}.$$
Therefore the required count is
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
This is the coefficient formula evaluated by the implementations.
We have \(R_0=0\), \(R_1=1\), and \(R_2=2^3-1=7\). Hence
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
so
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
The recurrence gives
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2.$$
Thus
$$H(x)=x+2x^2+O(x^3).$$
For one connected component,
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6.$$
For two connected components,
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1.$$
This matches direct inspection: among the seven non-empty families on \(\{1,2\}\), only the family containing \(\{1\}\) and \(\{2\}\) but not \(\{1,2\}\) has two connected components.
The C++, Python, and Java implementations all work modulo \(10^9+7\). They precompute factorials, inverse factorials, and modular inverses so that binomial factors and exponential-generating-function coefficients can be handled with simple modular multiplications.
Next they evaluate the raw counts \(R_r=2^{2^r-1}-1\). Because the modulus is prime, the enormous exponent \(2^r-1\) is reduced modulo \(10^9+6\) before fast modular exponentiation is applied. This keeps the computation small while preserving the correct modular value.
The inclusion-exclusion step is implemented as one polynomial convolution of the signed sequence \(((-1)^r R_r/r!)_{r\ge 0}\) with \((1/r!)_{r\ge 0}\). After the final sign adjustment, this produces the normalized coefficients \(a_n\).
The connected coefficients \(h_n\) are then recovered sequentially from the recurrence above. To obtain exactly \(K\) components, the implementation raises the truncated series \(H(x)\) to the \(K\)-th power by binary exponentiation, multiplies by the truncated series for \(e^x\), extracts the coefficient of \(x^N\), and finally multiplies by \(N!/K!\).
The C++ implementation additionally parallelizes the expensive convolutions and includes optional checkpoint validations on small cases before tackling the large target. The Python and Java implementations use the same mathematics with straightforward quadratic convolutions.
Let \(M=\max(n,K)\). Precomputing factorials, modular inverses, and the raw counts up to \(M\) costs \(O(M\log \text{MOD})\) time and \(O(M)\) memory, which is not the dominant part.
The main cost comes from truncated polynomial convolutions of degree \(M\). With the naive multiplication used here, one convolution costs \(O(M^2)\) time and \(O(M)\) additional memory. Recovering all connected coefficients from the recurrence is also \(O(M^2)\).
Exponentiating \(H(x)\) to the \(K\)-th power requires \(O(\log K)\) convolutions, so the total running time is \(O(M^2\log K)\) with an additional \(O(M^2)\) term from the recurrence. In practice the quadratic series operations dominate. Memory usage remains \(O(M)\) because only a small number of coefficient arrays are active at once.
Sei \([n]=\{1,\dots,n\}\). Wir wählen eine nichtleere Familie \(\mathcal{F}\) nichtleerer Teilmengen von \([n]\). Ihr Schnittgraph besitzt für jede gewählte Teilmenge einen Knoten, und zwei Knoten sind genau dann benachbart, wenn sich die zugehörigen Teilmengen schneiden. Gesucht ist \(C(n,K)\), also die Anzahl dieser Familien, deren Schnittgraph genau \(K\) Zusammenhangskomponenten hat. Für den Zielwert \(n=10000\) und \(K=10\) ist direkte Enumeration völlig ausgeschlossen.
Die Implementierungen lösen das Problem, indem sie zunächst alle Familien auf einer festen Labelmenge zählen und danach mit exponentiellen erzeugenden Funktionen die zusammenhängenden Strukturen herauslösen.
Auf einer Grundmenge der Größe \(r\) gibt es \(2^r-1\) nichtleere Teilmengen. Jede nichtleere Auswahl daraus ist eine gültige Familie, also ist die rohe Anzahl
$$R_r=2^{2^r-1}-1.$$
Schon ohne jede Konnektivitätsbedingung wächst dieser Ausdruck doppelt exponentiell. Deshalb ist ein Brute-Force-Verfahren für die echten Parameter unmöglich.
Sei \(U_n\) die Anzahl der Familien, deren Vereinigung genau \([n]\) ist. Mit Inklusion-Exklusion entfernen wir alle Familien, in denen mindestens ein Label fehlt. Beschränkt man sich auf eine gewählte Menge von \(r\) Labels, dann müssen alle ausgewählten Teilmengen innerhalb dieser \(r\)-Menge liegen, und es gibt genau \(R_r\) Möglichkeiten. Also gilt
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
Für den Schritt mit erzeugenden Funktionen normieren wir mit Fakultäten:
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
Der Sonderwert \(a_0=1\) steht für die leere Zusammenstellung von Zusammenhangskomponenten; das ist eine übliche Buchungskonvention in der Exponentialformel.
Betrachte eine Familie, deren Vereinigung ganz \([n]\) ist. Wenn zwei Graphkomponenten ein Label \(t\) gemeinsam hätten, dann würde eine gewählte Teilmenge aus der ersten Komponente und eine aus der zweiten beide \(t\) enthalten. Diese beiden Teilmengen würden sich schneiden und damit eine Kante zwischen den Komponenten erzeugen. Das ist unmöglich. Also verwenden verschiedene Zusammenhangskomponenten disjunkte Labelblöcke.
Umgekehrt: Zerlegt man \([n]\) in disjunkte nichtleere Blöcke und legt auf jeden Block genau eine zusammenhängende Familie, dann besitzt der entstehende Schnittgraph genau diese Blöcke als Zusammenhangskomponenten. Familien, die jedes Label benutzen, sind also genau Mengen zusammenhängender Familien auf disjunkten markierten Blöcken.
Definiere
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
wobei \(h_n\) die Anzahl zusammenhängender Familien auf allen \(n\) Labels geteilt durch \(n!\) ist. Die Exponentialformel liefert dann
$$A(x)=\exp(H(x)).$$
Leitet man \(A(x)=\exp(H(x))\) ab, so erhält man
$$A'(x)=H'(x)A(x).$$
Durch Koeffizientenvergleich bei \(x^{m-1}\) folgt
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}.$$
Wegen \(a_0=1\) wird daraus die Rekursion
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}.$$
Damit lassen sich die zusammenhängenden Anzahlen Größe für Größe berechnen, sobald die Vollbenutzungszahlen bekannt sind.
Im eigentlichen Problem muss nicht jedes Label in einer gewählten Teilmenge vorkommen. Ein unbenutztes Label erzeugt keinen Graphknoten und kann unabhängig gewählt werden; das führt auf den markierten Faktor
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}.$$
Eine Menge von genau \(K\) zusammenhängenden Komponenten trägt den Faktor
$$\frac{H(x)^K}{K!}.$$
Also ist die gesuchte Anzahl
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
Genau diese Koeffizientenformel wird von den Implementierungen ausgewertet.
Es gilt \(R_0=0\), \(R_1=1\) und \(R_2=2^3-1=7\). Daher
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
also
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
Die Rekursion liefert
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2.$$
Somit
$$H(x)=x+2x^2+O(x^3).$$
Für genau eine Zusammenhangskomponente erhält man
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6.$$
Für genau zwei Zusammenhangskomponenten ergibt sich
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1.$$
Das stimmt mit der direkten Kontrolle überein: Unter den sieben nichtleeren Familien auf \(\{1,2\}\) besitzt nur die Familie mit \(\{1\}\) und \(\{2\}\), aber ohne \(\{1,2\}\), zwei Zusammenhangskomponenten.
Die Implementierungen in C++, Python und Java arbeiten alle modulo \(10^9+7\). Zuerst werden Fakultäten, inverse Fakultäten und modulare Inverse vorbereitet, damit Binomialfaktoren und Koeffizienten exponentieller erzeugender Funktionen durch einfache modulare Multiplikationen berechnet werden können.
Danach werden die Rohzahlen \(R_r=2^{2^r-1}-1\) ausgewertet. Da der Modulus prim ist, wird der riesige Exponent \(2^r-1\) zunächst modulo \(10^9+6\) reduziert und anschließend per schneller modularer Potenzierung verarbeitet. So bleibt die Rechnung klein und der modulare Wert korrekt.
Der Inklusion-Exklusion-Schritt wird als eine Polynomfaltung der vorzeichenbehafteten Folge \(((-1)^r R_r/r!)_{r\ge 0}\) mit \((1/r!)_{r\ge 0}\) umgesetzt. Nach der abschließenden Vorzeichenkorrektur liegen die normierten Koeffizienten \(a_n\) vor.
Die zusammenhängenden Koeffizienten \(h_n\) werden danach nacheinander mit der obigen Rekursion rekonstruiert. Für genau \(K\) Komponenten potenziert die Implementierung die abgeschnittene Reihe \(H(x)\) mit binärer Exponentiation, multipliziert mit der abgeschnittenen Reihe von \(e^x\), liest den Koeffizienten von \(x^N\) ab und multipliziert am Ende mit \(N!/K!\).
Die C++-Implementierung parallelisiert zusätzlich die teuren Faltungen und enthält optionale Kontrollrechnungen für kleine Fälle, bevor sie die große Zieleingabe bearbeitet. Die Python- und Java-Versionen verwenden dieselbe Mathematik mit direkten quadratischen Faltungen.
Sei \(M=\max(n,K)\). Das Vorberechnen von Fakultäten, modularen Inversen und Rohzahlen bis \(M\) kostet \(O(M\log \text{MOD})\) Zeit und \(O(M)\) Speicher; das ist nicht der dominante Teil.
Der Hauptaufwand entsteht durch abgeschnittene Polynomfaltungen vom Grad \(M\). Mit der hier benutzten naiven Multiplikation kostet eine Faltung \(O(M^2)\) Zeit und \(O(M)\) zusätzlichen Speicher. Auch die Rekonstruktion aller zusammenhängenden Koeffizienten aus der Rekursion benötigt \(O(M^2)\).
Die Potenzierung von \(H(x)\) zur \(K\)-ten Potenz erfordert \(O(\log K)\) Faltungen. Insgesamt ergibt sich also \(O(M^2\log K)\) Zeit plus ein zusätzlicher \(O(M^2)\)-Term aus der Rekursion. Praktisch dominieren die quadratischen Reihenoperationen. Der Speicherverbrauch bleibt \(O(M)\), weil jeweils nur wenige Koeffizientenfelder gleichzeitig aktiv sind.
\([n]=\{1,\dots,n\}\) olsun. \([n]\)'in boş olmayan alt kümelerinden oluşan boş olmayan bir \(\mathcal{F}\) ailesi seçiyoruz. Kesişim grafında her seçilmiş alt küme bir düğümdür; iki düğüm ancak ve ancak karşılık gelen alt kümeler kesişiyorsa komşudur. İstenen şey, kesişim grafı tam olarak \(K\) bağlı bileşene sahip olan bu ailelerin sayısı \(C(n,K)\)'dir. Hedef girdi \(n=10000\) ve \(K=10\) olduğundan doğrudan sayım tamamen imkansızdır.
Uygulamalar problemi iki aşamada çözüyor: önce sabit bir etiket kümesi üzerindeki tüm aileleri sayıyor, sonra üstel üreteç fonksiyonlarıyla bağlı olanları ayıklıyor.
Büyüklüğü \(r\) olan bir taban kümede \(2^r-1\) tane boş olmayan alt küme vardır. Bunların boş olmayan her seçimi geçerli bir aile verir. Bu yüzden ham sayı
$$R_r=2^{2^r-1}-1$$
olur. Bağlılık şartını daha düşünmeden bile bu ifade çift üstel büyüdüğü için gerçek parametrelerde kaba kuvvet yaklaşımı kullanılamaz.
\(U_n\), birleşimi tam olarak \([n]\) olan ailelerin sayısı olsun. En az bir etiketi hiç kullanmayan aileleri dahil et-çıkar ile temizleriz. Eğer dikkati \(r\) etiketli seçilmiş bir kümeye sınırlandırırsak, seçilen tüm alt kümeler o \(r\) etiketin içinde kalmak zorundadır; dolayısıyla \(R_r\) seçenek vardır. Böylece
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
Üreteç fonksiyonu adımı için faktöriyellerle normalize ederiz:
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
\(a_0=1\) özel değeri, bağlı bileşenlerden oluşan boş düzenlemeyi temsil eder; bu, üstel formülde standart bir muhasebe kuralıdır.
Birleşimi bütün \([n]\) olan bir aile düşünelim. Eğer grafın iki farklı bileşeni ortak bir \(t\) etiketini paylaşsaydı, birinci bileşendeki bir seçilmiş alt küme ile ikinci bileşendeki bir seçilmiş alt küme ikisi de \(t\)'yi içerirdi. O zaman bu iki alt küme kesişir ve bileşenler arasında bir kenar oluşurdu. Bu çelişkidir. Demek ki farklı bağlı bileşenler ayrık etiket blokları kullanır.
Tersine, \([n]\)'i ayrık ve boş olmayan bloklara ayırıp her bloğun üzerine bir bağlı aile koyarsak, ortaya çıkan kesişim grafının bağlı bileşenleri tam olarak bu bloklar olur. Yani her etiketi kullanan aileler, ayrık etiket blokları üzerindeki bağlı ailelerin kümesi olarak ayrışır.
Şöyle tanımlayalım:
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
burada \(h_n\), tüm \(n\) etiketi kullanan bağlı ailelerin sayısının \(n!\)'ye bölünmüş halidir. Üstel formül
$$A(x)=\exp(H(x))$$
sonucunu verir.
\(A(x)=\exp(H(x))\) eşitliğinin türevini alınca
$$A'(x)=H'(x)A(x)$$
elde edilir. \(x^{m-1}\) katsayılarını eşitleyince
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}$$
çıkar. \(a_0=1\) olduğundan bu
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}$$
yinelemesine dönüşür. Böylece tüm etiketleri kullanan sayılar bilindikten sonra bağlı sayılar boyut boyut hesaplanabilir.
Asıl problemde her etiketin seçilmiş bir alt kümede görünmesi zorunlu değildir. Hiç kullanılmayan bir etiket grafikte düğüm oluşturmaz ve bağımsız seçilebilir; bunun üreteç fonksiyonu çarpanı
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}$$
olur. Tam olarak \(K\) bağlı bileşenden oluşan bir küme ise
$$\frac{H(x)^K}{K!}$$
katkısını yapar. Dolayısıyla aranan sayı
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
Programların hesapladığı son katsayı formülü tam olarak budur.
\(R_0=0\), \(R_1=1\) ve \(R_2=2^3-1=7\) olur. O halde
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
dolayısıyla
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
Yineleme
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2$$
sonucunu verir. Böylece
$$H(x)=x+2x^2+O(x^3)$$
olur. Tek bağlı bileşen için
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6$$
elde edilir. İki bağlı bileşen içinse
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1$$
çıkar. Bu, doğrudan kontrolle de aynıdır: \(\{1,2\}\) üzerindeki yedi boş olmayan aile arasında yalnızca \(\{1\}\) ve \(\{2\}\)'yi içerip \(\{1,2\}\)'yi içermeyen aile iki bağlı bileşen verir.
C++, Python ve Java uygulamalarının hepsi \(10^9+7\) modunda çalışır. Önce faktöriyeller, ters faktöriyeller ve modüler tersler hazırlanır; böylece binom katsayıları ile üstel üreteç fonksiyonu katsayıları basit modüler çarpımlarla hesaplanabilir.
Daha sonra ham sayılar \(R_r=2^{2^r-1}-1\) hesaplanır. Modül asal olduğu için devasa üs \(2^r-1\) önce \(10^9+6\) moduna indirilir, ardından hızlı modüler üs alma uygulanır. Böylece hesap küçük kalırken modüler sonuç doğru korunur.
Dahil et-çıkar adımı, \(((-1)^r R_r/r!)_{r\ge 0}\) işaretli dizisi ile \((1/r!)_{r\ge 0}\) dizisinin bir polinom evrişimi olarak gerçekleştirilir. Son işaret düzeltmesinden sonra normalize katsayılar \(a_n\) elde edilir.
Bağlı katsayılar \(h_n\) daha sonra yukarıdaki yineleme ile sırayla bulunur. Tam \(K\) bileşen için uygulama, kesilmiş \(H(x)\) serisini ikili üs alma ile \(K\). kuvvete yükseltir, \(e^x\) serisiyle çarpar, \(x^N\) katsayısını alır ve sonunda \(N!/K!\) ile çarpar.
C++ uygulaması ek olarak pahalı evrişimleri paralelleştirir ve büyük hedefe geçmeden önce küçük örneklerde isteğe bağlı doğrulamalar yapar. Python ve Java uygulamaları aynı matematiği doğrudan kuadratik evrişimlerle uygular.
\(M=\max(n,K)\) olsun. Faktöriyel, modüler ters ve ham sayıların \(M\)'ye kadar hazırlanması \(O(M\log \text{MOD})\) zaman ve \(O(M)\) bellek gerektirir; baskın maliyet bu değildir.
Ana yük, derecesi \(M\) olan kesilmiş polinom evrişimlerinden gelir. Burada kullanılan saf çarpım yöntemiyle bir evrişim \(O(M^2)\) zaman ve \(O(M)\) ek bellek ister. Yinelemeden tüm bağlı katsayıları çıkarmak da \(O(M^2)\) maliyetlidir.
\(H(x)\) serisini \(K\). kuvvete yükseltmek \(O(\log K)\) adet evrişim gerektirir. Bu yüzden toplam çalışma süresi \(O(M^2\log K)\) ve buna ek bir \(O(M^2)\) yineleme terimidir. Pratikte kuadratik seri işlemleri baskın kalır. Aynı anda yalnızca az sayıda katsayı dizisi tutulduğu için bellek kullanımı \(O(M)\) düzeyindedir.
Sea \([n]=\{1,\dots,n\}\). Elegimos una familia no vacía \(\mathcal{F}\) de subconjuntos no vacíos de \([n]\). Su grafo de intersección tiene un vértice por cada subconjunto elegido, y dos vértices son adyacentes exactamente cuando los subconjuntos correspondientes se intersectan. Debemos calcular \(C(n,K)\), el número de tales familias cuyo grafo de intersección tiene exactamente \(K\) componentes conexas. La entrada objetivo es \(n=10000\) y \(K=10\), así que una enumeración directa es totalmente inviable.
Las implementaciones resuelven el problema en dos etapas: primero cuentan todas las familias sobre un conjunto fijo de etiquetas, y luego extraen las conectadas mediante funciones generadoras exponenciales.
Sobre un conjunto base de tamaño \(r\) hay \(2^r-1\) subconjuntos no vacíos. Cualquier selección no vacía de esos subconjuntos forma una familia válida, así que el conteo bruto es
$$R_r=2^{2^r-1}-1.$$
Incluso antes de imponer conectividad, esta cantidad crece de manera doblemente exponencial, lo que explica por qué la fuerza bruta no sirve para los parámetros reales.
Sea \(U_n\) el número de familias cuya unión es exactamente \([n]\). La inclusión-exclusión elimina las familias que omiten al menos una etiqueta. Si restringimos la atención a un conjunto elegido de \(r\) etiquetas, entonces todos los subconjuntos seleccionados deben vivir dentro de ese \(r\)-conjunto, y por tanto hay \(R_r\) posibilidades. Luego
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
Para el paso de funciones generadoras normalizamos por factoriales:
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
El valor especial \(a_0=1\) representa el ensamblaje vacío de componentes conexas; es la convención estándar de contabilidad en la fórmula exponencial.
Consideremos una familia cuya unión es todo \([n]\). Si dos componentes del grafo compartieran una etiqueta \(t\), entonces algún subconjunto elegido de la primera componente y otro de la segunda contendrían ambos a \(t\). Esos dos subconjuntos se intersectarían y aparecería una arista entre las componentes, lo cual es imposible. Por tanto, componentes conexas distintas usan bloques disjuntos de etiquetas.
Recíprocamente, si particionamos \([n]\) en bloques disjuntos no vacíos y colocamos una familia conexa sobre cada bloque, el grafo de intersección resultante tiene exactamente esos bloques como componentes conexas. Así, las familias que usan todas las etiquetas son precisamente conjuntos de familias conexas sobre bloques etiquetados y disjuntos.
Definimos
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
donde \(h_n\) es el número de familias conexas que usan las \(n\) etiquetas, dividido por \(n!\). La fórmula exponencial da
$$A(x)=\exp(H(x)).$$
Al derivar \(A(x)=\exp(H(x))\) obtenemos
$$A'(x)=H'(x)A(x).$$
Igualando el coeficiente de \(x^{m-1}\) resulta
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}.$$
Como \(a_0=1\), esto se convierte en la recurrencia
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}.$$
De este modo, los conteos conexos se recuperan tamaño por tamaño una vez conocidos los conteos que usan todas las etiquetas.
El problema original no obliga a que cada etiqueta aparezca en algún subconjunto elegido. Una etiqueta no usada no aporta ningún vértice al grafo y puede elegirse de forma independiente; esto produce el factor etiquetado
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}.$$
Un conjunto de exactamente \(K\) componentes conexas aporta
$$\frac{H(x)^K}{K!}.$$
Por lo tanto, el conteo buscado es
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
Esa es exactamente la fórmula de extracción de coeficientes que evalúan las implementaciones.
Tenemos \(R_0=0\), \(R_1=1\) y \(R_2=2^3-1=7\). Entonces
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
y por tanto
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
La recurrencia da
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2.$$
Así,
$$H(x)=x+2x^2+O(x^3).$$
Para una sola componente conexa,
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6.$$
Para dos componentes conexas,
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1.$$
Esto coincide con la inspección directa: entre las siete familias no vacías sobre \(\{1,2\}\), solo la familia que contiene \(\{1\}\) y \(\{2\}\), pero no \(\{1,2\}\), tiene dos componentes conexas.
Las implementaciones en C++, Python y Java trabajan módulo \(10^9+7\). Primero precalculan factoriales, factoriales inversos e inversos modulares, para que los factores binomiales y los coeficientes de funciones generadoras exponenciales se manejen con multiplicaciones modulares simples.
Después evalúan los conteos brutos \(R_r=2^{2^r-1}-1\). Como el módulo es primo, el exponente enorme \(2^r-1\) se reduce primero módulo \(10^9+6\), y luego se aplica exponenciación modular rápida. Esto mantiene pequeña la computación sin alterar el valor modular correcto.
El paso de inclusión-exclusión se implementa como una sola convolución polinómica de la sucesión con signo \(((-1)^r R_r/r!)_{r\ge 0}\) con \((1/r!)_{r\ge 0}\). Tras el ajuste final de signo, se obtienen los coeficientes normalizados \(a_n\).
Los coeficientes conexos \(h_n\) se recuperan después de forma secuencial mediante la recurrencia anterior. Para obtener exactamente \(K\) componentes, la implementación eleva la serie truncada \(H(x)\) a la potencia \(K\) mediante exponenciación binaria, la multiplica por la serie truncada de \(e^x\), extrae el coeficiente de \(x^N\) y finalmente multiplica por \(N!/K!\).
La implementación en C++ además paraleliza las convoluciones costosas e incluye validaciones opcionales en casos pequeños antes de atacar la entrada grande. Las versiones en Python y Java usan la misma matemática con convoluciones cuadráticas directas.
Sea \(M=\max(n,K)\). Precalcular factoriales, inversos modulares y conteos brutos hasta \(M\) cuesta \(O(M\log \text{MOD})\) tiempo y \(O(M)\) memoria, pero esa no es la parte dominante.
El costo principal proviene de las convoluciones polinómicas truncadas de grado \(M\). Con la multiplicación ingenua empleada aquí, una convolución cuesta \(O(M^2)\) tiempo y \(O(M)\) memoria adicional. Recuperar todos los coeficientes conexos a partir de la recurrencia también cuesta \(O(M^2)\).
Elevar \(H(x)\) a la potencia \(K\) requiere \(O(\log K)\) convoluciones, por lo que el tiempo total es \(O(M^2\log K)\) más un término adicional \(O(M^2)\) debido a la recurrencia. En la práctica dominan las operaciones cuadráticas sobre series. La memoria permanece en \(O(M)\) porque solo se mantienen activas unas pocas tablas de coeficientes al mismo tiempo.
设 \([n]=\{1,\dots,n\}\)。我们从 \([n]\) 的所有非空子集中选出一个非空族 \(\mathcal{F}\)。把这个族看成一个交图：每个被选中的子集对应一个顶点，当且仅当两个子集有交集时，在对应顶点之间连一条边。题目要求计算 \(C(n,K)\)，也就是交图恰好有 \(K\) 个连通分量的此类集合族个数。目标输入是 \(n=10000\)、\(K=10\)，因此不可能直接枚举所有候选族。
三个实现采用的是同一条思路：先统计固定标号集合上的全部集合族，再用指数型生成函数把“连通”的部分抽取出来。
如果底层标号集合大小为 \(r\)，那么它的非空子集共有 \(2^r-1\) 个。从这些非空子集中任意选出一个非空子集族，就得到一个合法对象。因此原始计数为
$$R_r=2^{2^r-1}-1.$$
这个数量在还没有加入连通性限制之前就已经是双指数增长，所以真实参数下暴力搜索毫无可行性。
记 \(U_n\) 为并集恰好等于 \([n]\) 的集合族数量。也就是说，这些集合族真正用到了全部 \(n\) 个标号。要从“所有集合族”中过滤出这一类，最自然的方法是容斥：如果我们只允许使用某个大小为 \(r\) 的标号子集，那么所有被选中的子集都必须完全落在这 \(r\) 个标号之内，此时可能的集合族数就是 \(R_r\)。于是
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
为了进入生成函数框架，我们把这些计数按阶乘归一化：
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
这里 \(a_0=1\) 不是在说原题里存在一个“空的非空族”，而是生成函数中的标准记账方式：它表示“没有任何连通块”的空装配。
现在考虑一个并集已经覆盖全部 \([n]\) 的集合族。设它的交图分成若干个连通分量。如果两个不同的连通分量共享某个标号 \(t\)，那么第一个分量里一定有某个被选子集包含 \(t\)，第二个分量里也一定有某个被选子集包含 \(t\)。这两个子集因此会相交，于是它们对应的两个顶点之间必须有边，从而这两个分量其实应当连在一起，矛盾。
所以，不同连通分量所使用的标号块必然彼此不相交。反过来，如果我们把 \([n]\) 分成若干个互不相交的非空标号块，并在每个标号块上放置一个“自身连通”的集合族，那么合并以后得到的交图，其连通分量恰好就是这些标号块。于是，“使用全部标号的集合族”正好等价于“若干个连通集合族在互不相交的带标号块上的集合”。
定义
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
其中 \(h_n\) 表示“使用全部 \(n\) 个标号且交图连通”的集合族数，再除以 \(n!\) 之后得到的归一化系数。根据组合学中的指数公式，有
$$A(x)=\exp(H(x)).$$
对 \(A(x)=\exp(H(x))\) 两边求导，可得
$$A'(x)=H'(x)A(x).$$
比较 \(x^{m-1}\) 的系数，就得到
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}.$$
由于 \(a_0=1\)，所以可以把右边最后一项单独移出，从而得到递推式
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}.$$
这说明：只要已经知道所有“用满标号”的归一化计数 \(a_m\)，就可以按大小从小到大逐步恢复所有“连通”的归一化计数 \(h_m\)。
原题并没有要求每个标号都必须出现在某个被选子集中。一个没有被使用的标号不会在交图里产生任何顶点，它只是一个“空闲”的标号原子，因此对应的指数型生成函数因子是
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}.$$
另一方面，恰好 \(K\) 个连通分量意味着我们要取一个由 \(K\) 个连通对象组成的集合，其生成函数贡献是
$$\frac{H(x)^K}{K!}.$$
因此最终答案满足
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
这就是程序真正计算的核心公式。
当 \(n=2\) 时，有 \(R_0=0\)、\(R_1=1\)、\(R_2=2^3-1=7\)。于是
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
所以
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
递推给出
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2.$$
因此
$$H(x)=x+2x^2+O(x^3).$$
若要求恰好 1 个连通分量，则
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6.$$
若要求恰好 2 个连通分量，则
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1.$$
这与手工检查完全一致：在 \(\{1,2\}\) 上的 7 个非空集合族中，只有包含 \(\{1\}\) 与 \(\{2\}\) 但不包含 \(\{1,2\}\) 的那个族是不连通的。
C++、Python 和 Java 三个实现都在模 \(10^9+7\) 下工作。首先预处理阶乘、逆阶乘以及整数的模逆，这样二项式系数和指数型生成函数中的 \(1/j!\) 因子都可以转化为简单的模乘。
接下来程序计算原始数量 \(R_r=2^{2^r-1}-1\)。因为模数是素数，极大的指数 \(2^r-1\) 可以先对 \(10^9+6\) 取模，再进行快速模幂运算。这样既保持了正确的模值，也避免了真正处理天文级指数。
容斥步骤被写成一次多项式卷积：把带符号序列 \(((-1)^r R_r/r!)_{r\ge 0}\) 与 \((1/r!)_{r\ge 0}\) 相乘，经过最后的符号调整后，就得到所有归一化系数 \(a_n\)。
随后，程序根据前面的递推式按顺序恢复所有连通系数 \(h_n\)。要得到恰好 \(K\) 个连通分量的答案，就把截断后的 \(H(x)\) 级数用二进制幂法提升到 \(K\) 次方，再乘上 \(e^x\) 的截断级数，抽取 \(x^N\) 的系数，最后乘上 \(N!/K!\)。
C++ 版本还会把最耗时的卷积部分并行化，并在处理大规模目标输入之前提供若干小规模校验点。Python 和 Java 版本使用相同的数学公式，但卷积实现保持为直接的二次复杂度形式。
设 \(M=\max(n,K)\)。预处理到 \(M\) 为止的阶乘、模逆和原始计数需要 \(O(M\log \text{MOD})\) 时间与 \(O(M)\) 空间，但这不是主要瓶颈。
真正的主要代价来自次数截断到 \(M\) 的多项式卷积。这里使用的是朴素乘法，因此一次卷积需要 \(O(M^2)\) 时间和 \(O(M)\) 额外空间。根据递推恢复全部连通系数同样需要 \(O(M^2)\) 时间。
把 \(H(x)\) 提升到 \(K\) 次方需要 \(O(\log K)\) 次卷积，所以总时间复杂度是 \(O(M^2\log K)\)，再加上递推产生的一个 \(O(M^2)\) 项。实际运行时，主导成本仍然是这些二次级别的级数运算。空间复杂度保持在 \(O(M)\)，因为同时活动的系数数组数量很少。
Пусть \([n]=\{1,\dots,n\}\). Мы выбираем непустое семейство \(\mathcal{F}\) непустых подмножеств множества \([n]\). Его граф пересечений имеет по вершине для каждого выбранного подмножества, а две вершины соединяются ребром тогда и только тогда, когда соответствующие подмножества пересекаются. Нужно вычислить \(C(n,K)\) - число таких семейств, у которых граф пересечений имеет ровно \(K\) компонент связности. Целевой вход здесь \(n=10000\) и \(K=10\), поэтому прямой перебор полностью исключён.
Во всех трёх реализациях используется одна и та же схема: сначала считаются все семейства на фиксированном множестве меток, а затем с помощью экспоненциальных производящих функций выделяются связные объекты.
На базовом множестве размера \(r\) существует \(2^r-1\) непустых подмножеств. Любой непустой выбор из них даёт допустимое семейство, поэтому грубое число равно
$$R_r=2^{2^r-1}-1.$$
Даже без условия связности эта величина растёт вдвойне экспоненциально, так что перебор становится бессмысленным уже очень рано.
Обозначим через \(U_n\) число семейств, объединение которых равно ровно \([n]\). Принцип включений-исключений удаляет семейства, в которых хотя бы одна метка не используется. Если разрешить использовать только заранее выбранное множество из \(r\) меток, то все выбранные подмножества должны лежать внутри этого \(r\)-элементного множества, а значит, вариантов ровно \(R_r\). Следовательно,
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
Для перехода к производящим функциям удобно нормировать на факториалы:
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
Значение \(a_0=1\) означает пустую сборку из компонент связности; это стандартное соглашение в экспоненциальной формуле.
Рассмотрим семейство, объединение которого использует все метки из \([n]\). Если бы две разные компоненты графа делили общую метку \(t\), то в первой компоненте нашлось бы выбранное подмножество, содержащее \(t\), и во второй тоже. Эти два подмножества пересекались бы, значит между компонентами должно было бы быть ребро. Это невозможно. Следовательно, разные компоненты связности используют попарно непересекающиеся блоки меток.
Обратно, если разбить \([n]\) на непустые попарно непересекающиеся блоки и на каждом блоке разместить одно связное семейство, то итоговый граф пересечений будет иметь в точности эти блоки как компоненты связности. Поэтому семейства, использующие все метки, представляют собой именно множества связных семейств на непересекающихся размеченных блоках.
Определим
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
где \(h_n\) - число связных семейств, использующих все \(n\) меток, делённое на \(n!\). Тогда экспоненциальная формула даёт
$$A(x)=\exp(H(x)).$$
Дифференцируя равенство \(A(x)=\exp(H(x))\), получаем
$$A'(x)=H'(x)A(x).$$
Сравнение коэффициентов при \(x^{m-1}\) даёт
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}.$$
Так как \(a_0=1\), отсюда следует рекуррентная формула
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}.$$
Значит, зная нормированные количества для семейств, использующих все метки, можно по размеру последовательно восстановить все связные коэффициенты.
В исходной задаче не требуется, чтобы каждая метка вошла в какое-нибудь выбранное подмножество. Неиспользованная метка не создаёт вершину графа и выбирается независимо, поэтому её вклад даёт размеченный фактор
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}.$$
Множество ровно из \(K\) связных компонент даёт вклад
$$\frac{H(x)^K}{K!}.$$
Следовательно, искомое число равно
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
Именно эту формулу извлечения коэффициента реализуют программы.
Имеем \(R_0=0\), \(R_1=1\) и \(R_2=2^3-1=7\). Тогда
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
поэтому
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
Рекурсия даёт
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2.$$
Значит,
$$H(x)=x+2x^2+O(x^3).$$
Для одной компоненты связности получаем
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6.$$
Для двух компонент связности получаем
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1.$$
Это совпадает с прямой проверкой: среди семи непустых семейств на \(\{1,2\}\) ровно одно, содержащее \(\{1\}\) и \(\{2\}\), но не содержащее \(\{1,2\}\), имеет две компоненты связности.
Реализации на C++, Python и Java работают по модулю \(10^9+7\). Сначала предвычисляются факториалы, обратные факториалы и модульные обратные числа, чтобы биномиальные множители и коэффициенты экспоненциальных производящих функций сводились к простым модульным умножениям.
Затем вычисляются грубые значения \(R_r=2^{2^r-1}-1\). Поскольку модуль прост, огромный показатель \(2^r-1\) сначала уменьшается по модулю \(10^9+6\), после чего применяется быстрое модульное возведение в степень. Это позволяет держать вычисления компактными и при этом не потерять правильное значение по модулю.
Шаг включений-исключений реализован как одна полиномиальная свёртка знакопеременной последовательности \(((-1)^r R_r/r!)_{r\ge 0}\) с последовательностью \((1/r!)_{r\ge 0}\). После финальной поправки знака получаются нормированные коэффициенты \(a_n\).
Далее коэффициенты связных объектов \(h_n\) восстанавливаются последовательно по приведённой выше рекурсии. Чтобы получить ровно \(K\) компонент, реализация возводит усечённый ряд \(H(x)\) в \(K\)-ю степень бинарным методом, умножает на усечённый ряд для \(e^x\), извлекает коэффициент при \(x^N\) и в конце умножает на \(N!/K!\).
Версия на C++ дополнительно распараллеливает самые тяжёлые свёртки и содержит необязательные контрольные проверки на малых примерах перед вычислением большой целевой точки. Версии на Python и Java используют ту же математику с прямыми квадратичными свёртками.
Пусть \(M=\max(n,K)\). Предвычисление факториалов, модульных обратных и грубых значений до \(M\) требует \(O(M\log \text{MOD})\) времени и \(O(M)\) памяти, но это не главный вклад.
Основная стоимость возникает из-за усечённых полиномиальных свёрток степени \(M\). При наивном умножении, используемом здесь, одна свёртка стоит \(O(M^2)\) времени и \(O(M)\) дополнительной памяти. Восстановление всех коэффициентов связных объектов по рекурсии тоже занимает \(O(M^2)\).
Возведение \(H(x)\) в степень \(K\) требует \(O(\log K)\) свёрток, поэтому полное время работы равно \(O(M^2\log K)\) плюс дополнительный член \(O(M^2)\) из рекурсии. На практике доминируют именно квадратичные операции над рядами. Память остаётся порядка \(O(M)\), потому что одновременно хранятся лишь несколько массивов коэффициентов.
لتكن \([n]=\{1,\dots,n\}\). نختار عائلة غير فارغة \(\mathcal{F}\) من مجموعات جزئية غير فارغة من \([n]\). ثم نبني رسم التقاطع الخاص بها: لكل مجموعة مختارة رأس، ويوجد ضلع بين رأسين إذا وفقط إذا كانت المجموعتان المقابلتان تتقاطعان. المطلوب هو حساب \(C(n,K)\)، أي عدد هذه العائلات التي يملك رسم تقاطعها بالضبط \(K\) مركبات اتصال. في الحالة المستهدفة لدينا \(n=10000\) و\(K=10\)، ولذلك فإن التعداد المباشر غير ممكن عمليًا.
تعتمد التطبيقات الثلاثة على الفكرة نفسها: نعد أولًا جميع العائلات فوق مجموعة وسوم ثابتة، ثم نستخرج العائلات المتصلة باستخدام الدوال المولدة الأسية.
إذا كان حجم المجموعة الأساسية هو \(r\)، فإن عدد المجموعات الجزئية غير الفارغة هو \(2^r-1\). وكل اختيار غير فارغ من هذه المجموعات يعطي عائلة صالحة، ولذلك يكون العدد الخام
$$R_r=2^{2^r-1}-1.$$
حتى قبل فرض شرط الاتصال، ينمو هذا العدد نموًا أسيًا مضاعفًا، ولهذا لا يمكن الاعتماد على القوة الغاشمة عند القيم الحقيقية للمسألة.
لنرمز بـ \(U_n\) إلى عدد العائلات التي يساوي اتحادها تمامًا \([n]\). مبدأ الشمول والاستبعاد يزيل العائلات التي تهمل وسمًا واحدًا على الأقل. فإذا قصرنا الانتباه على مجموعة مختارة من \(r\) وسوم، كان لا بد أن تقع كل المجموعات المختارة داخل هذه المجموعة ذات الحجم \(r\)، ومن ثم يوجد \(R_r\) احتمالًا. لذلك نحصل على
$$U_n=\sum_{r=0}^{n}(-1)^{n-r}\binom{n}{r}R_r.$$
وللدخول في إطار الدوال المولدة، نطبع هذه الأعداد بقسمة على المضروب:
$$a_n=\frac{U_n}{n!}\quad (n\ge 1),\qquad a_0=1.$$
القيمة الخاصة \(a_0=1\) لا تعني وجود عائلة فارغة ضمن نص المسألة، بل تمثل "التجميع الخالي" لمركبات الاتصال، وهي قاعدة محاسبية معيارية في الصيغة الأسية.
لنأخذ عائلة يكون اتحادها هو كل \([n]\). إذا اشتركت مركبتان مختلفتان في الرسم في وسم واحد \(t\)، فلابد أن توجد مجموعة مختارة في المركبة الأولى تحتوي \(t\)، ومجموعة مختارة في المركبة الثانية تحتوي \(t\) أيضًا. عندئذ تتقاطع هاتان المجموعتان، فينشأ ضلع بين المركبتين، وهذا تناقض. إذن المركبات المختلفة لا يمكن أن تستعمل إلا كتلًا متباينة من الوسوم.
وبالعكس، إذا قسمنا \([n]\) إلى كتل غير فارغة ومتنافية، ووضعنا فوق كل كتلة عائلة متصلة واحدة، فإن رسم التقاطع الناتج تكون مركبات اتصاله هي هذه الكتل نفسها. لذلك فإن العائلات التي تستعمل جميع الوسوم تتفكك بالضبط إلى مجموعة من عائلات متصلة موضوعة على كتل موسومة ومتفارقة.
نعرّف
$$A(x)=\sum_{n\ge 0} a_n x^n,\qquad H(x)=\sum_{n\ge 1} h_n x^n,$$
حيث إن \(h_n\) هو عدد العائلات المتصلة التي تستعمل جميع الوسوم \(n\)، بعد قسمته على \(n!\). عندئذ تعطينا الصيغة الأسية
$$A(x)=\exp(H(x)).$$
باشتقاق العلاقة \(A(x)=\exp(H(x))\) نحصل على
$$A'(x)=H'(x)A(x).$$
وبمقارنة معامل \(x^{m-1}\) ينتج
$$m a_m=\sum_{i=1}^{m} i h_i a_{m-i}.$$
وبما أن \(a_0=1\)، فإن ذلك يتحول إلى العلاقة التراجعية
$$h_m=a_m-\frac{1}{m}\sum_{i=1}^{m-1} i h_i a_{m-i}.$$
وهكذا يمكن استرجاع الأعداد المتصلة حجمًا بعد حجم، متى عُرفت أعداد العائلات التي تستعمل جميع الوسوم.
المسألة الأصلية لا تفرض أن يظهر كل وسم داخل مجموعة مختارة. الوسم غير المستعمل لا يولد رأسًا في الرسم ويمكن اختياره استقلالًا، ولذلك يساهم بالعامل الموسوم
$$e^x=\sum_{j\ge 0}\frac{x^j}{j!}.$$
أما مجموعة مكونة من \(K\) مركبات متصلة بالضبط فتساهم بالعامل
$$\frac{H(x)^K}{K!}.$$
ومن ثم يكون العدد المطلوب
$$\boxed{C(n,K)=n!\,\left[x^n\right]\left(e^x\frac{H(x)^K}{K!}\right).}$$
وهذه هي صيغة استخراج المعامل التي تنفذها التطبيقات فعليًا.
لدينا \(R_0=0\) و\(R_1=1\) و\(R_2=2^3-1=7\). لذا
$$U_1=1,\qquad U_2=7-2\cdot 1=5,$$
ومن ثم
$$a_1=1,\qquad a_2=\frac{5}{2}.$$
وتعطي العلاقة التراجعية
$$h_1=a_1=1,\qquad h_2=a_2-\frac{1}{2}h_1a_1=\frac{5}{2}-\frac{1}{2}=2.$$
إذن
$$H(x)=x+2x^2+O(x^3).$$
عند طلب مركبة اتصال واحدة نحصل على
$$C(2,1)=2!\,\left[x^2\right]\left(e^xH(x)\right)=2!\,(2+1)=6.$$
وعند طلب مركبتي اتصال نحصل على
$$C(2,2)=2!\,\left[x^2\right]\left(e^x\frac{H(x)^2}{2}\right)=2!\cdot\frac{1}{2}=1.$$
وهذا يطابق الفحص المباشر: بين العائلات السبعة غير الفارغة فوق \(\{1,2\}\)، العائلة الوحيدة غير المتصلة هي التي تحتوي \(\{1\}\) و\(\{2\}\) ولا تحتوي \(\{1,2\}\).
تعمل تطبيقات C++ وPython وJava جميعها بترديد \(10^9+7\). في البداية تُحضَّر المضاريب، ومعكوسات المضاريب، والمعكوسات الضربية، حتى تتحول معاملات ذوات الحدين وعوامل الدوال المولدة الأسية إلى ضربات معيارية بسيطة.
بعد ذلك تُحسب القيم الخام \(R_r=2^{2^r-1}-1\). وبما أن الترديد عدد أولي، فإن الأس الهائل \(2^r-1\) يُختزل أولًا modulo \(10^9+6\)، ثم تُستخدم أسس معيارية سريعة. وبهذا تبقى الحسابات صغيرة من دون أن نفقد القيمة الصحيحة modulo \(10^9+7\).
تُنفَّذ خطوة الشمول والاستبعاد على هيئة التفاف كثيرات حدود واحد بين المتتالية ذات الإشارة \(((-1)^r R_r/r!)_{r\ge 0}\) والمتتالية \((1/r!)_{r\ge 0}\). وبعد تصحيح الإشارة في النهاية نحصل على المعاملات المعيارية \(a_n\).
ثم تُستعاد معاملات الجزء المتصل \(h_n\) بالتتابع من العلاقة السابقة. وللحصول على عدد البنى ذات \(K\) مركبات بالضبط، ترفع الشيفرة السلسلة المقطوعة \(H(x)\) إلى القوة \(K\) باستخدام الرفع الثنائي، ثم تضربها في السلسلة المقطوعة لـ \(e^x\)، ثم تستخرج معامل \(x^N\)، وأخيرًا تضرب في \(N!/K!\).
تضيف نسخة C++ توازيًا في التفافات كثيرات الحدود الأكثر كلفة، كما تتضمن نقاط تحقق اختيارية على أمثلة صغيرة قبل الانتقال إلى الإدخال الكبير. أما نسختا Python وJava فتستخدمان الرياضيات نفسها مع التفافات تربيعية مباشرة.
لنضع \(M=\max(n,K)\). إن التحضير المسبق للمضاريب والمعكوسات والقيم الخام حتى \(M\) يحتاج إلى زمن \(O(M\log \text{MOD})\) وذاكرة \(O(M)\)، لكنه ليس الجزء المسيطر.
العبء الأساسي يأتي من التفافات كثيرات الحدود المقطوعة حتى الدرجة \(M\). مع الضرب الساذج المستخدم هنا، تكلف عملية التفاف واحدة \(O(M^2)\) زمنًا و\(O(M)\) ذاكرة إضافية. كما أن استرجاع جميع معاملات الجزء المتصل من العلاقة التراجعية يكلف أيضًا \(O(M^2)\).
رفع \(H(x)\) إلى القوة \(K\) يحتاج إلى \(O(\log K)\) التفافات، ولذلك يكون الزمن الكلي \(O(M^2\log K)\) مع حد إضافي \(O(M^2)\) ناتج عن العلاقة التراجعية. عمليًا تظل عمليات السلاسل التربيعية هي المسيطرة. وتبقى الذاكرة في حدود \(O(M)\) لأن عدد مصفوفات المعاملات النشطة في اللحظة نفسها صغير.