 # Matrix exponentiation

Given recurrence:
f(n) = n * f(n-1) + (n-1) * f(n-2)

How to find f(n) using matrix exponentiation ?

1 Like

I’m open to corrections but I don’t quite think this is a linear sequence so applying matrix exponentiation is not possible. However, we can apply iterative dp instead.

Are there any base values ?? I mean, f(0) = k or f(c) = k, c & k being constant.

Not sure about matrix exponentiation but the solution of the recursion is:
f(n) = k*(n+2)*n! for some constant k
Note that there is no matrix exponentiation way of finding n! so you can’t find f(n) using it. But there is an O(n^{1/2}) algorithm for finding n! if n is very large(of order 10^{12})

@waqar_ahmad224 Can you answer this?

Take n common from R.H.S
f(n)=n*[ f(n-1) + f(n-2)] - f(n-2)
you can see something familiar f(n-1) +f(n-2) ie recurrence relation of fibonacci numbers you can calculate it in O(log n) time and same goes for f(n-2)
I’m not sure that this is right or not , but I tried ,I hope it helps

I am interested in that, can you suggest some source to read about it? Are we talking about (n!\%prime) or is an approximation algorithm?

The complexity is a bit higher, here is the source:
http://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/
I think the complexity analysis mentioned in the source is wrong, it should be O(n^{1/2} \cdot log^2n)
It’s n! modulo prime where prime is big(of order 10^9)

1 Like

I still wonder if there is any O(n) algorithm for n! for large n (obviously without mod\ prime).
( factorial of 10^9 has 8565705523 digits. )

If you won’t take modulo prime, then n! has O(n*log(n)) digits, so it’s not possible to store it for large n, but if you take modulo prime also then you have algorithms for small prime(https://cp-algorithms.com/algebra/factorial-modulo.html)
But suppose the mod is (10^9+7) or 998244353 or some other modulo of this range then FFT can be used.
In competitive programming you take modulo for even 25!
From starting only, I was thinking that we need to find f(n) modulo some prime(where prime is big)

It’s log10(n!), I guess.

Yes, that was the point that without \%p there is even no O(n) solution.
For large n we can calculate n!\%p with complexity of O(p^{1/2} log(p)^2) using FFT.

I gave the asymptotic space complexity, the exact would be 1 + floor[log10(n!)], but when talking about asymptotic complexity log(n!) is O(n*log(n))

Here is my solution it is giving wrong and can anybody tell me what i am doing wrong ???

Question — https://cses.fi/problemset/task/1096 My Solution — https://ideone.com/sE6Pgm

You should explain your solution, I got the following recursion:
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4) + f(n-5) + f(n-6), with initial values as follows:
f(1) = 1, f(2) = 2, f(3) = 4, f(4) = 8, f(5) = 16, f(6) = 32
Now it’s just matrix exponentiation.