Fancy Arrays (Codeforces 1895F)
Tags: Math, matrices

Let's call an array $$$a$$$ of $$$n$$$ non-negative integers fancy if the following conditions hold:   at least one from the numbers $$$x$$$, $$$x + 1$$$, ..., $$$x+k-1$$$ appears in the array;  consecutive elements of the array differ by at most $$$k$$$ (i.e. $$$|a_i-a_{i-1}| \le k$$$ for each $$$i \in [2, n]$$$). You are given $$$n$$$, $$$x$$$ and $$$k$$$. Your task is to calculate the number of fancy arrays of length $$$n$$$. Since the answer can be large, print it modulo $$$10^9+7$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases.The only line of each test case contains three integers $$$n$$$, $$$x$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$; $$$0 \le x \le 40$$$).

Output: For each test case, print a single integer — the number of fancy arrays of length $$$n$$$, taken modulo $$$10^9+7$$$.

Note: In the first test case of the example, the following arrays are fancy:  $$$[0, 0, 0]$$$;  $$$[0, 0, 1]$$$;  $$$[0, 1, 0]$$$;  $$$[0, 1, 1]$$$;  $$$[0, 1, 2]$$$;  $$$[1, 0, 0]$$$;  $$$[1, 0, 1]$$$;  $$$[1, 1, 0]$$$;  $$$[2, 1, 0]$$$. 

Sample Inputs:
4
3 0 1
1 4 25
4 7 2
1000000000 40 1000000000

Sample Outputs:
9
25
582
514035484

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * x + v

def matmul(a, b, n):
    if len(b) == n:
        c = [0] * n
        for i in range(n):
            x = 0
            for j in range(n):
                x += a[i * n + j] * b[j] % mod
            c[i] = x % mod
    else:
        c = [0] * (n * n)
        for i in range(n):
            for j in range(n):
                x = 0
                for k in range(n):
                    x += a[i * n + k] * b[k * n + j] % mod
                c[i * n + j] = x % mod
    return c
t = int(input())
ans = []
mod = pow(10, 9) + 7
for _ in range(t):
    (n, x, k) = map(int, input().split())
    ans0 = pow(2 * k + 1, n - 1, mod) * (x + k)
    if x:
        (a, b) = ([0] * (x * x), [1] * x)
        for i in range(x):
            for j in range(max(i - k, 0), min(i + k + 1, x)):
                a[f(i, j)] = 1
        n -= 1
        while n:
            if n & 1:
                b = matmul(a, b, x)
            a = matmul(a, a, x)
            n >>= 1
        ans0 -= sum(b)
    ans0 %= mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
from itertools import permutations
from heapq import heappop, heappush
from collections import deque
import random
import bisect
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mod = 10 ** 9 + 7

def mat_mul(X, Y):
    (n, m) = (len(X), len(Y[0]))
    res = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(Y)):
                res[i][j] += X[i][k] * Y[k][j]
                res[i][j] %= mod
    return res

def solve(n, k, x):
    mod = 10 ** 9 + 7
    res = pow(2 * k + 1, n - 1, mod) * (x + k) % mod
    if x == 0:
        return res
    A = [[0] * x for i in range(x)]
    for i in range(x):
        for j in range(x):
            if abs(i - j) <= k:
                A[i][j] = 1
    E = [[1] for _ in range(x)]
    t = n - 1
    while t:
        if t & 1:
            E = mat_mul(A, E)
        A = mat_mul(A, A)
        t >>= 1
    for i in range(x):
        res -= E[i][0]
        res %= mod
    return res
for _ in range(int(input())):
    (n, x, k) = mi()
    print(solve(n, k, x))

Solution (Python):
import sys
from itertools import permutations
from heapq import heappop, heappush
from collections import deque
import random
import bisect
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mod = 10 ** 9 + 7

def mat_mul(X, Y):
    (n, m) = (len(X), len(Y[0]))
    res = [[0 for j in range(m)] for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(Y)):
                res[i][j] += X[i][k] * Y[k][j]
                res[i][j] %= mod
    return res

def solve(n, k, x):
    mod = 10 ** 9 + 7
    res = pow(2 * k + 1, n - 1, mod) * (x + k) % mod
    if x == 0:
        return res
    A = [[0] * x for i in range(x)]
    for i in range(x):
        for j in range(x):
            if abs(i - j) <= k:
                A[i][j] = 1
    E = [[1] for _ in range(x)]
    t = n - 1
    while t:
        if t & 1:
            E = mat_mul(A, E)
        A = mat_mul(A, A)
        t >>= 1
    for i in range(x):
        res -= E[i][0]
        res %= mod
    return res
for _ in range(int(input())):
    (n, x, k) = mi()
    print(solve(n, k, x))