A link to a supplementary question using game-time data: here
The explanation of the official questions is very clear, and the idea of solving the questions directly depends on the solution. I only look at solution one, so I only give the realization of solution one. The implementation code of the solution is given directly here.
Block matrix
matrix Each element is a matrix or element, consider using a template class. Performance:
p.s. Jin Le is one of my trumpets
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
struct integer
{
ll v;
integer() : v(0) {}
integer(ll x) : v(x) {}
friend integer operator + (const integer & amp;a, const integer & amp;b) { return integer((a.v + b.v) % mod); }
friend integer operator*(const integer & amp;a, const integer & amp;b) { return integer(a.v * b.v % mod); }
friend ostream & amp; operator<<(ostream & amp; os, const integer & amp; i)
{
os << i.v;
return os;
}
};
template <class t>
struct matrix
{
vector<vector<t>> a;
ll n;
matrix(const vector<vector<t>> &aa) : a(aa), n(aa. size()) {}
matrix(int nn = 2) : n(nn)
{
a = vector<vector<t>>(n, vector<t>(n));
}
friend matrix<t> operator + (const matrix<t> & amp;x, const matrix<t> & amp;y)
{
matrix<t> r = matrix<t>(x.n);
for (ll i = 0; i < x.n; + + i)
{
for (ll j = 0; j < x.n; + + j)
{
r.a[i][j] = x.a[i][j] + y.a[i][j];
}
}
return r;
}
friend matrix<t> operator*(const matrix<t> & amp;x, const matrix<t> & amp;y)
{
matrix<t> r = matrix<t>(x.n);
for (ll i = 0; i < x.n; + + i)
{
for (ll j = 0; j < x.n; + + j)
{
for (ll k = 0; k < x.n; + + k)
{
r.a[i][j] = r.a[i][j] + x.a[i][k] * y.a[k][j];
}
}
}
return r;
}
matrix<t> pow(ll k)
{
if (k == 0)
{
return matrix<t>(n);
}
if (k == 1)
{
return *this;
}
if (k % 2 == 1)
{
return *this * pow(k - 1);
}
matrix<t> r = pow(k / 2);
return r * r;
}
friend ostream & amp; operator<<(ostream & amp;os, const matrix<t> & amp;m)
{
for (ll i = 0; i < m.n; + + i)
{
for (ll j = 0; j < m.n; + + j)
{
os << m.a[i][j] << ' ';
}
os << '\\
';
}
return os;
}
};
using arr = vector<vector<integer>>;
using mat = matrix<integer>;
mat unit(ll v)
{
return mat(arr{
{v == 0 ? 0 : 1, v}, {0, v == 0 ? 0 : 1}});
}
using arr2 = vector<vector<mat>>;
using mat2 = matrix<mat>;
mat fib(ll k)
{
mat m = mat(arr{<!-- -->{0, 1}, {1, 1}});
return m.pow(k);
}
const ll mn = 52;
ll n, m, k, e[mn][mn];
signed main()
{
// freopen("3.in", "r", stdin);
// freopen("3.out", "w", stdout);
ios::sync_with_stdio(false), cin. tie(0);
cin >> n >> m >> k;
arr2 ve = arr2(n, vector<mat>(n));
for (ll u, v, w; m--;)
{
cin >> u >> v >> w;
--u, --v;
ve[u][v] = ve[u][v] + fib(w);
}
mat2 m = mat2(ve);
m = m.pow(k);
auto print = [ & amp;](mat2 m)
{
for (ll i = 0; i < n; + + i)
{
for (ll j = 0; j < n; + + j)
{
cout << m.a[i][j].a[0][1] << ' ';
}
cout << '\\
';
}
};
print(m);
return 0;
}
/*
3 5 5
1 2 1
2 1 2
1 1 3
3 3 1
2 3 4
*/
Ordinary matrix
According to the problem solution, it is transformed into
2
no
x
2
no
2n\times 2n
2n by 2n matrix. Performance:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
using arr = vector<vector<ll>>;
struct matrix
{
ll n;
arr a;
matrix(ll nn = 2) : n(nn)
{
a = arr(n, vector<ll>(n));
}
matrix(arr aa) : n(aa. size()), a(aa) {}
friend matrix operator + (const matrix & amp; x, const matrix & amp; y)
{
matrix r = matrix(x.n);
for (ll i = 0; i < x.n; + + i)
{
for (ll j = 0; j < x.n; + + j)
{
r.a[i][j] = (x.a[i][j] + y.a[i][j]) % mod;
}
}
return r;
}
friend matrix operator*(const matrix & amp; x, const matrix & amp; y)
{
matrix r = matrix(x.n);
for (ll i = 0; i < x.n; + + i)
{
for (ll j = 0; j < x.n; + + j)
{
for (ll k = 0; k < x.n; + + k)
{
r.a[i][j] = (r.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
}
}
}
return r;
}
matrix pow(ll k)
{
if (k == 0)
{
return matrix(n);
}
if (k == 1)
{
return *this;
}
if (k % 2 == 1)
{
return *this * pow(k - 1);
}
matrix r = pow(k / 2);
return r * r;
}
};
using mat = matrix;
mat fib(ll k)
{
mat m = mat({<!-- -->{0, 1}, {1, 1}});
return m.pow(k);
}
ll n, m, k;
signed main()
{
ios::sync_with_stdio(false), cin. tie(0);
cin >> n >> m >> k;
mat e = mat(n * 2);
for (ll u, v, w; m--;)
{
cin >> u >> v >> w;
--u, --v;
mat f = fib(w);
(e.a[u * 2][v * 2] + = f.a[0][0]) %= mod;
(e.a[u * 2][v * 2 + 1] + = f.a[0][1]) %= mod;
(e.a[u * 2 + 1][v * 2] + = f.a[1][0]) %= mod;
(e.a[u * 2 + 1][v * 2 + 1] + = f.a[1][1]) %= mod;
}
e = e.pow(k);
for (ll i = 0; i < n; + + i)
{
for (ll j = 0; j < n; + + j)
{
cout << e.a[2*i][2*j+1] << ' ';
}
cout << '\\
';
}
return 0;
}
/*
3 5 5
1 2 1
2 1 2
1 1 3
3 3 1
2 3 4
*/