Throwing Dice

Your task is to calculate the number of ways to get a sum n by throwing dice. Each throw yields an integer between 1…6$1\dots 6$.

For example, if n = 10, some possible ways are 3+ 3+ 4, 1+4+1+4 and 1+1+6+1+1

Example:

Input:  n = 8
Output: 125

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

template <class T>
struct matrix
{
    vector<vector<T>> m;
    long long r, c;
    matrix() : r(), c() {}
    matrix(long long r, long long c, T x) : r(r), c(c), m(r, vector<T>(c, x)) {}
    matrix(long long n) : matrix(n, n, 0)
    {
        // identity matrix
        for (long long i = 0; i < n; i++)
            m[i][i] = 1;
    }
    matrix operator*(matrix<T> b)
    {
        matrix<T> a = *this;
        assert(a.c == b.r);
        matrix<T> o(a.r, b.c, 0);
        for (long long i = 0; i < a.r; i++)
            for (long long j = 0; j < b.c; j++)
                for (long long k = 0; k < a.c; k++)
                    o.m[i][j] = (o.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
        return o;
    }
    matrix operator^(long long b)
    {
        assert(r == c);
        matrix<T> a(r, c, 0);
        for (long long i = 0; i < r; i++)
            for (long long j = 0; j < c; j++)
                a.m[i][j] = m[i][j];
        matrix<T> o(r);
        while (b)
        {
            if (b % 2)
                o = o * a;
            a = a * a;
            b /= 2;
        }
        return o;
    }
};

long long throwingDice(long long n)
{

    n += 5;
    matrix<long long> A(1, 6, 0);
    A.m[0][5] = 1;
    matrix<long long> B(6, 6, 0);
    for (long long i = 1; i < 6; i++)
        B.m[i][i - 1] = 1;
    for (long long i = 0; i < 6; i++)
        B.m[i][5] = 1;
    A = A * (B ^ n);
    return A.m[0][0];
}

int main()
{
    long long n = 8;

    cout << throwingDice(n) << "\n";

    return 0;
}