// ////////////////////////////////////////////////////////
// # Title
// Gnomon numbering
//
// # URL
// https://projecteuler.net/problem=412
// http://euler.stephan-brumme.com/412/
//
// # Problem
// For integers `m`, `n` (`0 <= n < m`), let `L(m, n)` be an `m * m` grid with the top-right `n * n` grid removed.
//
// For example, `L(5, 3)` looks like this:
//
// ![L shape](p412_table53.png)
//
// We want to number each cell of `L(m, n)` with consecutive integers 1, 2, 3, ... such that the number in every cell is smaller than the number below it and to the left of it.
//
// For example, here are two valid numberings of `L(5, 3)`:
//
// ![examples](p412_tablenums.png)
//
// Let `LC(m, n)` be the number of valid numberings of `L(m, n)`.
// It can be verified that `LC(3, 0) = 42`, `LC(5, 3) = 250250`, `LC(6, 3) = 406029023400` and `LC(10, 5) mod 76543217 = 61251715`.
//
// Find `LC(10000, 5000) mod 76543217`.
//
// # Written by
// Stephan Brumme
// December 2017
//
// # Idea
// Okay, at the moment I have no idea how to solve that problem.
//
// But it was fun spending a few minutes on writing a brute-force solution for grids no larger than 6x6.
// By the way: ''bruteForce(6,3)'' finished after about 7.5 hours ...
// The next morning I wrote ''slow'' which is based on the following observation:
// - when filling the grid "in reverse order" (that means from 16 to 1), then smaller numbers are automatically stacked on larger numbers
// - each column of the grid can be seen as a "skyscraper"
// - there are no gaps in a skyscraper
// - each skyscraper is at most as high as its left neighbor
// In the end I don't have to store the single numbers in the grid (a 2D data structure).
// Instead I just need to track the height of each skyscraper (a 1D data structure).
// These heights are identical for many different number distributions so that I can accelerate the search by aggressive memoization.
// ''slow(6,3)'' finds the correct result in less than 0.01 seconds (vs. 7.5 hours !).
// Note: all results are displayed mod 76543217.
//
// However, this improved algorithm can't solve `LC(10000, 5000)` in a reasonable timeframe.
#include
#include
#include