TASKSELECT ( Đề thi) Automata Aproach

#include <iostream>
#include <cstdio>
#include <cstring>
#define task "TASKSELECT"

using namespace std;
using ll = long long;

const int N = 122 + 2;
const ll mod = 1e9 + 7;
int k, n;
struct Matrix
{
    ll a[N][N];
    Matrix()
    {
        memset(a, 0, sizeof a);
    }
    Matrix operator * (const Matrix &x)
    {
        Matrix ans;
        for(int i = 0; i <= (k + 1) * (k + 1); ++i)
            for(int j = 0; j <= (k + 1) * (k + 1); ++j)
                for(int h = 0; h <= (k + 1) * (k + 1); ++h)
                    (ans.a[i][h] += a[i][j] * x.a[j][h]) %= mod;
        return ans;
    }
};

Matrix Pow(Matrix &a, int b)
{
    Matrix ans;
    for(int i = 0; i < N; ++i)
        ans.a[i][i] = 1;
    for(; b > 0; b >>= 1)
    {
        if(b & 1)
            ans = ans * a;
        a = a * a;
    }
    return ans;
}


void Read()
{
    cin >> k >> n;
}

void Solve()
{
    int l = k;
    Matrix a;
    a.a[0][1] = 1;
    for(int i = 1; i <= k; ++i)
    {
        for(int j = 1; j < i; ++j)
        {
            ++l;
            if(j == 1)
                a.a[i][l] = 1;
            else
                a.a[l - 1][l] = 1;
        }
        if(i != 1)
            a.a[l][i] = 1;
        else
            a.a[i][i] = 1;
        if(i < k)
        {
            for(int j = 1; j <= i; ++j)
            {
                ++l;
                if(j == 1)
                    a.a[i][l] = 1;
                else
                    a.a[l - 1][l] = 1;
            }
            a.a[l][i + 1] = 1;
        }
    }
    a = Pow(a, n);
    cout << a.a[0][k] << "\n";
}

int32_t main()
{
    if(fopen(task".INP", "r"))
    {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        Read();
        Solve();
    }
}