Project Euler Problem 743
A window into a matrix is a contiguous sub matrix.
Solution
Answer: 259158998
Let $c_i\in{0,1,2}$ be the sum of the two entries in column $i$.
The condition says:
$$c_i+c_{i+1}+\cdots+c_{i+k-1}=k$$
for every $2\times k$ window.
Subtract consecutive windows:
$$(c_{i+1}+\cdots+c_{i+k})-(c_i+\cdots+c_{i+k-1})=0$$
so
$$c_{i+k}=c_i.$$
Hence the column-sum sequence is periodic with period $k$.
For $n=qk+r$, each residue class mod $k$ appears either $q$ or $q+1$ times.
In this problem,
$$k=10^8,\qquad n=10^{16}=10^8\cdot10^8,$$
so $q=10^8$ and $r=0$.
For a residue class:
- column sum $0$: $1$ choice,
- column sum $1$: $2$ choices,
- column sum $2$: $1$ choice.
Thus each position contributes the polynomial
$$1+2^q x+x^2,$$
and we need total column sum $k$, giving
$$A(k,n)=[x^k](1+2^q x+x^2)^k.$$
Let
$$a=2^{10^8}\pmod{10^9+7}.$$
Then
$$A=x^k^k.$$
Using the standard recurrence for these central trinomial-type coefficients:
$$u_0=1,\qquad u_1=a,$$
$$u_{m+1} = \frac{(2m+1)a,u_m-m(a^2-4)u_{m-1}}{m+1} \pmod{10^9+7},$$
and iterating up to $m=10^8-1$, we obtain:
$$A(10^8,10^{16}) \equiv 332704090 \pmod{1,000,000,007}.$$
Answer: 332704090