There are three plates containing \(a\), \(b\), and \(c\) beans, and exactly one bean is magical. A question may inspect only a subset taken from a single plate, and the answer is just yes or no. Let \(h(a,b,c)\) be the minimum number of such questions that always identifies the magical bean. The task is to evaluate
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
A brute-force search over triples or over decision trees is hopeless for the true input size, so the solution turns the problem into a counting argument over dyadic ranges.
Write \(s=a+b+c\) for the total number of candidate beans. The whole strategy revolves around the threshold
$$D=2^{k-1}\qquad\text{whenever}\qquad 2^{k-1}\lt s\le 2^k.$$
At that scale, \(k\) is the information-theoretic lower bound, and the only question is whether a given triple attains that bound or needs one extra step.
With \(s\) possible locations for the magical bean, any yes/no decision tree of depth \(t\) has at most \(2^t\) leaves. Therefore every strategy satisfies
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$$
For fixed \(s\), the number of nonnegative triples \((a,b,c)\) with total \(s\) is the stars-and-bars count
$$\binom{s+2}{2}.$$
So the universal baseline contribution is
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$$
Since \(\lceil\log_2 1\rceil=0\), the \(s=1\) term vanishes automatically. The implementations group this sum by dyadic blocks \((2^{k-1},2^k]\) and expand
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2},$$
so each block can be evaluated from closed forms for \(\sum s\) and \(\sum s^2\).
Fix a triple with \(2^{k-1}\lt s\le 2^k\), and set \(D=2^{k-1}\). If we hope to finish in exactly \(k\) questions, then after the first question both branches must leave at most \(D\) candidates, because only \(k-1\) further yes/no answers remain.
Suppose the first question selects a subset of size \(q\) from one plate. Then the two branch sizes are \(q\) and \(s-q\), so we must have
$$s-D\le q\le D.$$
Inside the cube \(0\le a,b,c\le D\), the chosen subset can only come from a plate that contains at least \(s-D\) beans. Thus a triple is easy at level \(k\) if at least one coordinate is at least \(s-D\). It is hard if no coordinate reaches that threshold.
Because \(s=a+b+c\), the condition \(a\lt s-D\) is equivalent to \(b+c\gt D\), and similarly for the other coordinates. Therefore, inside the cube, hardness is exactly the system
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$$
Every hard triple needs \(k+1\) questions; every non-hard triple attains the lower bound \(k\).
Define
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
This is the hard region at level \(k\) restricted to triples with total at most \(X\). To count it, use inclusion-exclusion on the three “easy” events
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
By symmetry,
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$$
where \(U_D(X)\) counts all triples in the box with total at most \(X\), \(A_D(X)\) counts one easy event such as \(E_{ab}\), \(B_D(X)\) counts an intersection of two easy events, and \(C_D(X)\) counts the intersection of all three.
The simplest term is the universe count:
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
The remaining terms reduce to one-dimensional polynomial sums after fixing either a pair sum or one coordinate. That is why the implementation only needs closed forms for arithmetic and quadratic progressions rather than any explicit enumeration of triples.
Now consider a triple with total \(s\le 2D\) but with one coordinate larger than \(D\). Because \(s\le 2D\), at most one coordinate can exceed \(D\).
Assume \(a\gt D\). To keep both branches within size \(D\), the first question must isolate exactly \(D\) beans from that oversized plate. The “yes” branch then has exactly \(D\) candidates, while the “no” branch leaves the reduced triple
$$\left(a-D,\ b,\ c\right),$$
whose total is \(s-D\).
So the original triple is hard at level \(k\) precisely when the reduced triple is hard at level \(k-1\). If we let \(E_k(X)\) denote the number of hard triples with total at most \(X\) on level \(k\), then
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$$
The factor \(3\) comes from the choice of which plate is the oversized one.
Let \(K\) be the largest integer with \(2^{K-1}\lt N\le 2^K\). Every triple in the dyadic block \(2^{k-1}\lt s\le 2^k\) contributes the baseline \(k\), and every hard triple contributes one extra question. Hence
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$$
This is the exact formula used by the implementation.
Take \(s=8\). Then \(k=3\) and \(D=4\).
For the triple \((3,3,2)\), all pair sums exceed \(4\):
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
So it lies in the hard region. Any three-question strategy would need its first question to split the eight candidates into two branches of size at most four, which forces a queried subset of size exactly \(4\). But no plate contains \(4\) beans, so such a first move is impossible. Therefore
$$h(3,3,2)=4.$$
By contrast, \((5,2,1)\) is easy at the same level: ask about a four-bean subset of the plate containing five beans. The “yes” branch leaves \(4\) candidates, and the “no” branch leaves \((1,2,1)\), whose total is \(4\), so two more questions suffice. Thus \(h(5,2,1)=3\).
The recursive idea appears one level higher with \((11,3,2)\), where \(s=16\) and \(D=8\). Asking about an eight-bean subset of the large plate leaves either a block of size \(8\) or the reduced triple \((3,3,2)\), already known to be hard. Hence \((11,3,2)\) is hard at level \(4\) and needs \(5\) questions.
The C++, Python, and Java implementations work entirely modulo \(10^9+7\). They first accumulate the baseline term by grouping totals \(s\) into dyadic intervals and evaluating
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
with closed forms for \(\sum s\) and \(\sum s^2\). Next they evaluate the hard-region counts \(W_D(X)\) by inclusion-exclusion. Each component of that inclusion-exclusion is reduced to a short list of polynomial range sums, so no loop over triples is ever required.
Finally, the implementation memoizes the recursive states \(E_k(X)\). Each state performs one within-cube count and, when \(X\gt 2^{k-1}\), one recursive call to the previous level. The answer is the baseline term plus the total number of hard triples across all relevant levels.
Let \(K=\lceil\log_2 N\rceil\). The number of dyadic levels is \(O(K)\), and each recursive state is evaluated once. Every state uses only constant-time modular arithmetic together with closed-form sums, so the total running time is \(O(\log N)\). The memoized state table also has size \(O(\log N)\).
Es gibt drei Teller mit \(a\), \(b\) und \(c\) Bohnen, und genau eine Bohne ist magisch. Eine Frage darf nur eine Teilmenge eines einzelnen Tellers prüfen, und die Antwort ist lediglich ja oder nein. Sei \(h(a,b,c)\) die minimale Anzahl solcher Fragen, mit denen die magische Bohne sicher identifiziert wird. Gesucht ist
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
Eine direkte Suche über alle Tripel oder gar über alle Entscheidungsbäume ist für die echten Parameter unmöglich. Deshalb formt die Lösung das Problem in eine Zählung über dyadische Bereiche um.
Schreibe \(s=a+b+c\) für die Gesamtzahl möglicher Positionen der magischen Bohne. Der gesamte Ansatz orientiert sich an der Schwelle
$$D=2^{k-1}\qquad\text{falls}\qquad 2^{k-1}\lt s\le 2^k.$$
Auf dieser Skala ist \(k\) die informationstheoretische Untergrenze. Danach muss nur noch entschieden werden, ob ein Tripel diese Schranke erreicht oder genau einen zusätzlichen Schritt braucht.
Bei \(s\) möglichen Kandidaten kann ein Ja/Nein-Entscheidungsbaum der Tiefe \(t\) höchstens \(2^t\) Blätter besitzen. Daher gilt immer
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$$
Für festes \(s\) ist die Anzahl nichtnegativer Tripel \((a,b,c)\) mit Summe \(s\) durch Stars and Bars gegeben:
$$\binom{s+2}{2}.$$
Damit ergibt sich der universelle Basisanteil
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$$
Da \(\lceil\log_2 1\rceil=0\), verschwindet der Term \(s=1\) automatisch. Die Implementierungen gruppieren diese Summe nach dyadischen Blöcken \((2^{k-1},2^k]\) und benutzen
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2},$$
sodass jeder Block aus geschlossenen Formeln für \(\sum s\) und \(\sum s^2\) berechnet werden kann.
Fixiere nun ein Tripel mit \(2^{k-1}\lt s\le 2^k\) und setze \(D=2^{k-1}\). Wenn wir in genau \(k\) Fragen fertig werden wollen, dann müssen nach der ersten Frage beide Äste höchstens \(D\) Kandidaten enthalten, denn es bleiben nur noch \(k-1\) Ja/Nein-Antworten.
Wählt die erste Frage eine Teilmenge der Größe \(q\) auf einem Teller, dann haben die beiden Zweige Größen \(q\) und \(s-q\). Also muss gelten
$$s-D\le q\le D.$$
Innerhalb des Würfels \(0\le a,b,c\le D\) kann diese Teilmenge nur von einem Teller stammen, der mindestens \(s-D\) Bohnen besitzt. Ein Tripel ist auf Stufe \(k\) also leicht, wenn mindestens eine Koordinate diesen Schwellenwert erreicht. Es ist schwer, wenn keine Koordinate groß genug ist.
Wegen \(s=a+b+c\) ist die Bedingung \(a\lt s-D\) äquivalent zu \(b+c\gt D\), und analog für die anderen Koordinaten. Innerhalb des Würfels ist Schwerheit daher genau das System
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$$
Jedes schwere Tripel braucht \(k+1\) Fragen; jedes nicht schwere Tripel erreicht die Untergrenze \(k\).
Definiere
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
Dies ist die schwere Region der Stufe \(k\), eingeschränkt auf Tripel mit Summe höchstens \(X\). Zur Auszählung verwendet man Inklusion-Exklusion für die drei “leichten” Ereignisse
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
Wegen der Symmetrie gilt
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$$
wobei \(U_D(X)\) alle Tripel im Würfel mit Summe höchstens \(X\) zählt, \(A_D(X)\) ein leichtes Ereignis wie \(E_{ab}\), \(B_D(X)\) einen Schnitt zweier leichter Ereignisse und \(C_D(X)\) den Schnitt aller drei.
Der einfachste Term ist die Universumszählung:
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
Die übrigen Terme reduzieren sich nach Fixierung einer Paar-Summe oder einer Koordinate auf eindimensionale Polynomsummen. Deshalb brauchen die Implementierungen nur geschlossene Formeln für arithmetische und quadratische Folgen und niemals eine explizite Enumeration aller Tripel.
Betrachte nun ein Tripel mit \(s\le 2D\), bei dem eine Koordinate größer als \(D\) ist. Wegen \(s\le 2D\) kann höchstens eine Koordinate diese Schranke überschreiten.
Nehmen wir \(a\gt D\) an. Um beide Äste auf Größe höchstens \(D\) zu halten, muss die erste Frage genau \(D\) Bohnen aus dieser großen Platte isolieren. Dann besitzt der “Ja”-Ast genau \(D\) Kandidaten, während der “Nein”-Ast das reduzierte Tripel
$$\left(a-D,\ b,\ c\right)$$
mit Summe \(s-D\) zurücklässt.
Das ursprüngliche Tripel ist auf Stufe \(k\) also genau dann schwer, wenn das reduzierte Tripel auf Stufe \(k-1\) schwer ist. Bezeichnet \(E_k(X)\) die Zahl schwerer Tripel mit Summe höchstens \(X\) auf Stufe \(k\), dann gilt
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$$
Der Faktor \(3\) kommt von der Wahl, welcher Teller der übergroße ist.
Sei \(K\) die größte Zahl mit \(2^{K-1}\lt N\le 2^K\). Jedes Tripel im dyadischen Block \(2^{k-1}\lt s\le 2^k\) liefert mindestens \(k\), und jedes schwere Tripel liefert genau eine zusätzliche Frage. Also
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$$
Genau diese Formel wird im Programm ausgewertet.
Nimm \(s=8\). Dann sind \(k=3\) und \(D=4\).
Für das Tripel \((3,3,2)\) sind alle Paar-Summen größer als \(4\):
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
Es liegt also in der schweren Region. Jede Drei-Fragen-Strategie müsste die acht Kandidaten bereits mit der ersten Frage in zwei Zweige von Größe höchstens vier teilen, also eine Teilmenge der Größe genau \(4\) abfragen. Aber kein Teller enthält \(4\) Bohnen. Daher gilt
$$h(3,3,2)=4.$$
Dagegen ist \((5,2,1)\) auf derselben Stufe leicht: Man fragt nach einer Vierer-Teilmenge des Tellers mit fünf Bohnen. Der “Ja”-Ast hat \(4\) Kandidaten, und der “Nein”-Ast hinterlässt \((1,2,1)\) mit Gesamtsumme \(4\), also reichen dort zwei weitere Fragen. Damit ist \(h(5,2,1)=3\).
Die Rekursion sieht man eine Stufe höher bei \((11,3,2)\), wo \(s=16\) und \(D=8\) gilt. Eine Frage nach acht Bohnen der großen Platte lässt entweder genau \(8\) Kandidaten übrig oder das reduzierte Tripel \((3,3,2)\), das bereits schwer ist. Also ist \((11,3,2)\) auf Stufe \(4\) schwer und benötigt \(5\) Fragen.
Die C++, Python- und Java-Implementierungen arbeiten vollständig modulo \(10^9+7\). Zuerst wird der Basisterm aufgebaut, indem die Summen über \(s\) dyadisch gebündelt und
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
mit geschlossenen Formeln für \(\sum s\) und \(\sum s^2\) ausgewertet werden. Danach werden die schweren Regionen \(W_D(X)\) per Inklusion-Exklusion gezählt. Jeder Bestandteil dieser Zählung wird auf wenige Polynombereiche reduziert, sodass keine Schleife über alle Tripel nötig ist.
Zum Schluss memoisiert die Implementierung die rekursiven Zustände \(E_k(X)\). Jeder Zustand benötigt genau eine Zählung innerhalb des Würfels und, falls \(X\gt 2^{k-1}\), genau einen rekursiven Schritt zur vorherigen Stufe. Die Antwort ist Basisterm plus Gesamtzahl schwerer Tripel über alle relevanten Ebenen.
Mit \(K=\lceil\log_2 N\rceil\) gibt es \(O(K)\) dyadische Ebenen, und jeder rekursive Zustand wird nur einmal ausgewertet. Jeder Zustand verwendet lediglich konstante viele modulare Rechenoperationen und geschlossene Summenformeln. Die gesamte Laufzeit ist daher \(O(\log N)\), und auch der Speicherbedarf der Memoisierung ist \(O(\log N)\).
Üç tabakta sırasıyla \(a\), \(b\) ve \(c\) fasulye vardır ve bunlardan tam biri sihirlidir. Her soru yalnızca tek bir tabaktan seçilen bir alt kümeyi yoklayabilir ve cevap sadece evet ya da hayırdır. \(h(a,b,c)\), sihirli fasulyeyi kesin olarak bulmak için gereken en az soru sayısı olsun. İstenen toplam
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
Gerçek giriş boyutunda ne tüm üçlüleri tek tek saymak ne de karar ağaçlarını doğrudan kurmak mümkündür. Bu yüzden çözüm, problemi ikinin kuvvetlerine göre bölünmüş aralıklarda sayım problemine dönüştürür.
\(s=a+b+c\) toplam aday sayısı olsun. Tüm çözüm şu eşik etrafında kurulur:
$$D=2^{k-1}\qquad\text{ve}\qquad 2^{k-1}\lt s\le 2^k.$$
Bu ölçekte \(k\), bilgi kuramından gelen alt sınırdır. Geriye kalan tek soru, verilen bir üçlünün bu sınırı tam yakalayıp yakalamadığı ya da bir fazladan soruya ihtiyaç duyup duymadığıdır.
Sihirli fasulyenin \(s\) farklı yerde olma ihtimali varsa, derinliği \(t\) olan bir evet/hayır karar ağacı en fazla \(2^t\) yaprak ayırabilir. Bu nedenle her strateji için
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil$$
zorunludur. Toplamı \(s\) olan negatif olmayan üçlü sayısı ise stars and bars formülüyle
$$\binom{s+2}{2}$$
olur. Dolayısıyla evrensel taban katkı
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}$$
şeklindedir. \(\lceil\log_2 1\rceil=0\) olduğu için \(s=1\) terimi zaten sıfırdır. Uygulamalar bu toplamı dyadik bloklara \((2^{k-1},2^k]\) ayırır ve
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2}$$
açılımını kullanarak her bloğu \(\sum s\) ve \(\sum s^2\) için kapalı formüllerle hesaplar.
Şimdi \(2^{k-1}\lt s\le 2^k\) olan bir üçlü sabitleyelim ve \(D=2^{k-1}\) diyelim. Eğer tam \(k\) soruda bitirmek istiyorsak, ilk sorudan sonra iki dalda da en fazla \(D\) aday kalmalıdır; çünkü yalnızca \(k-1\) ek evet/hayır cevabı vardır.
İlk soru tek bir tabaktan büyüklüğü \(q\) olan bir alt kümeyi seçsin. O zaman iki dalın boyutları \(q\) ve \(s-q\) olur; dolayısıyla
$$s-D\le q\le D$$
gereklidir. \(0\le a,b,c\le D\) küpünün içinde böyle bir \(q\) ancak en az bir tabakta \(s-D\) kadar fasulye varsa seçilebilir. Demek ki bir üçlü, seviye \(k\)'da en az bir koordinatı bu eşiğe ulaşıyorsa kolay, hiçbir koordinat ulaşmıyorsa zordur.
\(s=a+b+c\) olduğundan \(a\lt s-D\) koşulu \(b+c\gt D\) ile denktir; diğerleri de aynıdır. Bu yüzden küp içindeki zor bölge tam olarak
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D$$
koşullarıyla tanımlanır. Her zor üçlü \(k+1\) soru ister; zor olmayan her üçlü ise alt sınır olan \(k\)'ya ulaşır.
Şunu tanımlayalım:
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
Bu, toplamı en fazla \(X\) olan zor üçlülerin sayısıdır. Bunu saymak için şu üç “kolay” olayı dahil et-çıkar ile kullanırız:
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
Simetri sayesinde
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X)$$
yazılır. Burada \(U_D(X)\) kutunun içindeki tüm üçlüleri, \(A_D(X)\) tek bir kolay olayı, \(B_D(X)\) iki kolay olayın kesişimini ve \(C_D(X)\) üç olayın ortak kesişimini sayar.
En basit terim evren sayımıdır:
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
Kalan terimler de bir çift toplamını veya bir koordinatı sabitleyince tek değişkenli polinom toplamlarına iner. Bu yüzden uygulama tüm üçlüleri dolaşmak yerine yalnızca aritmetik ve ikinci dereceden toplamların kapalı formlarını kullanır.
Şimdi toplamı \(s\le 2D\) olan ama koordinatlarından biri \(D\)'den büyük olan bir üçlü düşünelim. \(s\le 2D\) olduğu için aynı anda en fazla bir koordinat \(D\)'yi aşabilir.
\(a\gt D\) olduğunu varsayalım. Her iki dalı da en fazla \(D\) boyutunda tutmanın tek yolu, ilk soruda bu büyük tabaktan tam \(D\) fasulyelik bir alt kümeyi ayırmaktır. “Evet” dalı böylece tam \(D\) aday bırakır; “hayır” dalı ise
$$\left(a-D,\ b,\ c\right)$$
indirgenmiş üçlüsünü bırakır ve bunun toplamı \(s-D\)'dir.
Dolayısıyla başlangıçtaki üçlü seviye \(k\)'da ancak ve ancak bu indirgenmiş üçlü seviye \(k-1\)'de zorsa zor olur. Toplamı en fazla \(X\) olan seviye-\(k\) zor üçlü sayısına \(E_k(X)\) dersek
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k \end{cases}$$
olur. Buradaki \(3\) katsayısı, büyük olan tabağın hangisi olduğuna karşılık gelir.
\(2^{K-1}\lt N\le 2^K\) olacak şekilde \(K\) seçilsin. \(2^{k-1}\lt s\le 2^k\) bloğundaki her üçlü taban olarak \(k\) katkı yapar ve her zor üçlü bir ek soru daha getirir. Sonuçta
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}$$
elde edilir. Uygulama tam olarak bu formülü hesaplar.
\(s=8\) alalım. O zaman \(k=3\) ve \(D=4\).
\((3,3,2)\) üçlüsünde tüm ikili toplamlar \(4\)'ten büyüktür:
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
Bu yüzden üçlü zor bölgededir. Üç soruluk herhangi bir strateji, ilk soruda sekiz adayı en fazla dörderlik iki dala ayırmak zorundadır; yani sorgulanan alt kümenin boyutu tam \(4\) olmalıdır. Ama hiçbir tabakta \(4\) fasulye yoktur. Demek ki
$$h(3,3,2)=4.$$
Buna karşılık \((5,2,1)\) aynı seviyede kolaydır: beş fasulyeli tabaktan dört elemanlı bir alt küme sorulur. “Evet” dalı \(4\) aday bırakır; “hayır” dalı \((1,2,1)\) üçlüsüne düşer ve toplam \(4\) olduğu için iki ek soru yeterlidir. Dolayısıyla \(h(5,2,1)=3\).
Rekürsiyon bir üst seviyede \((11,3,2)\) ile görünür. Burada \(s=16\) ve \(D=8\)'dir. Büyük tabaktan sekiz fasulyelik bir alt küme sorulduğunda ya tam \(8\) aday kalır ya da zaten zor olduğunu bildiğimiz \((3,3,2)\) indirgenmiş üçlüsü elde edilir. Bu yüzden \((11,3,2)\) dördüncü seviyede zordur ve \(5\) soru ister.
C++, Python ve Java uygulamaları her adımı \(10^9+7\) modunda yürütür. Önce, \(s\) toplamlarını dyadik aralıklara ayırarak taban terimi toplarlar ve
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
ifadesini \(\sum s\) ile \(\sum s^2\) için kapalı formlarla değerlendirirler. Sonra \(W_D(X)\) zor bölge sayımlarını dahil et-çıkar yoluyla hesaplarlar. Bu dahil et-çıkarın her parçası kısa polinom aralık toplamlarına indirildiği için üçlüler üzerinde doğrudan döngü kurulmaz.
Son aşamada uygulama, rekürsif \(E_k(X)\) durumlarını önbelleğe alır. Her durum bir küp içi sayım ve, \(X\gt 2^{k-1}\) ise, bir önceki seviyeye tek bir rekürsif çağrı içerir. Nihai cevap, taban katkı ile tüm seviyelerdeki zor üçlü sayılarının toplamıdır.
\(K=\lceil\log_2 N\rceil\) olmak üzere dyadik seviye sayısı \(O(K)\)'dır ve her rekürsif durum yalnızca bir kez hesaplanır. Her durumda sabit sayıda modüler işlem ve kapalı form toplam kullanıldığı için toplam çalışma süresi \(O(\log N)\), önbellek boyutu da \(O(\log N)\) olur.
Hay tres platos con \(a\), \(b\) y \(c\) judías, y exactamente una de ellas es mágica. Cada pregunta solo puede inspeccionar un subconjunto tomado de un único plato, y la respuesta es sí o no. Sea \(h(a,b,c)\) el número mínimo de preguntas que garantiza identificar la judía mágica. Debemos calcular
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
Un recorrido directo de todas las ternas o de todos los árboles de decisión es inviable para el tamaño real del problema, así que la solución transforma todo en un recuento sobre intervalos diádicos.
Escribamos \(s=a+b+c\) para el número total de posiciones candidatas. Toda la estrategia gira alrededor del umbral
$$D=2^{k-1}\qquad\text{cuando}\qquad 2^{k-1}\lt s\le 2^k.$$
En esa escala, \(k\) es la cota inferior informacional. Luego solo queda decidir si una terna concreta alcanza esa cota o si necesita exactamente una pregunta adicional.
Con \(s\) posibles ubicaciones para la judía mágica, cualquier árbol de decisión sí/no de profundidad \(t\) tiene como máximo \(2^t\) hojas. Por tanto siempre vale
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$$
Para un \(s\) fijo, el número de ternas no negativas \((a,b,c)\) con suma \(s\) es
$$\binom{s+2}{2}.$$
Así obtenemos la contribución base universal
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$$
Como \(\lceil\log_2 1\rceil=0\), el caso \(s=1\) desaparece por sí solo. Las implementaciones agrupan esta suma por bloques diádicos \((2^{k-1},2^k]\) y expanden
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2},$$
de modo que cada bloque se evalúa con fórmulas cerradas para \(\sum s\) y \(\sum s^2\).
Fijemos una terna con \(2^{k-1}\lt s\le 2^k\) y pongamos \(D=2^{k-1}\). Si queremos terminar en exactamente \(k\) preguntas, después de la primera pregunta ambas ramas deben dejar como máximo \(D\) candidatos, porque solo quedan \(k-1\) respuestas sí/no.
Si la primera pregunta elige un subconjunto de tamaño \(q\) dentro de un plato, entonces los dos tamaños de rama son \(q\) y \(s-q\). Necesariamente
$$s-D\le q\le D.$$
Dentro del cubo \(0\le a,b,c\le D\), ese \(q\) solo puede salir de un plato que tenga al menos \(s-D\) judías. Por tanto, una terna es fácil en el nivel \(k\) si alguna coordenada alcanza ese umbral, y es difícil si ninguna lo hace.
Como \(s=a+b+c\), la condición \(a\lt s-D\) equivale a \(b+c\gt D\), y análogamente para las otras coordenadas. Así, dentro del cubo, la dificultad queda caracterizada exactamente por
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$$
Toda terna difícil necesita \(k+1\) preguntas; toda terna no difícil alcanza la cota \(k\).
Definimos
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
Este es el número de ternas difíciles con suma a lo sumo \(X\). Para contarlo, se usa inclusión-exclusión sobre los tres eventos “fáciles”
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
Por simetría,
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$$
donde \(U_D(X)\) cuenta todas las ternas del cubo con suma a lo sumo \(X\), \(A_D(X)\) cuenta un evento fácil, \(B_D(X)\) cuenta la intersección de dos de ellos y \(C_D(X)\) la intersección de los tres.
El término más simple es el universo:
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
Los otros términos también se reducen a sumas polinómicas de una sola variable al fijar una suma de pares o una coordenada. Por eso la implementación solo usa fórmulas cerradas para progresiones aritméticas y cuadráticas, sin iterar explícitamente sobre todas las ternas.
Consideremos ahora una terna con \(s\le 2D\) pero con una coordenada mayor que \(D\). Como \(s\le 2D\), como mucho una coordenada puede superar ese umbral.
Supongamos \(a\gt D\). Para que ambas ramas queden de tamaño a lo sumo \(D\), la primera pregunta debe aislar exactamente \(D\) judías de ese plato grande. La rama “sí” deja exactamente \(D\) candidatos, y la rama “no” reduce el problema a
$$\left(a-D,\ b,\ c\right),$$
cuya suma es \(s-D\).
Así, la terna original es difícil en el nivel \(k\) si y solo si la terna reducida es difícil en el nivel \(k-1\). Si \(E_k(X)\) denota el número de ternas difíciles con suma a lo sumo \(X\) en el nivel \(k\), entonces
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$$
El factor \(3\) corresponde a cuál de los tres platos es el que excede \(D\).
Sea \(K\) el mayor entero tal que \(2^{K-1}\lt N\le 2^K\). Toda terna en el bloque diádico \(2^{k-1}\lt s\le 2^k\) aporta al menos \(k\), y toda terna difícil aporta una pregunta extra. Por tanto
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$$
Esa es exactamente la expresión evaluada por la implementación.
Tomemos \(s=8\). Entonces \(k=3\) y \(D=4\).
Para la terna \((3,3,2)\), las tres sumas de pares son mayores que \(4\):
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
Luego está en la región difícil. Cualquier estrategia de tres preguntas necesitaría que la primera pregunta dividiera los ocho candidatos en dos ramas de tamaño a lo sumo cuatro, lo cual obliga a consultar un subconjunto de tamaño exactamente \(4\). Pero ningún plato contiene \(4\) judías. Por ello
$$h(3,3,2)=4.$$
En cambio, \((5,2,1)\) es fácil en el mismo nivel: se pregunta por un subconjunto de cuatro judías del plato que tiene cinco. La rama “sí” deja \(4\) candidatos, y la rama “no” deja \((1,2,1)\), cuya suma es \(4\), así que bastan dos preguntas más. Por tanto \(h(5,2,1)=3\).
La recursión se ve un nivel más arriba con \((11,3,2)\), donde \(s=16\) y \(D=8\). Preguntar por un subconjunto de ocho judías del plato grande deja o bien un bloque de tamaño \(8\) o bien la terna reducida \((3,3,2)\), que ya sabemos que es difícil. Así, \((11,3,2)\) es difícil en el nivel \(4\) y requiere \(5\) preguntas.
Las implementaciones en C++, Python y Java trabajan siempre módulo \(10^9+7\). Primero acumulan el término base agrupando los valores de \(s\) por intervalos diádicos y evaluando
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
mediante fórmulas cerradas para \(\sum s\) y \(\sum s^2\). Después calculan los recuentos \(W_D(X)\) por inclusión-exclusión. Cada pieza de esa inclusión-exclusión se reduce a unas pocas sumas polinómicas sobre intervalos, así que no hace falta iterar sobre todas las ternas.
Finalmente, la implementación memoriza los estados recursivos \(E_k(X)\). Cada estado realiza un recuento dentro del cubo y, cuando \(X\gt 2^{k-1}\), una sola llamada recursiva al nivel anterior. La respuesta final es el término base más el número total de ternas difíciles en todos los niveles relevantes.
Si \(K=\lceil\log_2 N\rceil\), hay \(O(K)\) niveles diádicos y cada estado recursivo se evalúa una sola vez. Cada estado usa solo aritmética modular de tiempo constante y fórmulas cerradas, así que el tiempo total es \(O(\log N)\). La memoria de la memoización también es \(O(\log N)\).
三只盘子里分别有 \(a\)、\(b\)、\(c\) 颗豆子，并且恰好有一颗是魔法豆。每次提问只能在单个盘子内选择一个子集，答案只有“是”或“否”。记 \(h(a,b,c)\) 为无论魔法豆在哪里，都能保证找出的最少提问次数。目标是计算
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
对所有三元组直接建决策树显然不可行，因此解法把问题改写成按二的幂分层的计数问题。
设
$$s=a+b+c$$
为当前候选位置总数。整个分析围绕阈值
$$D=2^{k-1}\qquad\text{其中}\qquad 2^{k-1}\lt s\le 2^k$$
展开。在这个尺度下，\(k\) 是信息论下界，而关键在于判断某个三元组是否恰好达到这个下界，还是必须多问一次。
如果魔法豆有 \(s\) 个可能位置，那么深度为 \(t\) 的是/否决策树最多只有 \(2^t\) 个叶子，因此一定有
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$$
对固定的 \(s\)，满足 \(a+b+c=s\) 的非负三元组数量是经典的 stars and bars 结果
$$\binom{s+2}{2}.$$
于是所有三元组都会贡献一个通用基线
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$$
因为 \(\lceil\log_2 1\rceil=0\)，所以 \(s=1\) 这一层自然没有贡献。实现中把 \(s\) 按区间 \((2^{k-1},2^k]\) 分组，并把
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2}$$
展开成关于 \(s\) 的二次多项式，这样每一组都能通过 \(\sum s\) 和 \(\sum s^2\) 的闭式公式一次算完。
固定一个满足 \(2^{k-1}\lt s\le 2^k\) 的三元组，并令 \(D=2^{k-1}\)。如果希望总共只用 \(k\) 次提问，那么第一次提问之后，无论答案是“是”还是“否”，剩余候选数都必须不超过 \(D\)，因为后面只剩 \(k-1\) 次是/否机会。
设第一次在某个盘子里询问一个大小为 \(q\) 的子集，那么两条分支的候选数分别是 \(q\) 和 \(s-q\)。因此必须满足
$$s-D\le q\le D.$$
如果三只盘子的豆子数都不超过 \(D\)，那么这样的 \(q\) 只有在某个盘子至少含有 \(s-D\) 颗豆子时才可能选出来。所以在第 \(k\) 层里，只要有某个坐标达到这个门槛，三元组就是容易的；如果三个坐标都达不到，它就是困难的。
由于 \(s=a+b+c\)，条件 \(a\lt s-D\) 等价于 \(b+c\gt D\)，另外两个坐标同理。因此在立方体 \(0\le a,b,c\le D\) 内，困难三元组恰好满足
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$$
这样的三元组需要 \(k+1\) 次提问；其余三元组都能用恰好 \(k\) 次完成。
定义
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
这表示总和不超过 \(X\) 的困难三元组个数。为了计算它，对三个“容易事件”使用容斥：
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
利用对称性可写成
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$$
其中 \(U_D(X)\) 表示盒子里所有总和不超过 \(X\) 的三元组，\(A_D(X)\) 表示一个容易事件，\(B_D(X)\) 表示两个容易事件的交集，\(C_D(X)\) 表示三个容易事件的交集。
最直接的一项是全集计数：
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
其余三项在固定某个坐标或某个两数和之后，也都能化成单变量多项式求和。因此实现并不枚举三元组，而是把所有计数都压缩成若干个一维区间上的闭式和。
现在考虑总数 \(s\le 2D\) 但某个坐标大于 \(D\) 的情况。因为总和最多只有 \(2D\)，所以至多只有一个坐标会超过 \(D\)。
假设 \(a\gt D\)。若想让第一次提问后的两条分支都不超过 \(D\)，唯一合理的做法是在这个大盘子里挑出恰好 \(D\) 颗豆子来询问。这样“是”分支正好剩 \(D\) 个候选，而“否”分支会把问题缩减成
$$\left(a-D,\ b,\ c\right),$$
其总和变为 \(s-D\)。
所以原三元组在第 \(k\) 层是困难的，当且仅当这个缩减后的三元组在第 \(k-1\) 层也是困难的。若记 \(E_k(X)\) 为第 \(k\) 层中总和不超过 \(X\) 的困难三元组数，则有递推
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$$
这里的系数 \(3\) 对应于“哪一个盘子超出了 \(D\)”这三种对称选择。
设 \(K\) 满足 \(2^{K-1}\lt N\le 2^K\)。对每个 dyadic 区间 \(2^{k-1}\lt s\le 2^k\)，所有三元组至少贡献 \(k\)，而困难三元组再额外贡献 \(1\)。因此
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$$
这正是实现所计算的数学表达式。
先看 \(s=8\)。此时 \(k=3\)，\(D=4\)。
对三元组 \((3,3,2)\)，三个两数和都大于 \(4\)：
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
所以它落在困难区域里。若想用三次提问解决，第一次提问必须把 8 个候选切成两个不超过 4 的分支，这迫使被询问的子集大小必须正好是 \(4\)。但没有任何一个盘子里有 \(4\) 颗豆子，因此做不到，于是
$$h(3,3,2)=4.$$
相反，\((5,2,1)\) 在同一层就是容易的：在有 5 颗豆子的盘子里询问一个大小为 4 的子集。“是”分支留下 \(4\) 个候选；“否”分支留下 \((1,2,1)\)，其总数是 \(4\)，再用两次提问即可。所以 \(h(5,2,1)=3\)。
递归思想在更高一层的 \((11,3,2)\) 上尤其清楚。这里 \(s=16\)，\(D=8\)。第一次从大盘子里问 8 颗豆子后，要么留下恰好 \(8\) 个候选，要么落到缩减后的 \((3,3,2)\)，而它已经被证明是困难的。因此 \((11,3,2)\) 在第 4 层仍然困难，需要 \(5\) 次提问。
C++、Python 和 Java 实现始终在模 \(10^9+7\) 下工作。首先，它们按 dyadic 区间汇总基线项，并把
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
转换为 \(\sum s\) 与 \(\sum s^2\) 的闭式求和。然后，通过容斥计算 \(W_D(X)\) 这样的困难区域计数。容斥中的每一部分都被化成少量一维多项式区间和，因此完全不需要显式枚举所有三元组。
最后，实现对递归状态 \(E_k(X)\) 做记忆化。每个状态只包含一次立方体内部计数，以及在 \(X\gt 2^{k-1}\) 时对上一层的单次递归调用。最终答案就是基线项加上所有相关层级中困难三元组的总数。
令 \(K=\lceil\log_2 N\rceil\)。dyadic 层数是 \(O(K)\)，每个递归状态只会被计算一次。每个状态都只做常数次模运算和闭式求和，所以总时间复杂度为 \(O(\log N)\)，记忆化表的空间复杂度也是 \(O(\log N)\)。
Есть три тарелки с \(a\), \(b\) и \(c\) бобами, и ровно один боб является магическим. Каждый вопрос может проверять только подмножество, взятое с одной тарелки, а ответ бывает лишь да или нет. Обозначим через \(h(a,b,c)\) минимальное число таких вопросов, которое гарантированно находит магический боб. Требуется вычислить
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
Полный перебор троек или непосредственное построение деревьев решений для настоящего входа невозможны, поэтому решение сводит задачу к подсчётам по диадическим слоям.
Пусть
$$s=a+b+c$$
обозначает общее число кандидатных мест. Вся конструкция основана на пороге
$$D=2^{k-1}\qquad\text{при}\qquad 2^{k-1}\lt s\le 2^k.$$
На этом уровне \(k\) является информационной нижней границей, а дальше нужно понять только одно: достигает ли данная тройка этой границы или требует ещё одного вопроса.
Если у магического боба есть \(s\) возможных позиций, то дерево решений глубины \(t\) с ответами да/нет имеет не более \(2^t\) листьев. Поэтому всегда
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$$
Для фиксированного \(s\) число неотрицательных троек \((a,b,c)\) с суммой \(s\) равно
$$\binom{s+2}{2}.$$
Значит универсальный базовый вклад имеет вид
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$$
Поскольку \(\lceil\log_2 1\rceil=0\), случай \(s=1\) исчезает сам. Реализации группируют эту сумму по диадическим блокам \((2^{k-1},2^k]\) и раскладывают
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2},$$
после чего каждый блок вычисляется через закрытые формулы для \(\sum s\) и \(\sum s^2\).
Зафиксируем тройку с \(2^{k-1}\lt s\le 2^k\) и положим \(D=2^{k-1}\). Если мы хотим уложиться ровно в \(k\) вопросов, то после первого вопроса в каждой ветви должно остаться не более \(D\) кандидатов, потому что остаётся только \(k-1\) двоичных ответа.
Пусть первый вопрос выбирает подмножество размера \(q\) на одной тарелке. Тогда размеры двух ветвей равны \(q\) и \(s-q\), следовательно необходимо
$$s-D\le q\le D.$$
Внутри куба \(0\le a,b,c\le D\) такой \(q\) можно взять лишь с тарелки, на которой не меньше \(s-D\) бобов. Значит, тройка на уровне \(k\) является лёгкой, если хотя бы одна координата достигает этого порога, и трудной, если не достигает ни одна.
Так как \(s=a+b+c\), условие \(a\lt s-D\) эквивалентно \(b+c\gt D\), и аналогично для остальных координат. Поэтому внутри куба трудность описывается точно системой
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$$
Каждая трудная тройка требует \(k+1\) вопросов, а каждая нетрудная достигает нижней границы \(k\).
Определим
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
Это число трудных троек с суммой не больше \(X\). Для подсчёта используется включение-исключение по трём “лёгким” событиям
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
По симметрии имеем
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$$
где \(U_D(X)\) считает все тройки в кубе с суммой не больше \(X\), \(A_D(X)\) считает одно лёгкое событие, \(B_D(X)\) — пересечение двух таких событий, а \(C_D(X)\) — пересечение всех трёх.
Самый простой член — это полный объём:
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
Остальные члены после фиксации суммы пары или одной координаты тоже сводятся к одномерным полиномиальным суммам. Поэтому реализация нигде не перебирает все тройки явно, а использует только закрытые формулы для линейных и квадратичных сумм.
Теперь рассмотрим тройку с \(s\le 2D\), но с одной координатой, большей \(D\). Поскольку \(s\le 2D\), превышать порог может не более одной координаты.
Пусть \(a\gt D\). Чтобы обе ветви после первого вопроса имели размер не больше \(D\), нужно выделить из этой большой тарелки подмножество ровно из \(D\) бобов. Тогда ветвь “да” оставляет ровно \(D\) кандидатов, а ветвь “нет” приводит к уменьшенной тройке
$$\left(a-D,\ b,\ c\right),$$
чья сумма равна \(s-D\).
Значит, исходная тройка трудна на уровне \(k\) тогда и только тогда, когда уменьшенная тройка трудна на уровне \(k-1\). Если \(E_k(X)\) обозначает число трудных троек с суммой не больше \(X\) на уровне \(k\), то
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$$
Множитель \(3\) отражает выбор, какая именно тарелка оказалась слишком большой.
Пусть \(K\) таково, что \(2^{K-1}\lt N\le 2^K\). Каждая тройка в диадическом блоке \(2^{k-1}\lt s\le 2^k\) даёт базовый вклад \(k\), а каждая трудная тройка добавляет ещё один вопрос. Поэтому
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$$
Именно это выражение и вычисляется в программе.
Возьмём \(s=8\). Тогда \(k=3\) и \(D=4\).
Для тройки \((3,3,2)\) все попарные суммы больше \(4\):
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
Значит, она лежит в трудной области. Любая стратегия из трёх вопросов должна уже первым вопросом разбить восемь кандидатов на две ветви размером не более четырёх, а это требует подмножества размера ровно \(4\). Но ни на одной тарелке нет \(4\) бобов. Следовательно,
$$h(3,3,2)=4.$$
Напротив, \((5,2,1)\) на том же уровне легко: можно спросить про подмножество из четырёх бобов на тарелке с пятью. Ветвь “да” оставит \(4\) кандидатов, а ветвь “нет” оставит \((1,2,1)\) с суммой \(4\), и там хватит ещё двух вопросов. Итак, \(h(5,2,1)=3\).
Рекурсивная идея особенно ясно видна на \((11,3,2)\), где \(s=16\) и \(D=8\). Вопрос про восемь бобов на большой тарелке приводит либо к блоку размера \(8\), либо к уменьшенной тройке \((3,3,2)\), уже известной как трудная. Поэтому \((11,3,2)\) трудна на уровне \(4\) и требует \(5\) вопросов.
Реализации на C++, Python и Java целиком работают по модулю \(10^9+7\). Сначала они суммируют базовый член, группируя значения \(s\) по диадическим диапазонам и вычисляя
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
через закрытые формулы для \(\sum s\) и \(\sum s^2\). Затем они считают трудные области \(W_D(X)\) методом включения-исключения. Каждая составляющая этого подсчёта сводится к короткому набору полиномиальных сумм по отрезкам, так что прямой перебор троек не нужен.
После этого реализация мемоизирует рекурсивные состояния \(E_k(X)\). Каждое состояние выполняет один подсчёт внутри куба и, если \(X\gt 2^{k-1}\), один рекурсивный переход к предыдущему уровню. Итоговый ответ равен базовому вкладу плюс числу всех трудных троек на релевантных уровнях.
Если \(K=\lceil\log_2 N\rceil\), то число диадических уровней равно \(O(K)\), и каждое рекурсивное состояние вычисляется только один раз. Внутри состояния используются лишь константное число модульных операций и закрытые формулы, поэтому общее время равно \(O(\log N)\). Память для таблицы мемоизации также составляет \(O(\log N)\).
لدينا ثلاثة أطباق تحتوي على \(a\) و\(b\) و\(c\) حبّة، ويوجد حبّة سحرية واحدة فقط. كل سؤال يمكنه فحص مجموعة جزئية مأخوذة من طبق واحد فقط، والجواب يكون نعم أو لا. نرمز بـ \(h(a,b,c)\) إلى أقل عدد من هذه الأسئلة اللازمة لضمان تحديد الحبّة السحرية. والمطلوب حساب
$$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$$
العدّ المباشر لكل الثلاثيات أو بناء أشجار القرار مباشرة غير ممكن للحجم الحقيقي للمدخل، لذلك يعيد الحل صياغة المسألة على شكل عدّ عبر مستويات ثنائية الأساس.
لنكتب
$$s=a+b+c$$
ليكون عدد المواقع المرشحة الكلي. الفكرة كلها تتمحور حول العتبة
$$D=2^{k-1}\qquad\text{عندما}\qquad 2^{k-1}\lt s\le 2^k.$$
عند هذا المستوى يكون \(k\) هو الحد الأدنى المعلوماتي، ثم يبقى أن نعرف هل تحقق الثلاثية هذا الحد بالضبط أم تحتاج سؤالاً إضافياً واحداً.
إذا كان للحبّة السحرية \(s\) مواقع ممكنة، فإن شجرة قرارات نعم/لا بعمق \(t\) لا يمكن أن تملك أكثر من \(2^t\) ورقة. لذلك دائماً
$$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$$
ولقيمة ثابتة من \(s\)، فإن عدد الثلاثيات غير السالبة \((a,b,c)\) التي مجموعها \(s\) يساوي
$$\binom{s+2}{2}.$$
إذن نحصل على مساهمة أساسية عامة
$$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$$
وبما أن \(\lceil\log_2 1\rceil=0\)، فإن حد \(s=1\) يختفي تلقائياً. تقوم التطبيقات بتجميع هذا المجموع على كتل ثنائية من الشكل \((2^{k-1},2^k]\)، ثم تكتب
$$\binom{s+2}{2}=\frac{s^2+3s+2}{2},$$
وبذلك يمكن تقييم كل كتلة باستخدام الصيغ المغلقة لـ \(\sum s\) و\(\sum s^2\).
ثبّت ثلاثية تحقق \(2^{k-1}\lt s\le 2^k\)، وضع \(D=2^{k-1}\). إذا أردنا الانتهاء في \(k\) أسئلة بالضبط، فيجب أن يترك السؤال الأول في كلا الفرعين عدداً لا يزيد على \(D\) من المرشحين، لأننا لا نملك بعده إلا \(k-1\) إجابة ثنائية.
إذا اختار السؤال الأول مجموعة جزئية حجمها \(q\) من طبق واحد، فإن حجمي الفرعين سيكونان \(q\) و\(s-q\). لذلك يلزم
$$s-D\le q\le D.$$
داخل المكعب \(0\le a,b,c\le D\)، لا يمكن اختيار مثل هذا \(q\) إلا من طبق يحتوي على الأقل \(s-D\) حبّة. إذن تكون الثلاثية سهلة في المستوى \(k\) إذا وصلت إحدى الإحداثيات إلى هذا الحد، وتكون صعبة إذا لم تصل أي إحداثية إليه.
وبما أن \(s=a+b+c\)، فإن الشرط \(a\lt s-D\) يكافئ \(b+c\gt D\)، وبالمثل لباقي الإحداثيات. لذا فإن الصعوبة داخل المكعب توصف تماماً بالشروط
$$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$$
كل ثلاثية صعبة تحتاج \(k+1\) سؤالاً، وكل ثلاثية غير صعبة تحقق الحد الأدنى \(k\).
نعرّف
$$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$$
وهذا هو عدد الثلاثيات الصعبة التي لا يزيد مجموعها على \(X\). ولحسابه نستخدم مبدأ الشمول والاستبعاد على الأحداث “السهلة” الثلاثة
$$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$$
وبفضل التناظر نحصل على
$$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$$
حيث إن \(U_D(X)\) يعدّ جميع الثلاثيات داخل الصندوق ومجموعها لا يتجاوز \(X\)، و\(A_D(X)\) يعدّ حدثاً سهلاً واحداً، و\(B_D(X)\) يعدّ تقاطع حدثين، و\(C_D(X)\) يعدّ تقاطع الأحداث الثلاثة كلها.
أبسط حد هو عدّ الفضاء كله:
$$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$$
أما الحدود الأخرى فتتحول أيضاً، بعد تثبيت مجموع زوج أو تثبيت إحداثية واحدة، إلى مجاميع كثيرات حدود في متغير واحد. لهذا السبب لا تقوم التطبيقات بعدّ كل الثلاثيات صراحة، بل تعتمد فقط على صيغ مغلقة لمجاميع خطية وتربيعية.
لننظر الآن إلى ثلاثية مجموعها \(s\le 2D\) لكن إحدى إحداثياتها أكبر من \(D\). بما أن \(s\le 2D\)، فلا يمكن أن تتجاوز العتبة إلا إحداثية واحدة على الأكثر.
افترض أن \(a\gt D\). وحتى يبقى كل فرع بحجم لا يتجاوز \(D\)، يجب أن يعزل السؤال الأول بالضبط \(D\) حبّة من ذلك الطبق الكبير. عندئذٍ يترك فرع “نعم” عدداً مساوياً تماماً لـ \(D\) من المرشحين، بينما يترك فرع “لا” الثلاثية المختزلة
$$\left(a-D,\ b,\ c\right),$$
ويصبح مجموعها \(s-D\).
إذن تكون الثلاثية الأصلية صعبة في المستوى \(k\) إذا وفقط إذا كانت الثلاثية المختزلة صعبة في المستوى \(k-1\). وإذا رمزنا بـ \(E_k(X)\) إلى عدد الثلاثيات الصعبة ذات المجموع الذي لا يتجاوز \(X\) في المستوى \(k\)، فإن
$$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$$
ومعامل \(3\) يأتي من اختيار أيّ طبق هو الذي تجاوز العتبة.
ليكن \(K\) بحيث \(2^{K-1}\lt N\le 2^K\). كل ثلاثية في الكتلة الثنائية \(2^{k-1}\lt s\le 2^k\) تساهم أساساً بمقدار \(k\)، وكل ثلاثية صعبة تضيف سؤالاً واحداً آخر. لذلك
$$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$$
وهذه هي الصيغة نفسها التي تنفذها البرامج.
خذ \(s=8\). عندها \(k=3\) و\(D=4\).
بالنسبة إلى الثلاثية \((3,3,2)\)، فإن جميع المجاميع الثنائية أكبر من \(4\):
$$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$$
إذن هي تقع في المنطقة الصعبة. أي استراتيجية من ثلاث أسئلة يجب أن تقسّم المرشحين الثمانية في السؤال الأول إلى فرعين لا يزيد كل منهما على أربعة، وهذا يفرض أن تكون المجموعة المسؤولة عنها ذات حجم \(4\) تماماً. لكن لا يوجد طبق يحوي \(4\) حبّات. لذلك
$$h(3,3,2)=4.$$
أما \((5,2,1)\) فهي سهلة في المستوى نفسه: نسأل عن مجموعة حجمها أربع حبّات من الطبق الذي يحوي خمساً. فرع “نعم” يترك \(4\) مرشحين، وفرع “لا” يترك \((1,2,1)\) ومجموعه \(4\)، وعندها تكفي سؤالان إضافيان. إذن \(h(5,2,1)=3\).
وتظهر الفكرة العودية بوضوح في \((11,3,2)\)، حيث \(s=16\) و\(D=8\). سؤال عن مجموعة من ثماني حبّات من الطبق الكبير يترك إما كتلة حجمها \(8\) أو الثلاثية المختزلة \((3,3,2)\) التي نعرف أنها صعبة. لذلك تكون \((11,3,2)\) صعبة في المستوى الرابع وتحتاج إلى \(5\) أسئلة.
تعمل تطبيقات C++ وPython وJava بالكامل بترديد \(10^9+7\). أولاً تجمع الحد الأساسي عبر تقسيم قيم \(s\) إلى مجالات ثنائية وتقييم
$$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$$
باستخدام الصيغ المغلقة لـ \(\sum s\) و\(\sum s^2\). ثم تحسب المناطق الصعبة \(W_D(X)\) بمبدأ الشمول والاستبعاد. وكل جزء من هذا الحساب يُختزل إلى عدد قليل من المجاميع كثيرة الحدود على فترات، لذلك لا توجد أي حاجة إلى المرور على جميع الثلاثيات واحدةً واحدة.
بعد ذلك تستخدم التنفيذات الحفظ بالتذكّر للحالات العودية \(E_k(X)\). كل حالة تجري عدّاً واحداً داخل المكعب، وإذا كان \(X\gt 2^{k-1}\) فإنها تستدعي المستوى السابق مرة واحدة فقط. الجواب النهائي هو الحد الأساسي مضافاً إليه عدد الثلاثيات الصعبة عبر كل المستويات المطلوبة.
إذا كان \(K=\lceil\log_2 N\rceil\)، فإن عدد المستويات الثنائية هو \(O(K)\)، وكل حالة عودية تُحسب مرة واحدة فقط. وبما أن كل حالة تستخدم عدداً ثابتاً من العمليات المعيارية والصيغ المغلقة، فإن الزمن الكلي يساوي \(O(\log N)\). أما الذاكرة المطلوبة لجدول الحفظ بالتذكّر فهي أيضاً \(O(\log N)\).