Problem 716 asks for a quantity \(C(h,w)\) attached to an \(h\times w\) grid graph. The C++, Python, and Java implementations do not enumerate graph configurations or traverse the grid directly. Instead, they evaluate a compact closed formula modulo \(10^9+7\).
That is the key mathematical fact visible in the implementations: once \(h\) and \(w\) are known, the whole problem collapses to a symmetric combination of \(2^h\), \(2^w\), \(2^{h+w}\), and a few linear terms in \(h\) and \(w\). So the real work is not graph search but safe modular evaluation of that formula for very large dimensions.
Let \(M=10^9+7\). The implementations compute \(C(h,w)\) as
$$C(h,w)=T_0+T_1+T_2+T_3,$$
with
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
The required answer is \(C(h,w)\bmod M\).
The only non-polynomial parts are the three powers \(2^h\), \(2^w\), and \(2^{h+w}\). It is convenient to write
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
So the formula is controlled by just three exponential values and a few coefficients that are linear or bilinear in \(h\) and \(w\). This is why the solver never needs to materialize the graph itself.
Each term has a distinct role in the final expression:
$$T_0=9P_{h+w}$$
is the main doubly-exponential contribution tied to the full rectangle.
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
are two matching correction terms. One is weighted by \(2^h\), the other by \(2^w\), so they exchange roles when the rectangle is rotated.
Finally,
$$T_3=2hw+10h+10w+10$$
is purely polynomial. It balances the expression after the exponential pieces have been combined.
Grouping the terms differently gives
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1).$$
This form makes two structural facts obvious.
First, the expression is symmetric under \(h\leftrightarrow w\), exactly what one expects from an \(h\times w\) rectangle whose horizontal and vertical directions are interchangeable.
Second, the bilinear factor \(2hw\) appears in all nonconstant pieces except the leading \(9P_{h+w}\). So the implemented formula combines an area-like term, two one-direction correction terms, and one constant-linear remainder.
Because \(h\) and \(w\) are large, the implementations never form the raw integer \(C(h,w)\). Instead they reduce every building block modulo \(M\).
Define
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
and let
$$Q_e\equiv 2^e \pmod M.$$
Then the whole computation becomes
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M.$$
If an intermediate coefficient is negative before reduction, it is normalized back into the interval \([0,M-1]\). That keeps every multiplication and addition safe.
The smallest built-in checkpoint is \((h,w)=(3,3)\). Here
$$2^3=8,\qquad 2^{3+3}=64.$$
Now evaluate the four pieces:
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
Therefore
$$C(3,3)=576-128-128+88=408,$$
which matches the implementation's checkpoint exactly. A second check gives \(C(3,6)=4696\), again agreeing with the program.
The C++, Python, and Java implementations all follow the same pipeline. First they reduce the product \(hw\) modulo \(M\). Next they compute \(2^h\), \(2^w\), and \(2^{h+w}\) using fast exponentiation, so the cost depends only on the bit-length of the exponents.
After that, the implementation forms the two signed coefficients \(2hw-8w-10\) and \(2hw-8h-10\), normalizes them modulo \(M\), multiplies them by the corresponding powers of two, adds the polynomial remainder \(2hw+10h+10w+10\), and finally reduces the sum modulo \(M\). The C++, Python, and Java implementations differ only in language mechanics; mathematically they perform the same four-term evaluation.
The work outside exponentiation is constant-time modular arithmetic. The only logarithmic part is computing \(2^h\), \(2^w\), and \(2^{h+w}\), which costs \(O(\log h+\log w+\log(h+w))\) time. Since \(\log(h+w)\) dominates up to constants, the overall complexity is \(O(\log(h+w))\) time and \(O(1)\) extra memory.
Problem 716 verlangt einen Wert \(C(h,w)\), der zu einem \(h\times w\)-Gittergraphen gehört. Die C++-, Python- und Java-Implementierungen erzeugen dabei keine Graphzustände und laufen nicht über das Gitter. Stattdessen werten sie direkt eine geschlossene Formel modulo \(10^9+7\) aus.
Der mathematische Kern ist also bereits in einer kompakten algebraischen Form enthalten. Sobald \(h\) und \(w\) feststehen, bleibt nur noch eine symmetrische Kombination aus \(2^h\), \(2^w\), \(2^{h+w}\) und einigen linearen Termen in \(h\) und \(w\). Genau deshalb ist das Verfahren auch für sehr große Dimensionen schnell.
Sei \(M=10^9+7\). Die Implementierungen berechnen
$$C(h,w)=T_0+T_1+T_2+T_3,$$
wobei
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
Gesucht ist also \(C(h,w)\bmod M\).
Die einzigen nichtpolynomiellen Bausteine sind \(2^h\), \(2^w\) und \(2^{h+w}\). Zweckmäßig ist die Schreibweise
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
Damit hängt die ganze Formel nur von drei Potenzwerten und einigen linearen beziehungsweise bilinearen Koeffizienten in \(h\) und \(w\) ab. Das erklärt, warum keinerlei Graphstruktur explizit gespeichert werden muss.
Jeder Summand erfüllt eine eigene Funktion:
$$T_0=9P_{h+w}$$
ist der führende Beitrag mit beiden Dimensionen zugleich.
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
sind zwei zueinander duale Korrekturterme. Einer ist mit \(2^h\), der andere mit \(2^w\) gewichtet; bei Vertauschung der Achsen tauschen sie daher ihre Rollen.
Schließlich ist
$$T_3=2hw+10h+10w+10$$
rein polynomial und gleicht die Gesamtformel nach dem Zusammenfassen der exponentiellen Teile aus.
Anders gruppiert erhält man
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1).$$
Daran erkennt man sofort zwei Dinge.
Erstens ist die Formel invariant unter \(h\leftrightarrow w\). Das passt genau zur Symmetrie eines rechteckigen Gitters, bei dem horizontale und vertikale Richtung austauschbar sind.
Zweitens tritt der Flächenfaktor \(2hw\) in allen nichtkonstanten Anteilen außer dem führenden \(9P_{h+w}\) auf. Die Implementierung kombiniert also einen flächenartigen Hauptbeitrag, zwei richtungsgebundene Korrekturen und einen linearen Restterm.
Da \(h\) und \(w\) groß sind, wird der rohe Integerwert nie vollständig aufgebaut. Stattdessen reduziert die Implementierung jeden Baustein sofort modulo \(M\).
Definiere
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
und
$$Q_e\equiv 2^e \pmod M.$$
Dann reduziert sich die Rechnung auf
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M.$$
Falls ein Zwischenkoeffizient vor der Reduktion negativ ist, wird er in den Bereich \([0,M-1]\) zurücknormalisiert. So bleiben alle Multiplikationen und Additionen wohldefiniert.
Der kleinste eingebaute Prüfwert ist \((h,w)=(3,3)\). Dann gilt
$$2^3=8,\qquad 2^{3+3}=64.$$
Nun berechnen wir die vier Summanden:
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
Damit folgt
$$C(3,3)=576-128-128+88=408,$$
genau wie im Kontrollwert der Implementierung. Ein zweiter Prüfpunkt liefert \(C(3,6)=4696\).
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Abfolge. Zuerst wird das Produkt \(hw\) modulo \(M\) gebildet. Danach werden \(2^h\), \(2^w\) und \(2^{h+w}\) per schneller Exponentiation berechnet, sodass die Laufzeit nur von der Bitlänge der Exponenten abhängt.
Anschließend bildet die Implementierung die beiden vorzeichenbehafteten Koeffizienten \(2hw-8w-10\) und \(2hw-8h-10\), normalisiert sie modulo \(M\), multipliziert sie mit den passenden Zweierpotenzen, addiert den polynomialen Rest \(2hw+10h+10w+10\) und reduziert die Gesamtsumme nochmals modulo \(M\). Sprachspezifisch unterscheiden sich nur die Integer-Details; mathematisch ist es in allen drei Sprachen dieselbe Vier-Term-Auswertung.
Außerhalb der Potenzberechnung ist nur konstante modulare Arithmetik nötig. Die drei Potenzen \(2^h\), \(2^w\) und \(2^{h+w}\) kosten zusammen \(O(\log h+\log w+\log(h+w))\) Zeit. Bis auf konstante Faktoren ist das \(O(\log(h+w))\) Zeit bei \(O(1)\) Zusatzspeicher.
Problem 716, \(h\times w\) boyutlu bir ızgara grafına bağlı \(C(h,w)\) değerini istiyor. C++, Python ve Java implementasyonları bu değeri bulmak için graf üzerindeki durumları tek tek saymıyor ve ızgarayı dolaşmıyor. Bunun yerine doğrudan \(10^9+7\) modunda kapalı bir formülü değerlendiriyor.
Dolayısıyla görünen matematiksel içerik zaten oldukça sıkıştırılmış durumda. \(h\) ve \(w\) verildiğinde problem, \(2^h\), \(2^w\), \(2^{h+w}\) ve birkaç doğrusal terimin simetrik bir birleşimine indirgeniyor. Büyük girişlerde hızın kaynağı da burada yatıyor: esas iş grafik araması değil, modüler cebirin dikkatli uygulanması.
\(M=10^9+7\) olsun. Implementasyonların hesapladığı ifade şudur:
$$C(h,w)=T_0+T_1+T_2+T_3,$$
burada
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
İstenen sonuç \(C(h,w)\bmod M\) değeridir.
Polinom olmayan tek parçalar \(2^h\), \(2^w\) ve \(2^{h+w}\) terimleridir. Şu gösterim faydalıdır:
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
Böylece formülün tamamı yalnızca üç üstel değere ve \(h,w\) cinsinden birkaç doğrusal ya da bilineer katsayıya bağlı hale gelir. Bu yüzden çözümün ızgarayı bellekte kurmasına gerek kalmaz.
Her terim sonucun başka bir yönünü temsil eder:
$$T_0=9P_{h+w}$$
dikdörtgenin iki boyutunu birden içeren baskın üstel katkıdır.
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
birbirinin yatay-dikey eşi olan iki düzeltme terimidir. Biri \(2^h\) ile, diğeri \(2^w\) ile ağırlıklandırıldığı için \(h\) ile \(w\) yer değiştirince rolleri de yer değiştirir.
Son olarak
$$T_3=2hw+10h+10w+10$$
saf polinom kısımdır ve üstel parçalar toplandıktan sonra kalan doğrusal-sabit dengeyi sağlar.
İfadeyi yeniden gruplayınca
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1)$$
elde edilir. Bu yazım iki önemli şeyi açıkça gösterir.
Birincisi, formül \(h\leftrightarrow w\) değişiminde aynen kalır. Bu da yatay ve dikey yönleri değiştirildiğinde aynı kalan dikdörtgen simetrisiyle uyumludur.
İkincisi, \(2hw\) alan-benzeri çarpanı, baştaki \(9P_{h+w}\) dışında sabit olmayan bütün bileşenlerde yer alır. Yani kapalı form, alan etkisi, yönsel düzeltmeler ve doğrusal bir artık parça arasında dengelenmiştir.
\(h\) ve \(w\) büyük olduğu için uygulama ham tam sayı değeri doğrudan üretmez. Her ara sonuç hemen \(M\) moduna indirgenir.
Şu katsayıları tanımlayalım:
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
ve
$$Q_e\equiv 2^e \pmod M.$$
Böylece bütün hesap
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M$$
şekline iner. Bir katsayı ara aşamada negatif çıkarsa, \([0,M-1]\) aralığına normalize edilerek güvenli hale getirilir.
Implementasyonun en küçük kontrol noktası \((h,w)=(3,3)\) değeridir. Burada
$$2^3=8,\qquad 2^{3+3}=64.$$
Dört parçayı hesaplayalım:
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
Dolayısıyla
$$C(3,3)=576-128-128+88=408,$$
olur ve bu, implementasyondaki kontrol değeriyle birebir aynıdır. İkinci bir kontrol olarak \(C(3,6)=4696\) elde edilir.
C++, Python ve Java implementasyonları aynı işlem sırasını izler. Önce \(hw\) çarpımı \(M\) modunda hesaplanır. Sonra \(2^h\), \(2^w\) ve \(2^{h+w}\) hızlı üs alma ile bulunduğu için süre yalnızca üslerin bit uzunluğuna bağlı olur.
Daha sonra implementasyon, \(2hw-8w-10\) ve \(2hw-8h-10\) katsayılarını modda normalize eder, bunları ilgili \(2\) üsleriyle çarpar, polinom artık terimi \(2hw+10h+10w+10\) ile toplar ve son kez modulo indirger. Diller arasında sadece tam sayı ayrıntıları değişir; matematiksel algoritma aynıdır.
Üs alma dışındaki bütün işlemler sabit maliyetli modüler toplama ve çarpmalardır. Üç üs hesabı toplamda \(O(\log h+\log w+\log(h+w))\) zaman alır. Sabit katsayılar göz ardı edildiğinde toplam karmaşıklık \(O(\log(h+w))\) zaman ve \(O(1)\) ek bellektir.
El problema 716 pide un valor \(C(h,w)\) asociado a un grafo de rejilla de tamaño \(h\times w\). Las implementaciones en C++, Python y Java no recorren estados del grafo ni construyen la rejilla explícitamente. En su lugar, evalúan una fórmula cerrada módulo \(10^9+7\).
Eso significa que la matemática visible en el código ya está comprimida en una expresión algebraica simétrica. Una vez fijados \(h\) y \(w\), todo se reduce a combinar \(2^h\), \(2^w\), \(2^{h+w}\) y algunos términos lineales en \(h\) y \(w\). Por eso el método sigue siendo rápido incluso cuando las dimensiones son muy grandes.
Sea \(M=10^9+7\). Las implementaciones calculan
$$C(h,w)=T_0+T_1+T_2+T_3,$$
donde
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
La respuesta pedida es \(C(h,w)\bmod M\).
Las únicas partes no polinómicas son \(2^h\), \(2^w\) y \(2^{h+w}\). Conviene escribir
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
Así, toda la fórmula queda determinada por tres potencias de dos y por coeficientes lineales o bilineales en \(h\) y \(w\). Esa es la razón por la que el algoritmo no necesita representar el grafo de rejilla.
Cada término cumple una función específica:
$$T_0=9P_{h+w}$$
es la contribución principal que involucra simultáneamente las dos dimensiones.
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
son dos correcciones emparejadas. Una está ponderada por \(2^h\) y la otra por \(2^w\), de modo que se intercambian al permutar alto y ancho.
Por último,
$$T_3=2hw+10h+10w+10$$
es la parte puramente polinómica y ajusta el remanente después de combinar los términos exponenciales.
Reagrupando se obtiene
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1).$$
Esta forma deja claras dos propiedades.
La primera es la simetría \(h\leftrightarrow w\), coherente con el hecho de que un rectángulo no cambia esencialmente si se intercambian sus ejes.
La segunda es que el factor bilineal \(2hw\) aparece en todos los bloques no constantes salvo en el término principal \(9P_{h+w}\). La fórmula implementada mezcla, por tanto, un componente ligado al área, dos correcciones direccionales y un resto lineal.
Como \(h\) y \(w\) son grandes, las implementaciones nunca forman el entero completo sin reducción. Cada bloque se calcula ya en el anillo módulo \(M\).
Definimos
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
y además
$$Q_e\equiv 2^e \pmod M.$$
Entonces todo el cálculo se resume en
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M.$$
Si alguno de los coeficientes intermedios es negativo antes de reducir, se normaliza de nuevo al intervalo \([0,M-1]\).
La comprobación más pequeña incorporada usa \((h,w)=(3,3)\). En este caso
$$2^3=8,\qquad 2^{3+3}=64.$$
Calculamos los cuatro términos:
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
Por tanto,
$$C(3,3)=576-128-128+88=408,$$
que coincide exactamente con la verificación de la implementación. Otra comprobación da \(C(3,6)=4696\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan \(hw\) módulo \(M\). Luego obtienen \(2^h\), \(2^w\) y \(2^{h+w}\) mediante exponenciación rápida, así que el coste depende solo de la longitud binaria de los exponentes.
Después forman los dos coeficientes con signo \(2hw-8w-10\) y \(2hw-8h-10\), los normalizan módulo \(M\), los multiplican por las potencias de dos correspondientes, añaden el resto polinómico \(2hw+10h+10w+10\) y reducen la suma final. Cambian los detalles del lenguaje, pero no la matemática del algoritmo.
Fuera de las potencias, todo es aritmética modular de costo constante. Las tres exponenciaciones cuestan en total \(O(\log h+\log w+\log(h+w))\) tiempo, lo que equivale a \(O(\log(h+w))\) ignorando constantes. La memoria adicional es \(O(1)\).
第 716 题要求计算一个与 \(h\times w\) 网格图相关的量 \(C(h,w)\)。从实现可以看出，C++、Python 和 Java 版本都没有去枚举图上的状态，也没有显式构造整张网格图；它们做的是直接在模 \(10^9+7\) 的意义下计算一个闭式公式。
因此，这道题在实现层面呈现出来的核心数学并不是“搜索”，而是“化简”。当 \(h\) 和 \(w\) 给定后，整个问题被压缩为 \(2^h\)、\(2^w\)、\(2^{h+w}\) 与若干关于 \(h,w\) 的线性项、双线性项的组合。只要把这些部分按模数安全地算出来，就能得到最终结果。
设 \(M=10^9+7\)。实现计算的表达式为
$$C(h,w)=T_0+T_1+T_2+T_3,$$
其中
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
题目所需的值就是 \(C(h,w)\bmod M\)。
整个公式里，真正“增长很快”的只有三项：\(2^h\)、\(2^w\) 和 \(2^{h+w}\)。把它们记为
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
这样一来，\(C(h,w)\) 就可以被理解为“三个 2 的幂”乘上若干简单系数的线性组合。也就是说，程序根本不需要把网格图本身展开；它只要掌握这些幂值和相应系数，就能完成全部计算。
四个部分分别承担不同作用。
第一块
$$T_0=9P_{h+w}$$
依赖于 \(h+w\)，是最显眼的双指数型主项。
第二、第三块
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
是成对出现的修正项。一个乘 \(2^h\)，另一个乘 \(2^w\)，所以当交换 \(h\) 和 \(w\) 时，这两项会互换位置。
最后一块
$$T_3=2hw+10h+10w+10$$
完全是多项式项，不含指数因子。它的作用是在前面几块合并后补回剩余的常数与线性部分。
把同类项重新整理，可以得到
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1).$$
这个写法有两个优点。
第一，它清楚地说明了公式满足 \(h\leftrightarrow w\) 对称性：交换高和宽之后，表达式不变。这与矩形网格在横竖方向上的对称性一致。
第二，它把结构分成了几类：\(2hw\) 这一面积型因子同时出现在多个部分中；\(9P_{h+w}\) 是单独的主项；\((8w+10)P_h\) 与 \((8h+10)P_w\) 是方向对应的修正；最后 \(10(h+w+1)\) 则是纯线性尾项。这样的分组比原式更容易读懂。
由于 \(h,w\) 很大，程序不会先算出普通整数意义下的 \(C(h,w)\) 再取模，而是从头到尾都在模 \(M\) 的环里工作。
定义
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
再令
$$Q_e\equiv 2^e \pmod M.$$
那么整个问题就变成
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M.$$
如果某个中间系数在普通整数意义下是负数，那么先把它加上足够多的 \(M\) 再取模，使它回到 \([0,M-1]\) 范围内。这样后续的乘法和加法都会保持稳定。
实现里最小的校验点之一是 \((h,w)=(3,3)\)。此时
$$2^3=8,\qquad 2^{3+3}=64.$$
四个部分分别为
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
因此
$$C(3,3)=576-128-128+88=408.$$
这个结果与实现中的校验值完全一致。另一个已知校验是 \(C(3,6)=4696\)，同样吻合。
C++、Python 和 Java 实现遵循同一条计算路径。首先求出 \(hw\bmod M\)。然后分别用快速幂计算 \(2^h\)、\(2^w\) 和 \(2^{h+w}\)，因此耗时只和指数的二进制长度有关，而不是和网格大小本身成正比。
接着，实现构造两个可能为负的系数 \(2hw-8w-10\) 与 \(2hw-8h-10\)，把它们规范化到模 \(M\) 的范围内，再分别乘上对应的 2 的幂，随后加上多项式尾项 \(2hw+10h+10w+10\)，最后再做一次模归约。三种语言的语法细节不同，但执行的数学步骤完全一致。
除去快速幂之外，其余操作都只是常数次模加法和模乘法。三次幂运算总共需要 \(O(\log h+\log w+\log(h+w))\) 时间，按数量级可写成 \(O(\log(h+w))\)。额外空间只需要保存少量整数，因此为 \(O(1)\)。
В задаче 716 требуется вычислить величину \(C(h,w)\), связанную с прямоугольным решётчатым графом размера \(h\times w\). Реализации на C++, Python и Java не перебирают состояния графа и не строят сетку по вершинам. Вместо этого они сразу вычисляют замкнутую формулу по модулю \(10^9+7\).
Это важно: вся математика, реально используемая программой, уже сведена к компактному симметричному выражению. После задания \(h\) и \(w\) задача становится вычислением комбинации из \(2^h\), \(2^w\), \(2^{h+w}\) и нескольких линейных или билинейных членов. Поэтому решение работает быстро даже для очень больших размеров.
Пусть \(M=10^9+7\). Реализации считают
$$C(h,w)=T_0+T_1+T_2+T_3,$$
где
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
Искомое значение равно \(C(h,w)\bmod M\).
Неполиномиальными частями являются только три степени двойки: \(2^h\), \(2^w\) и \(2^{h+w}\). Удобно обозначить
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
Тогда вся формула определяется всего тремя экспоненциальными значениями и несколькими коэффициентами, зависящими от \(h\) и \(w\) линейно или билинейно. Поэтому никакая явная обработка графа не требуется.
Каждое слагаемое играет свою роль.
$$T_0=9P_{h+w}$$
является главным вкладом, зависящим сразу от обеих размерностей.
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
образуют парные корректирующие члены. Один умножается на \(2^h\), другой на \(2^w\), так что при перестановке \(h\) и \(w\) они просто меняются местами.
Наконец,
$$T_3=2hw+10h+10w+10$$
является чисто полиномиальной частью и компенсирует остаток после экспоненциальных слагаемых.
После перегруппировки получаем
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1).$$
Здесь сразу видны две вещи.
Во-первых, формула симметрична относительно замены \(h\leftrightarrow w\), что естественно для прямоугольника, у которого горизонтальное и вертикальное направления равноправны.
Во-вторых, фактор \(2hw\), похожий на площадь, входит во все неконстантные блоки, кроме ведущего \(9P_{h+w}\). Значит, реализованное выражение объединяет главный вклад, два направленных поправочных члена и один линейный остаток.
Поскольку \(h\) и \(w\) велики, программы не строят обычное целое значение \(C(h,w)\) целиком. Каждый строительный блок сразу вычисляется по модулю \(M\).
Обозначим
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
а также
$$Q_e\equiv 2^e \pmod M.$$
Тогда всё вычисление записывается как
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M.$$
Если промежуточный коэффициент до взятия по модулю отрицателен, его нормализуют обратно в диапазон \([0,M-1]\), чтобы последующие умножения и сложения были корректными.
Наименьшая встроенная проверка использует \((h,w)=(3,3)\). Здесь
$$2^3=8,\qquad 2^{3+3}=64.$$
Посчитаем четыре слагаемых:
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
Следовательно,
$$C(3,3)=576-128-128+88=408,$$
что в точности совпадает с контрольным значением реализации. Ещё одна проверка даёт \(C(3,6)=4696\).
Реализации на C++, Python и Java выполняют одну и ту же последовательность действий. Сначала вычисляется произведение \(hw\) по модулю \(M\). Затем с помощью быстрого возведения в степень находятся \(2^h\), \(2^w\) и \(2^{h+w}\), поэтому время зависит только от длины двоичной записи показателей.
После этого реализация строит два знаковых коэффициента \(2hw-8w-10\) и \(2hw-8h-10\), нормализует их по модулю \(M\), умножает на соответствующие степени двойки, добавляет полиномиальный хвост \(2hw+10h+10w+10\) и ещё раз берёт сумму по модулю. Различаются лишь технические детали языков, а не математическая схема.
Вне быстрого возведения в степень остаётся только константное число модульных операций. Три вычисления степеней требуют \(O(\log h+\log w+\log(h+w))\) времени, что эквивалентно \(O(\log(h+w))\) с точностью до констант. Дополнительная память равна \(O(1)\).
المسألة 716 تطلب حساب كمية \(C(h,w)\) مرتبطة بشبكة مستطيلة أبعادها \(h\times w\). ما تكشفه التنفيذات في C++ وPython وJava هو أنها لا تعد حالات الرسم البياني حالةً بحالة، ولا تبني الشبكة صراحة. بدلاً من ذلك، فهي تقيم صيغة مغلقة مباشرةً بترديد \(10^9+7\).
لذلك فجوهر الحل الظاهر في الكود ليس بحثًا على الرسم البياني، بل تبسيط جبري منظم. بعد تثبيت \(h\) و\(w\)، تصبح المهمة كلها عبارة عن دمج \(2^h\) و\(2^w\) و\(2^{h+w}\) مع عدد قليل من الحدود الخطية والثنائية الخطية في \(h\) و\(w\). ومن هنا تأتي السرعة حتى عندما تكون الأبعاد كبيرة جدًا.
ليكن \(M=10^9+7\). تقوم التنفيذات بحساب
$$C(h,w)=T_0+T_1+T_2+T_3,$$
حيث
$$T_0=9\cdot 2^{h+w},$$
$$T_1=(2hw-8w-10)2^h,$$
$$T_2=(2hw-8h-10)2^w,$$
$$T_3=2hw+10h+10w+10.$$
إذن الجواب المطلوب هو \(C(h,w)\bmod M\).
الأجزاء غير متعددة الحدود في الصيغة هي فقط \(2^h\) و\(2^w\) و\(2^{h+w}\). ومن المناسب كتابة
$$P_h=2^h,\qquad P_w=2^w,\qquad P_{h+w}=2^{h+w}=P_hP_w.$$
وبذلك تصبح الصيغة كلها معتمدة على ثلاث قوى للعدد \(2\)، وعلى معاملات بسيطة خطية أو ثنائية الخطية في \(h\) و\(w\). لهذا السبب لا يحتاج الحل إلى تمثيل الرسم البياني نفسه في الذاكرة.
كل حد من الحدود الأربعة يؤدي دورًا محددًا:
$$T_0=9P_{h+w}$$
وهو الحد الأسي الرئيسي الذي يعتمد على البعدين معًا.
أما
$$T_1=(2hw-8w-10)P_h,\qquad T_2=(2hw-8h-10)P_w$$
فهما حدان تصحيحيان متناظران. أحدهما موزون بـ \(2^h\) والآخر بـ \(2^w\)، ولذلك يتبادلان الدور عند تبديل \(h\) و\(w\).
وأخيرًا
$$T_3=2hw+10h+10w+10$$
هو الحد كثير الحدود الخالص، ويعوض الباقي الخطي والثابت بعد جمع الأجزاء الأسية.
إذا أعدنا تجميع الحدود نحصل على
$$C(h,w)=2hw(P_h+P_w+1)+9P_{h+w}-(8w+10)P_h-(8h+10)P_w+10(h+w+1).$$
وهذه الصيغة تكشف حقيقتين مهمتين.
الأولى أنها متناظرة تحت التبديل \(h\leftrightarrow w\)، وهذا ينسجم مع تناظر المستطيل نفسه عند تبديل الاتجاه الأفقي بالاتجاه الرأسي.
والثانية أن العامل \(2hw\) ذو الطابع المساحي يظهر في كل الأجزاء غير الثابتة تقريبًا، باستثناء الحد الرئيسي \(9P_{h+w}\). لذلك يمكن قراءة التعبير على أنه مزيج من مساهمة رئيسية، وتصحيحين اتجاهيين، وباقٍ خطي نهائي.
بما أن \(h\) و\(w\) كبيران، فلا يتم تكوين القيمة الصحيحة الكاملة لـ \(C(h,w)\) أولًا ثم أخذ الترديد. بل تُختزل كل قطعة مباشرة داخل الحسابات المعيارية.
نعرّف
$$\alpha_h\equiv 2hw-8w-10 \pmod M,$$
$$\alpha_w\equiv 2hw-8h-10 \pmod M,$$
$$\beta\equiv 2hw+10h+10w+10 \pmod M,$$
وكذلك
$$Q_e\equiv 2^e \pmod M.$$
عندها تصبح العملية كلها
$$C(h,w)\equiv 9Q_{h+w}+\alpha_hQ_h+\alpha_wQ_w+\beta \pmod M.$$
وإذا ظهر معامل سالب قبل الاختزال، تتم إعادته إلى المجال \([0,M-1]\) قبل المتابعة، حتى تبقى الضربات والجمعات المعيارية سليمة.
أصغر نقطة تحقق مضمّنة هي \((h,w)=(3,3)\). عندئذ
$$2^3=8,\qquad 2^{3+3}=64.$$
فنحسب الحدود الأربعة:
$$T_0=9\cdot 64=576,$$
$$T_1=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=(18-24-10)\cdot 8=-128,$$
$$T_2=(2\cdot 3\cdot 3-8\cdot 3-10)2^3=-128,$$
$$T_3=2\cdot 3\cdot 3+10\cdot 3+10\cdot 3+10=88.$$
إذن
$$C(3,3)=576-128-128+88=408,$$
وهو نفس مقدار التحقق الموجود في التنفيذ. كما أن فحصًا آخر يعطي \(C(3,6)=4696\).
تتبع تنفيذات C++ وPython وJava المسار نفسه. أولًا يُحسب \(hw\) بترديد \(M\). ثم تُحسب القيم \(2^h\) و\(2^w\) و\(2^{h+w}\) باستخدام الرفع السريع للأس، ولذلك تعتمد الكلفة على طول التمثيل الثنائي للأسس لا على حجم الشبكة نفسه.
بعد ذلك، تُكوَّن المعاملات الموقعة \(2hw-8w-10\) و\(2hw-8h-10\)، وتُطبَّع معياريًا، ثم تُضرب في قوى العدد \(2\) المناسبة، ثم يضاف الحد كثير الحدود \(2hw+10h+10w+10\)، وأخيرًا يُختزل المجموع مرة أخيرة بترديد \(M\). الاختلافات بين اللغات تنفيذية فقط، أما الخوارزمية الرياضية فهي واحدة.
خارج حساب القوى لا يوجد إلا عدد ثابت من العمليات المعيارية. حساب \(2^h\) و\(2^w\) و\(2^{h+w}\) يحتاج إجمالًا إلى \(O(\log h+\log w+\log(h+w))\) زمنًا، وهذا يساوي من حيث الرتبة \(O(\log(h+w))\). أما الذاكرة الإضافية فهي \(O(1)\).