# 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)!

Difficulty: interview

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

# https://www.python-course.eu/python3_memoization.php
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):
    # Your Code Here
    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