# SHELBY-Editorial

Travel with Thomas

Author: vikiwarrior
Editorialist: vikiwarrior
Tester: dragno99

# PROBLEM:

There are v cities numbered from 1 to v in your country. Also, there are e roads connecting the cities. One can go from city u_i to v_i (and vice versa) using the i-th road. No two cities have more than one road connecting them. You can start your travel from any city. You need to travel n cities (not necessarily distinct).
Find the number of ways you can travel n cities.

Note: You can travel one city multiple times in a single travel. (See sample test case for better understanding)

# PREREQUISITES:

• Matrix Exponentiation

EASY - MEDIUM

# EXPLANATION:

This is a classic dynamic programming problem with matrix exponentiation.

Let M_i be a matrix of dimension [v x 1 ] with values m_1,m_2,m_3,m_4 …m_v where m_j where 1 \leq j \leq v represents the no of ways we can travel i nodes with j being the last node of the travel.

Initially, M_1 would be a [v x 1 ] matrix with all values equal to 1 as there is only one way per vertex to travel one node.

You can see the following recursion being formed :

M_{i+1} = A * M_i

Here, A is the adjacency matrix of dimension [v x v ].

As n is huge we cannot normally calculate M_n. The complexity of such implementation is O(v*v*n).

To optimize this observe that we can also write M_i as M_i = A^{i-1} * M_1 when i \le 2

Now , we just need to compute A^n fast for this we use matrix exponentiation. The complexity now will be O(v*v*v* \log(n)) which will run fine given the time constraints.

See setter and tester codes for implementation.

# SOLUTION:

Setter's Solution in C++
//vikiwarrior - Vikrant Kumar

#include "bits/stdc++.h"

using namespace std;

#define int long long

#define pb push_back

#define ppb pop_back

#define pf push_front

#define ppf pop_front

#define all(x) (x).begin(), (x).end()

#define uniq(v) (v).erase(unique(all(v)), (v).end())

#define sz(x) (int)((x).size())

#define fr first

#define sc second

#define pii pair<int, int>

#define rep(i, a, b) for (int i = a; i < b; i++)

#define mem1(a) memset(a, -1, sizeof(a))

#define mem0(a) memset(a, 0, sizeof(a))

#define ppc __builtin_popcount

#define ppcll __builtin_popcountll

template <typename T1, typename T2>

istream &operator>>(istream &in, pair<T1, T2> &a)

{

in >> a.fr >> a.sc;

return in;

}

template <typename T1, typename T2>

ostream &operator<<(ostream &out, pair<T1, T2> a)

{

out << a.fr << " " << a.sc;

return out;

}

template <typename T, typename T1>

T amax(T &a, T1 b)

{

if (b > a)

a = b;

return a;

}

template <typename T, typename T1>

T amin(T &a, T1 b)

{

if (b < a)

a = b;

return a;

}

const long long INF = 1e18;

const int32_t M = 1e9 + 7;

const int32_t MM = 998244353;

const int N = 0;

const int MOD = 1e9 + 7;

const long long MOD2 = static_cast<long long>(MOD) * MOD;

struct Matrix

{

vector<vector<int>> mat;

int n_rows, n_cols;

Matrix() {}

Matrix(vector<vector<int>> values) : mat(values), n_rows(values.size()),

n_cols(values[0].size()) {}

static Matrix identity_matrix(int n)

{

vector<vector<int>> values(n, vector<int>(n, 0));

for (int i = 0; i < n; i++)

values[i][i] = 1;

return values;

}

Matrix operator*(const Matrix &other) const

{

int n = n_rows, m = other.n_cols;

vector<vector<int>> result(n_rows, vector<int>(n_cols, 0));

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

{

long long tmp = 0;

for (int k = 0; k < n_cols; k++)

{

tmp += mat[i][k] * 1ll * other.mat[k][j];

while (tmp >= MOD2)

tmp -= MOD2;

}

result[i][j] = tmp % MOD;

}

return move(Matrix(move(result)));

}

inline bool is_square() const

{

return n_rows == n_cols;

}

};

Matrix pw(Matrix a, int p)

{

Matrix result = Matrix::identity_matrix(a.n_cols);

while (p > 0)

{

if (p & 1)

result = a * result;

a = a * a;

p >>= 1;

}

return result;

}

void solve()

{

int v, e, n;

cin >> v >> e >> n;

vector<vector<int>> m(v, vector<int>(v, 0));

for (int i = 0; i < e; i++)

{

int u, v;

cin >> u >> v;

m[u - 1][v - 1] = 1;

m[v - 1][u - 1] = 1;

}

vector<vector<int>> col(v, vector<int>(1, 1));

int sum = 0;

Matrix result = pw(m, n - 1) * col;

for (int i = 0; i < v; i++)

sum = (sum + result.mat[i][0]) % MOD;

cout << sum << endl;

}

signed main()

{

int t;

cin>>t;

for(int i=1;i<=t;i++)

{

solve();

}

return 0;

}

Tester's Solution in Python
def TwoD(a, b, val):
lst = [[val for col in range(b)] for col in range(a)]
return lst

mod = int(1000000007)

def mul(a , b , v):
c = TwoD(v , v , 0)
for i in range(v):
for j in range(v):
for k in range(v):
c[i][j] += a[i][k] * b[k][j]
c[i][j] %= mod
return c

for _ in range(int(input())):
v,e,n = map(int,input().split())
a = TwoD(v , v , 0 )
for j in range(e):
x,y = map(int,input().split())
x -= 1
y -= 1
a[x][y] = 1
a[y][x] = 1

n -= 1
res = TwoD(v , v , 0)
for i in range(v):
res[i][i] = 1
while n > 0 :
if n % 2 > 0:
res = mul(res , a , v)
a = mul(a , a , v)
n //= 2
ans = 0
for i in range(v):
for j in range(v):
ans += res[i][j]
ans %= mod
print(ans)