PROBLEM LINK:
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
DIFFICULTY:
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.
More about matrix exponentiation.
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)