Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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\).

Step 1: Isolate the exponential core

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.

Step 2: Separate the four algebraic contributions

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.

Step 3: Rewrite the formula to expose symmetry

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.

Step 4: Move everything into modular arithmetic

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.

Worked Example

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=716
2. Grid graph background: Wikipedia — Grid graph
3. Modular arithmetic: Wikipedia — Modular arithmetic
4. Exponentiation by squaring: Wikipedia — Exponentiation by squaring
5. Powers of two: Wikipedia — Power of two