PROBLEM LINK:
Author: ashwanth2003
Tester: manoj_vajpeyi
Editorialist: ashwanth2003
DIFFICULTY:
MEDIUM
PREREQUISITES:
Adjacency Matrix Properties, Matrix Exponentiation
PROBLEM:
Given two numbers A, B and the number of operations P, you need to determine the number of ways to perform P operations to convert A to B modulo 10^9+7
The operations are defined as follows:
- multiply by 2
- multiply by 4
- divide by 2
- divide by 4
- add 1
- subtract 1
After every operation, the number A should lie between 1 to 10 inclusive.
QUICK EXPLANATION:
- Convert this problem into a graph problem with edge-weights as cost and do matrix exponentiation
EXPLANATION:
-
This problem can be modeled as a graph problem keeping each number {1 ā¦ 10} as nodes and the operations as edges (Note: parallel edges may exist)
-
Corner cases for parallel edges:
- 1 ā 2 (multiply by 2 or add 1)
- 2 ā 1 (divide by 2 or subtract 1)
-
Our ultimate goal is to find the number of paths from A to B with fixed path length P.
-
There is an exciting property with the adjacency matrix of a graph
-
A^p[i][j] = number of paths from node i to node j with length exactly P
-
I like to leave out the proof of this property as an exercise (hint: induction)
-
The adjacency matrix of our problem looks like this
-
\left[\begin{array}{lll}
0&2&0&1&0&0&0&0&0&0\\
2&0&1&1&0&0&0&1&0&0\\
1&1&0&1&0&1&0&0&0&0\\
1&1&1&0&1&0&0&1&0&0\\
1&1&0&1&0&1&0&0&0&1\\
1&0&1&0&1&0&1&0&0&0\\
1&0&1&0&0&1&0&1&0&0\\
0&1&0&1&0&0&1&0&1&0\\
0&1&0&1&0&0&0&1&0&1\\
0&1&0&0&1&0&0&0&1&0\\
\end{array}\right]
-
\left[\begin{array}{lll}
0&2&0&1&0&0&0&0&0&0\\
2&0&1&1&0&0&0&1&0&0\\
1&1&0&1&0&1&0&0&0&0\\
1&1&1&0&1&0&0&1&0&0\\
1&1&0&1&0&1&0&0&0&1\\
1&0&1&0&1&0&1&0&0&0\\
1&0&1&0&0&1&0&1&0&0\\
0&1&0&1&0&0&1&0&1&0\\
0&1&0&1&0&0&0&1&0&1\\
0&1&0&0&1&0&0&0&1&0\\
\end{array}\right]
-
Since the constraints for P are very large, we could think of matrix exponentiation to solve our problem
ALGORITHM:
- Step 1: convert into a graph problem
- Step 2: generate an adjacency matrix of size 10 x 10 for the graph
- Step 3: raise the Adjacency matrix to power P using matrix exponentiation modulo 10^9+7
- Step 4: A^p[i][j] contains the number of paths from node i to node j with length P
TIME COMPLEXITY
O\left(Q \cdot 10^3 \log \left(10^{18}\right)\right)
= 150 \times 10^3 \times \log \left(10^{18}\right)
= 10^7
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<pair<lli , lli>> vpll;
typedef vector<pair<ld , ld>> vplld;
typedef pair<int,int> pii;
typedef vector<lli> vl;
typedef pair<lli,lli> pll;
typedef priority_queue<lli> pq;
typedef priority_queue<pair<lli,lli>> pqp;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define print(a) for(auto x:a) cout<<x<<" ";cout<<endl;
#define printarr(a , n) for(int i = 0 ; i < n ;i ++) cout << a[i] << " "; cout << endl;
#define inf 1e18
//
// matrix exponentiation on adjacency matrix
//
struct mat
{
lli mat[10][10];
};
struct mat adjmat;
struct mat idenmat;
struct mat zeromat;
int reached(lli i , lli j)
{
int count = 0;
if(i*2 == j) count++;
if(i/2 == j) count++;
if(i+1 == j) count++;
if(i-1 == j) count++;
if(i*4 == j) count++;
if(i/4 == j) count++;
return count;
}
void construct()
{
for(int i =0 ; i < 10 ; i ++) for(int j = 0; j < 10 ; j ++) adjmat.mat[i][j] = 0;
for(int i = 1 ; i <= 10 ; i ++)
{
for(int j = 1 ; j <= 10 ; j ++)
{
adjmat.mat[i-1][j-1] = reached(i , j);
}
}
for(int i =0 ; i < 10 ; i ++) for(int j = 0; j < 10 ; j ++) idenmat.mat[i][j] = (i == j);
for(int i =0 ; i < 10 ; i ++) for(int j = 0; j < 10 ; j ++) zeromat.mat[i][j] = 0;
}
void printmat(struct mat a)
{
for(int i = 0; i < 10 ; i ++)
{
for(int j = 0 ;j < 10 ; j ++)
{
cout << a.mat[i][j] << " ";
}
cout << endl;
}
}
lli mod = 1e9 + 7;
struct mat mul(struct mat a , struct mat b)
{
struct mat c;
for(int i = 0 ; i < 10 ; i ++)
{
for(int j = 0 ; j < 10 ; j ++)
{
c.mat[i][j] = 0;
for(int k = 0 ; k < 10 ; k ++)
{
c.mat[i][j] += (a.mat[i][k]*b.mat[k][j])%mod;
c.mat[i][j] %= mod;
}
}
}
return c;
}
struct mat power(struct mat x, lli n) //x base n exponent
{
if(n==0) return idenmat;
struct mat pow = idenmat;
while(n)
{
if (n & 1)
pow = mul(pow,x);
n = n >> 1;
x = mul(x,x);
}
return pow;
}
void solve()
{
lli a , b , p;
cin >> a >> b >> p;
struct mat ans = power(adjmat,p);
cout << ans.mat[a-1][b-1] << endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
construct();
int t;cin>>t; while(t--)
solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define int long long int
const int mod = 1e9 + 7;
const int inf = 5e18;
//const int mod = 998244353;
using namespace std;
vector<vector<int>> mul(vector<vector<int>>mat1,vector<vector<int>>mat2)
{
int n=10;
vector<vector<int>>res(n,vector<int>(n,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int ele=0;
for(int k=0;k<n;k++)
{
ele+=mat1[i][k]*mat2[k][j];
ele%=mod;
}
res[i][j]=ele;
}
}
return res;
}
vector<vector<int>> pow(vector<vector<int>>mat,int p)
{
int n=10;
vector<vector<int>>res(n,vector<int>(n,0));
for(int i=0;i<n;i++) res[i][i]=1;
while(p)
{
if(p%2) res=mul(res,mat);
p=p/2;
mat=mul(mat,mat);
}
return res;
}
void myfun()
{
int a,b,n;
cin>>a>>b>>n;
vector<vector<int>>mat(10,vector<int>(10,0));
for(int i=0;i<10;i++)
{
int cur=i+1;
int nex;
nex=cur+1; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur-1; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur/2; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur/4; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur*2; if(nex>0 && nex<11) mat[i][nex-1]+=1;
nex=cur*4; if(nex>0 && nex<11) mat[i][nex-1]+=1;
}
mat=pow(mat,n);
cout<<mat[a-1][b-1]<<"\n";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("input0.txt", "r", stdin);
//freopen("output0.txt", "w", stdout);
int t = 1;
cin >> t;
while (t--)
myfun();
return 0;
}