3700. Number of ZigZag Arrays II

class Solution {

    private static final long MOD = 1_000_000_007L;

    static class Matrix {

        int n, m;
        long[] data;

        Matrix(int n, int m) {
            this.n = n;
            this.m = m;
            this.data = new long[n * m];
        }

        long get(int i, int j) {
            return data[i * m + j];
        }

        void set(int i, int j, long val) {
            data[i * m + j] = val;
        }

        Matrix mul(Matrix b) {
            Matrix res = new Matrix(n, b.m);

            for (int i = 0; i < n; i++) {
                for (int k = 0; k < m; k++) {
                    long cur = get(i, k);

                    if (cur == 0) {
                        continue;
                    }

                    for (int j = 0; j < b.m; j++) {
                        res.set(
                            i,
                            j,
                            (res.get(i, j) + cur * b.get(k, j)) % MOD
                        );
                    }
                }
            }

            return res;
        }

        Matrix pow(long exp, Matrix res) {
            Matrix base = new Matrix(n, m);
            System.arraycopy(data, 0, base.data, 0, data.length);

            while (exp > 0) {
                if ((exp & 1L) == 1L) {
                    res = res.mul(base);
                }

                base = base.mul(base);
                exp >>= 1;
            }

            return res;
        }
    }

    public int zigZagArrays(int n, int l, int r) {

        int m = r - l + 1;

        if (n == 1) {
            return m;
        }

        Matrix trans = new Matrix(2 * m, 2 * m);

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < i; j++) {
                trans.set(i, j + m, 1L);
            }

            for (int j = i + 1; j < m; j++) {
                trans.set(i + m, j, 1L);
            }
        }

        Matrix dp = new Matrix(1, 2 * m);

        for (int i = 0; i < 2 * m; i++) {
            dp.set(0, i, 1L);
        }

        dp = trans.pow(n - 1L, dp);

        long ans = 0;

        for (int i = 0; i < 2 * m; i++) {
            ans = (ans + dp.get(0, i)) % MOD;
        }

        return (int) ans;
    }
}

MOD = 1_000_000_007


class Matrix:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.data = [0] * (n * m)

    def get(self, i, j):
        return self.data[i * self.m + j]

    def set(self, i, j, val):
        self.data[i * self.m + j] = val

    def mul(self, b):
        res = Matrix(self.n, b.m)

        for i in range(self.n):
            for k in range(self.m):
                cur = self.get(i, k)

                if cur == 0:
                    continue

                for j in range(b.m):
                    res.set(
                        i,
                        j,
                        (res.get(i, j) + cur * b.get(k, j)) % MOD
                    )

        return res

    def pow(self, exp, res):
        base = Matrix(self.n, self.m)
        base.data[:] = self.data[:]

        while exp > 0:
            if exp & 1:
                res = res.mul(base)

            base = base.mul(base)
            exp >>= 1

        return res


class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:

        m = r - l + 1

        if n == 1:
            return m

        trans = Matrix(2 * m, 2 * m)

        for i in range(m):

            for j in range(i):
                trans.set(i, j + m, 1)

            for j in range(i + 1, m):
                trans.set(i + m, j, 1)

        dp = Matrix(1, 2 * m)

        for i in range(2 * m):
            dp.set(0, i, 1)

        dp = trans.pow(n - 1, dp)

        ans = 0

        for i in range(2 * m):
            ans = (ans + dp.get(0, i)) % MOD

        return ans

class Solution {
    static constexpr long long MOD = 1000000007LL;

    struct Matrix {
        int n, m;
        vector<long long> data;

        Matrix(int n, int m) : n(n), m(m), data(n * m, 0) {}

        long long get(int i, int j) {
            return data[i * m + j];
        }

        void set(int i, int j, long long val) {
            data[i * m + j] = val;
        }

        Matrix mul(Matrix &b) {
            Matrix res(n, b.m);

            for (int i = 0; i < n; i++) {
                for (int k = 0; k < m; k++) {
                    long long cur = get(i, k);

                    if (cur == 0)
                        continue;

                    for (int j = 0; j < b.m; j++) {
                        res.set(
                            i,
                            j,
                            (res.get(i, j) + cur * b.get(k, j)) % MOD
                        );
                    }
                }
            }

            return res;
        }

        Matrix pow(long long exp, Matrix res) {
            Matrix base(n, m);
            base.data = data;

            while (exp > 0) {
                if (exp & 1LL)
                    res = res.mul(base);

                base = base.mul(base);
                exp >>= 1;
            }

            return res;
        }
    };

public:
    int zigZagArrays(int n, int l, int r) {

        int m = r - l + 1;

        if (n == 1)
            return m;

        Matrix trans(2 * m, 2 * m);

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < i; j++)
                trans.set(i, j + m, 1);

            for (int j = i + 1; j < m; j++)
                trans.set(i + m, j, 1);
        }

        Matrix dp(1, 2 * m);

        for (int i = 0; i < 2 * m; i++)
            dp.set(0, i, 1);

        dp = trans.pow(n - 1LL, dp);

        long long ans = 0;

        for (int i = 0; i < 2 * m; i++)
            ans = (ans + dp.get(0, i)) % MOD;

        return (int)ans;
    }
};