Linear Recurrence : Introduction

Fibonacci Sequence is one of the simplest examples of a linear recurrence: $$$F_x = F_{x-1} + F_{x-2}$$$, with $$$F_0 = 0, F_1 = 1$$$

Here is a more general example of a linear recurrence:

\begin{align} R_{x} = \sum_{i=1}^{n}{C_i \cdot R_{x-i}} \end{align}

where $$$C_i$$$ is constant and $$$R_x$$$ is the x-th term of the recurrence. Since $$$R_x$$$ depends on the previous $$$n$$$ terms of the recurrence, it is called a linear recurrence of order $$$n$$$. It is called a "Linear" Recurrence, since we do not have any terms of the type $$$R_x \cdot R_y$$$

Note: We need $$$n$$$ initial conitions for a linear recurrence of order $$$n$$$, for example, we have 2 initial conditions for the Fibonacci Sequence.

Iternary

In this blog we will learn about various methods of solving the following problem: Given a Linear Recurrence of order $$$N$$$, find the $$$K$$$-th term of the recurrence. There are various methods to do this:

• $$$O(N \cdot K)$$$ using DP
• $$$O(N^3 \cdot logK)$$$ using Matrix Exponentiation
• $$$O(P(n) \cdot logK)$$$ using Characterstic Polynomials where $$$P(n)$$$ is the time required for polynomial multiplication — which can be $$$O(N^2)$$$ naively or $$$O(N^{1.58})$$$ using Karatsuba Multiplication or $$$O(N logN)$$$ using Fast Fourier Transform.

DP Solution

The $$$O(N \cdot K)$$$ solution is pretty trivial. (Assume dp[0] .. dp[n-1] are stored correctly as initial conditions)

for(int i = n; i < k; i++){
    dp[i] = 0;
    for(int j = 1; j <= n; j++){
        dp[i] += c[j] * dp[i - j];
    }
}

Matrix Exponentiation

You can find more detailed explanations on this technique here and here. But here I've described it briefly:

Let's look at the problem from another angle. From the DP solution, it is clear that we need to keep track of the previous $$$n$$$ elements at all times, and it won't matter even if we "forget" other elements. So let's keep a column vector of the "current" $$$n$$$ consecutive elements. Since the recurrence relation is a Linear Relation, it is possible to have a linear transformation to get the next elements.

Finding this linear transformation is quite intuitive and it can be expressed as multiplication with a square matrix, so let's directly write the general result.

Reader is advised to take a moment to manually mutliply the matrices and verify the above result for a better understanding.

Alright, so a multiplication with the Transformation Matrix shifts the elements of the vector by $$$1$$$ index each, so we can shift it by $$$X$$$ indices by multiplying the transformation matrix to it $$$X$$$ times. However we take advantage of the fact that we can first multiply the transformation with itself $$$X$$$ times and then multiply it with the column vector. Why is this advantageous? Because we can use Binary Exponentiation! If we the transformation matrix is $$$T$$$, we can find $$$T^X$$$ in $$$O(N^3 logX)$$$ time. This lets us get the K-th term in $$$O(N^3 logK)$$$ time.

Check out this Mashup for practice problems

Using Characterstic Polynomial

I might've over-explained this section of the blog, because I personally found it very hard to understand this part when I initally learnt it.

I learnt about this technique from TLE's blog on Berlekamp Massey Algorithm, but since it wasn't explained in detail, I had a lot of difficulty in understanding this, so I'll try to explain it in a more beginner-friendly way. Apparently the name of this trick is Kitamasa Method.

First of all, an important observation

The original recurrence can be re-written as:

\begin{align} R_{j}-\sum_{i=1}^{n}{C_i \cdot R_{j-i}} = 0 \end{align}

Which means, any multiple of $$$\left(R_{j}-\sum_{i=1}^{n}{C_i \cdot R_{j-i}}\right)$$$ is $$$0$$$ and if it is added or subtracted anywhere, the answer doesn't change.

Let's bring in Polynomials

In simple words, in the linear recurrence, replace $$$R_{i}$$$ with $$$x^i$$$ everywhere to a get a polynomial equation. Multiplying $$$x$$$ to every element of the polynomial would just mean adding $$$1$$$ to all the subscripts in the linear recurrence. It is quite obvious to see that adding or subtracting such polynomial equations is also allowed. "Allowed? For what?" — For converting the polynomial back to the recurrence! Yes! This is a bit magical.

Try to check it on a few cases manually to verify that it is always allowed to do the following:

• Convert the linear recurrence into polynomial equation
• Add/Subtract/Multiply the polynomial equation with $$$x$$$ or some constants
• Convert the polynomial back to linear recurrence (replace $$$x^i$$$ with $$$R_{i}$$$ everywhere)

The final equation that you get after this, will be valid.

Alright, so what now? Let's convert the original recurrence into a polynomial (It is called the Characterstic Polynomial of the Reccurence)

\begin{align} f(x) = x^n-\sum_{i=1}^{n}{C_i \cdot x^{n-i}} \end{align}

Now since we know that upon converting the characterstic polynomial back to recurrence form, its value will be 0. We take advantage of this — Any multiple of the characterstic polynomial can be added or subtracted without any effect on the result.

We want to find $$$R_K$$$, upon converting it to polynomial we get $$$x^K$$$

We wish to find $$$\left(x^K + m(x) \cdot f(x)\right)$$$, where $$$m(x)$$$ is any polynomial! (Since $$$f(x)$$$ will be $$$0$$$ upon converting back to recurrence)

Now the idea is simple, we choose $$$m(x)$$$ in such a way that, only terms with degree less than $$$n$$$ remain. To do so, we pick, $$$m(x)$$$ as the negative of the quotient when $$$x^K$$$ is divided by $$$f(x)$$$. Which eventually leaves us with $$$x^K$$$ $$$mod$$$ $$$f(x)$$$

Hence the final solution

Find $$$x^K$$$ $$$mod$$$ $$$f(x)$$$ and then convert it to recurrence, which will have only terms $$$R_0, R_1, \cdots, R_{n-1}$$$

They way to do this is:

• Figure out how to calculate poly mod poly. (remainder when a polynomial is divided by another polynomial)
• Use binary exponentiation to find $$$x^K$$$ $$$mod$$$ $$$f(x)$$$

It is easy to see that there will be $$$O(logK)$$$ steps, with each step involving poly mod poly.

Hence using FFT, this can be done in $$$O(N logN logK)$$$

"Wait! You didn't tell how to do Poly mod Poly!"

Now, I won't be explaining how to do Poly mod Poly, because it is pretty easy to do naively in $$$O(N^2)$$$, and very complex using FFT in $$$O(N logN)$$$ — You can read about it here.

However, you can just use Poly mod Poly as a black box and use this code library by adamant (Although it is not very optimized, but it is good for basic use)

Practice Problems

RNG Codechef

You can also try the problems from the matrix exponentiation mashup using this technique, but it'll be an overkill.

Special Thanks to coder_ravan_01 who claims to be the 6969th friend.

So long story short, Problemset got renamed to Bugabooset. (Full story if you're interested)

Don't get me wrong, I personally find it extremely amazing, but I still want this change to be reverted.

I have some valid reasons:-

• Whenever some newcomer asks me for advice... I say something like, "Go to the Codeforces Problemset and sort the problems by difficulty and then solve a few everyday", now recently what is happening is that, a lot of newcomers can't find the problemset (because it does not exist anymore!!).
• If I tell them to go to the bugabooset, they will ask me what is that and what it means, and that's one story that I do not want to explain to someone for the 348th time!
• The link still points to "http://codeforces.net/problemset", I think this discrepancy is very confusing... Now some might say, we can change it to "http://codeforces.net/bugabooset" but that'll unnecessarily ruin many people's bookmarks (unless old links redirect to the new ones, ok yeah, this one is a moot point tbh)
• Regarding the problem vs question debate: The actual victims are pretty much unaffected by this change. My point is- If they called them "questions" when "problemset" existed, what makes you think they will call them "bugaboos" now? They won't! They'll still call it "question" and many people will still call it "problem" and only the few woke people will call it "bugaboo".
• I can foresee that somewhere in the future, some Legendary Grandmaster might write a blog saying that people who say "bugaboo" have high ratings and people who say "question" or "problem" don't. So this solution, isn't really a solution at all... It'll just cause even more problems(or more bugaboos idk).
• Lastly, and this one is the only actual valid reason (and also the only reason that was required): IT IS EXTREMELY CONFUSING to the newcomers, they have no clue what all this means. I agree it's extremely hilarious and I appreciate it, but most of us (except maybe a few geneosities) are at least 10 years old! And this type of a joke HAS TO get old someday or the other.

LATEST EDIT: The channel is created, read more in my new blog.

EDIT: I have decided I'm going to start the channel. If you want videos on some specific topics or editorials of some famous questions, please mention them in the comment section below.

Hello everyone,

I see a lot of content in russian or chinese language that gets translated or rewritten in english and then it gets introduced to the world. I believe that in my country (India), there are people who aren't very familiar with English either. I actually know a few people who are sometimes unable to understand blogs and editorials because of being weak in English. Even some of the people who understand English pretty well might feel more comfortable with Hindi.

Now I know that English is a pretty standard language and people should be good at it, but I still believe that Hindi videos would actually be helpful to some people, although I'm not very sure, that's why I wrote this blog.

Should I start a youtube channel in which I make videos about algorithms and/or problem solutions in Hindi? I have a few nice topics in mind.

Please comment your opinions/suggestions (your suggestions are valuable even if you can't speak/understand Hindi)

I was implementing a Trie for Google Kickstart earlier today and the code is malfunctioning in a very strange way. I have no idea why this is happening. I narrowed down the problem in a few hours.

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b)        for(int i=a;i<b;i++)

struct node{
	int ends=0;
	int child[26]={0};
};

vector<node> trie;
int makenode(){
	trie.push_back(node());
	int x=(int)trie.size() - 1;
	cout<<x<<" ";
	return x;
}

void insert(string &s,int root=0,int pos=0){
	if(pos==(int)(s.size())){
		trie[root].ends++;
		return;
	}
	int next=s[pos]-'A';
	if(!trie[root].child[next]){
		// trie.push_back(node()); trie[root].child[next]=(int)trie.size()-1;    //THIS LINE WORKS FINE
		trie[root].child[next]=makenode();
		cout<<trie[root].child[next]<<"\n";
	}
	insert(s,trie[root].child[next],pos+1);
}

int main(){
	trie.clear();
	trie.push_back(node());
	string s;
	cin>>s;
	insert(s);
	return 0;
}

The function makenode() returns x. When I print x, the values are fine but after returning the values are getting changed.

One would expect the above code to print the same integers per line but the values aren't same.

These are the values of x before and after returning from the function makenode().

Does anybody have any idea why this is happening?

(I have noticed that only the values 1,2,4,8,16,32,etc are wrong)

There's another simple greedy solution to the problem using dfs trees.

First form a dfs tree of the graph with any vertex as its root. Now consider a vertex $$$P$$$ which has a backedge to vertex $$$Q$$$, if $$$depth(P)-depth(Q)+1 >= \lceil\sqrt{n}\rceil$$$ then we have found a cycle of at least $$$\lceil\sqrt{n}\rceil$$$ vertices.

If we cannot find such a cycle, we'll find an independent set, we know that the leaves of a dfs tree do not have an edge between them. So we'll take all the leaves in the independent set. But that may not be enough we need more vertices, so we'll choose each such vertex whose depth is at least $$$\left(\lceil\sqrt{n}\rceil - 1\right)$$$ less than the minimum depth of all the chosen vertices in it's subtree and insert it to the independent set (we can do so because if there is an edge between the current vertex and any of the previously chosen vertices, we would have found a cycle). How can we say that such an independent set will have at least $$$\lceil\sqrt{n}\rceil$$$ vertices? Here is an intuitive proof:-

Consider any linear chain in the dfs tree of length $$$L$$$ which terminates at a single leaf, we can pick $$$\lceil\frac{L}{\sqrt{n}}\rceil$$$ vertices from this chain. Whenever we put a vertex in the independent set, we can disconnect its entire subtree from the graph and consider it as a new leaf. After this we can select any other linear chain and repeat this process.

In total, we'll have $$$\sum{\lceil\frac{L}{\sqrt{n}}\rceil}$$$ vertices in our independent set which is at least $$$\lceil\frac{n}{\sqrt{n}}\rceil = \lceil\sqrt{n}\rceil$$$ (since $$$\sum{L} = n$$$).

I'd appreciate if someone can come up with a more concrete proof.

Here is my accepted solution: https://codeforces.net/contest/1325/submission/73328247