# Problem Description

Let's imagine a function `F(n)`, which is defined over the integers
in the range of `1 <= n <= max_n`, and `0 <= F(n) <= max_fn` for every `n`.

There are `(1 + max_fn) ** max_n` possible definitions of `F` in total.

Out of those definitions, how many `F`s satisfy the following equations?
Since your answer will be very large, please give your answer **modulo 12345787**.

* `F(n) + F(n + 1) <= max_fn` for `1 <= n < max_n`
* `F(max_n) + F(1) <= max_fn`

# Constraints

`1 <= max_n <= 100`

`1 <= max_fn <= 5`

The inputs will be always valid integers.

# Examples

```python
# F(1) + F(1) <= 1, F(1) = 0
circular_limited_sums(1, 1) == 1

# F = (0, 0), (0, 1), (1, 0)
circular_limited_sums(2, 1) == 3

# F = (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0)
circular_limited_sums(3, 1) == 4

# F = (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0),
# (0, 1, 0, 1), (1, 0, 0, 0), (1, 0, 1, 0)
circular_limited_sums(4, 1) == 7

# F = (0), (1)
circular_limited_sums(1, 2) == 2
# F = (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)
circular_limited_sums(2, 2) == 6
# F = (0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1),
# (0, 2, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (2, 0, 0)
circular_limited_sums(3, 2) == 11
circular_limited_sums(4, 2) == 26
```

# Acknowledgement

This problem was designed as a hybrid of [Project Euler #209: Circular Logic](https://projecteuler.net/problem=209) and [Project Euler #164: Numbers for which no three consecutive digits have a sum greater than a given value](https://projecteuler.net/problem=164).

If you enjoyed this Kata, please also have a look at [my other Katas](https://www.codewars.com/users/Bubbler/authored)!

Source: codewars | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Starter code: def circular_limited_sums(max_n, max_fn):
	

Solutions:
mod = 12345787
mat = [([1, 1], [0, 1, 3]), ([2, 1, -1], [0, 2, 6, 11]), ([2, 3, -1, -1], [0, 2, 10, 23, 70]), ([3, 3, -4, -1, 1], [0, 3, 15, 42, 155, 533]), ([3, 6, -4, -5, 1, 1], [0, 3, 21, 69, 301, 1223, 5103])]
for i in range(100):
	[m.append(sum((k * m[-1 - i] for (i, k) in enumerate(c))) % mod) for (c, m) in mat]

def circular_limited_sums(max_n, max_fn):
	return mat[max_fn - 1][1][max_n]


def circular_limited_sums(max_n, max_fn):
	if max_n == 1:
		return sum([1 for i in range(max_fn + 1) if i + i <= max_fn]) % 12345787
	nexts = [list(filter(lambda x: i + x <= max_fn, range(max_fn + 1))) for i in range(max_fn + 1)]
	result = 0
	for ii in range(max_fn + 1):
		v = [[1 if e in nexts[ii] else 0 for e in range(max_fn + 1)]]
		for _ in range(max_n - 2):
			v.append([0 for i in range(max_fn + 1)])
			for (i, e) in enumerate(v[-2]):
				for j in nexts[i]:
					v[-1][j] += e
		result += sum([e for (i, e) in enumerate(v[-1]) if i + ii <= max_fn])
	return result % 12345787


class Memoize:

	def __init__(self, fn):
		self.fn = fn
		self.memo = {}

	def __call__(self, *args):
		if args not in self.memo:
			self.memo[args] = self.fn(*args)
		return self.memo[args]

@Memoize
def linear_limited_sums(X, Y, head, tail):
	if X == 1:
		return 1 if head == tail else 0
	if X == 2:
		return 1 if head + tail <= Y else 0
	return sum((linear_limited_sums(X - 1, Y, head, T) for T in range(Y - tail + 1))) % 12345787

def circular_limited_sums(X, Y):
	return sum((linear_limited_sums(X, Y, head, tail) for head in range(Y + 1) for tail in range(Y - head + 1))) % 12345787


dp = {}

def circular_limited_sums(max_n, max_fn):
	if max_n == 1:
		return max_fn // 2 + 1
	else:
		s = 0
		for i in range(max_fn + 1):
			s += solve(max_n - 1, max_fn, i, i)
			s %= 12345787
		return s

def solve(n, m, first, last):
	if (n, m, first, last) in dp:
		return dp[n, m, first, last]
	if n == 1:
		dp[n, m, first, last] = m - max(first, last) + 1
		return dp[n, m, first, last]
	s = 0
	for i in range(m - last + 1):
		if first is None:
			s += solve(n - 1, m, i, i)
		else:
			s += solve(n - 1, m, first, i)
		s %= 12345787
	dp[n, m, first, last] = s
	return dp[n, m, first, last]


import numpy as np

def pow(mat, n):
	if n == 1:
		return mat
	mat2 = pow(mat, n // 2)
	mat2 = np.dot(mat2, mat2) % 12345787
	if n % 2 == 1:
		mat2 = np.dot(mat2, mat) % 12345787
	return mat2

def circular_limited_sums(max_n, m):
	mat = np.zeros(shape=(m + 1, m + 1), dtype=np.int64)
	for a in range(m + 1):
		for b in range(m + 1):
			if a + b <= m:
				mat[a, b] = 1
	return np.trace(pow(mat, max_n)) % 12345787


def circular_limited_sums(max_n, max_fn):
	p = 12345787
	m = max_fn + 1
	v = [[int(f1 == fn) for fn in range(m)] for f1 in range(m)]
	for n in range(max_n - 1):
		v = [[sum(w[:m - fn]) % p for fn in range(m)] for w in v]
	return sum((sum(w[:m - f1]) % p for (f1, w) in enumerate(v))) % p


MODULUS = 12345787

def circular_limited_sums(max_n, max_fn):
	total = 0
	for initial in range(max_fn + 1):
		counts = {v: 0 for v in range(max_fn + 1)}
		counts[initial] = 1
		for n in range(1, max_n):
			new_counts = {}
			for v in range(max_fn + 1):
				new_counts[v] = sum((counts[v_prev] for v_prev in range(max_fn - v + 1))) % MODULUS
			counts = new_counts
		total += sum((counts[v] for v in range(max_fn - initial + 1))) % MODULUS
	return total % MODULUS


import numpy as np

def circular_limited_sums(max_n, max_fn):
	if max_n == 1:
		return max_fn // 2 + 1
	if max_n == 2:
		return (max_fn + 1) * (max_fn + 2) // 2
	t = np.matrix(np.flipud(np.tri(max_fn + 1, max_fn + 1, 0, object)))
	k = t ** (max_n - 2)
	return (np.sum(k.dot(np.arange(max_fn + 1, 0, -1)[:, None])) - np.sum(np.multiply(k.dot(t), np.logical_not(t)))) % 12345787


def generate_table(max_n, max_fn):
	a = []
	a.append([[0 for __ in range(_ + 1)] for _ in range(max_fn + 1)])
	for j in range(max_fn + 1):
		for k in range(j + 1):
			if j + k <= max_fn:
				a[0][j][k] = 1
	i = 1
	while 2 ** i + 1 <= max_n:
		a.append([[0 for __ in range(_ + 1)] for _ in range(max_fn + 1)])
		for j in range(max_fn + 1):
			for k in range(j + 1):
				a[i][j][k] = sum([a[i - 1][max(j, c)][min(j, c)] * a[i - 1][max(k, c)][min(k, c)] % 12345787 for c in range(max_fn + 1)])
		i += 1
	return a

def linear(s1, s2, indices, table, max_fn):
	index = indices[-1]
	if len(indices) == 1:
		return table[index][max(s1, s2)][min(s1, s2)]
	else:
		return sum([table[index][max(s1, s)][min(s1, s)] * linear(s, s2, indices[:-1], table, max_fn) for s in range(0, max_fn + 1)])

def circular_limited_sums(max_n, max_fn):
	table = generate_table(max_n + 1, max_fn)
	lengths = [2 ** i + 1 for i in range(8)]
	lengths = lengths[::-1]
	m = max_n
	indices = []
	for (index, length) in enumerate(lengths):
		while length - 1 <= m:
			indices.append(7 - index)
			m -= length - 1
	if len(indices) == 1:
		return sum([table[indices[0]][s][s] for s in range(max_fn + 1)]) % 12345787
	if len(indices) == 2:
		return sum([table[indices[0]][max(s, t)][min(s, t)] * table[indices[1]][max(s, t)][min(s, t)] for s in range(max_fn + 1) for t in range(max_fn + 1)]) % 12345787
	if len(indices) >= 3:
		return sum([table[indices[0]][max(s, s1)][min(s, s1)] * table[indices[1]][max(s, s2)][min(s, s2)] * linear(s1, s2, indices[2:], table, max_fn) for s in range(max_fn + 1) for s1 in range(max_fn + 1) for s2 in range(max_fn + 1)]) % 12345787


def circular_limited_sums(max_n, max_fn):
	FL = [[0] * (max_fn + 1) for i in range(max_fn + 1)]
	for i in range(max_fn + 1):
		for j in range(max_fn + 1):
			if i == j:
				FL[i][j] = 1
	for x in range(max_n - 1):
		nextFL = [[0] * (max_fn + 1) for i in range(max_fn + 1)]
		for i in range(max_fn + 1):
			for j in range(max_fn + 1):
				for k in range(max_fn + 1):
					if j + k <= max_fn:
						nextFL[i][k] += FL[i][j]
		FL = nextFL
	tot = 0
	for i in range(max_fn + 1):
		for j in range(max_fn + 1):
			if i + j <= max_fn:
				tot += FL[i][j]
	return tot % 12345787