DP with Matrix Exponentiation Concept Doubt

#1

1D DP linear recurrence formula:
f(n)=∑ci*f(n−i)+d where i=1......k

Do I have to remember this technique or it varies?

#2

@Kinjal this formula represents generalised 1D DP . So you did not have to remember this. because every question this formula will take different form.
For exmaple: for fibbonacci f(n) = f(n-1)+f(n-2)
for factorial f(n) = n*f(n-1)

#3

Okay and to solve these recurrence relations, we need to use Matrix Exponentiation…Or I could say to find the F(n)…

#4

@Kinjal no you can also use dynamic programming to solve these recurrences.

#5

so why do we use matrix exponentiation technique to solve these dp problems? for efficient time complexity or something else…

#6

@Kinjal matrix exponentiation can only be used to solve linear recurrences. We use matrix exponentiation for efficent time complexity.

#7

How matrix exponentiation technique works for linear recurrence relation?

#8

@Kinjal there is a complete video in the course for this topic.

#9

F(i) * T = F(i+1), is the relation between F(i) and Transformation matrix, T…so I mean, how multiplication of F(i) and T, (F(i) * T) will happen if F(i) is Kx1 matrix and T is KxK matrix…?

This is the link: http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

#10

Sorry…it’s
T * F(i)
But, how transformation matrix will change, is it state dependent or constant through out the process?
Like if I have to calculate per se,

F(i+2)=T*F(i+1)

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#12

Yah konsa tarika hai, doubt solve karne ka…tell me, what’s my doubt again?

#13

there are lots of chat above
could you tell me now
what’s your doubt??

#14

there are 2 ways to solve linear recurrence

  1. dynamic Programing --> used when n is small
  2. Matrix Exponentiation —> used when n is large
#15

Yeah…when n is large, we use Matrix Exponentiation and also if present state is dependent on previous state and if we can form just a recurrence formula out of the problem then we can say that present state or n’th state dependent upon previous (n-1) states or just previous state i.e. (n-1)'th state.

My doubt is, I’m trying to solve the problem called Sereja and LCM from codechef, and I did understand the task of the problem or may be not but I’m not able to get the way Sanyam bhaiya solved the problem using Matrix Exponentiation. So I just need help to understand the solution of the problem.

#16

Do we have to form transformation matrix here to solve this problem?
this is also one of my small doubt in this problem.

#17

there is a another simple approach of this problem

We have to find the possible number of arrays: A[1], A[2], A[3],…,A[N]
such that A[i] >=1 and A[i] <= M and LCM(A[1], A[2], …, A[N]) is
divisible by D.
We have to find the sum of the answers with D = L, L+1, …,R modulo
10^9 + 7.
A/Q we have to find the number of array whose LCM is a multiple of a
given number(say ‘x’).
Using negation calculate the number of arrays whose LCM is not
a multiple of x (say ‘y’).
Hence, ans = (possible array with m numbers) - y.
Note: The maximum value of the array elements can be 1000, the
maximum number of distinct prime factors possible is 4 (2 * 3 * 5 * 7 *
11 > 1000).
Let the prime factors of x be p,q,r,s
x = (p^a) * (q^b) * (r^c) * (s^d)
p^a: P
q^b: Q
r^c: R
s^d: S
To calculate y:
None of element of array have any prime factor that x has OR
it may have some of it missing
So, calculate the number of arrays such that either (P or its multiple
are not present) OR (Q or its multiple are not present) OR (R orits multiple are not present) OR (S or its multiple are not
present).
y = |not ( P ) U not(Q) U not( R) U not( S)|
Applying Principle of Inclusion-Exclusion Principle
A = power(m - m/P,n) + power(m - m/Q,n) + power(m - m/R,n
) + power(m - m/S,n);
B = power(m - m/P - m/Q + m/(PQ), n) + power(m - m/Q - m
/R + m/(QR), n)…
C = power(m- m/P -m/Q - m/R + m/(PQ) + m/(QR) + m/(P*R)

  • m/(PQR),n)…
    D = powmod(m - m/P - m/Q - m/R - m/S + m/(PQ) + m/(QR)
  • m/(PR) + m/(RS) + m/(PS) + m/(QS) - m/(PQR)- m/(Q
    RS) - m/(PQS) - m/(PRS) + m/(PQR*S),n);
    Final Answer will be:
    y = A - B + C - D
    ans = m ^ n - y
    = m ^ n - A + B - C + D

Code

#18

So, m^n is the universal set?
But tell me bhaiya, if I’m wrong…from the given problem what I have observed that,
m is the upper bound of numbers present in the array, I guess
n is the count of numbers present in the array, I guess
then what is m^n actually mean on the perspective of the problem?

#19

ans = (possible array with m numbers) - y.
m^n is total no of possible array with m number

#20

Bhaiya, what I understand, m^n from here is like,

we have to find the possible number of arrays with a N elements each in the array select from total M numbers so we can select each position M ways and there are N positions…

Mc1 and Mc1 and Mc1 and.........in N positions in the array
i.e. M*M*M.....N times
i.e. M^N

Is it correct to derive m^n?