After grasping the basic method of solving linear recurrence, let’s apply it in real problems.

This is a classical problem that is directly solvable using the basic method I explained in the previous post. It is expected that you solve this problem and master the basic method before solving the next problems.

**SPOJ Recursive Sequence (Version II)**

A slightly harder version of the previous problem. This time, instead of determining , we have to determine .

Let’s simplify the problem first, using a well-known technique called partial sum. Define a series , where , with . Then, the result we are looking for is exactly (prove that). So, instead of determining (n – m + 1) terms of sequence , it is sufficient to determine only two terms of series .

How to compute S? The crucial observation is that , i.e., S itself is a linear recurrence! So, we can adopt the matrix equation of a to incorporate S. The final matrix equation of would look like this:

,

with initial values:

.

After finding the matrix equation, and can be computed easily: is the first row of , and is the first row of .

You may also want to solve SPOJ Fibonacci Sum. It uses exactly the same idea.

As an example, assume that N = 4. Let

- A
_{i}= the current number of cow i, - B
_{i}= the number of cow i in the next iteration.

From the story, we know that the next number of a cow is the sum of all other cows’ current numbers. In other words,

B_{1} = A_{2} + A_{3} + A_{4}.

B_{2} = A_{1} + A_{3} + A_{4}.

B_{3} = A_{1} + A_{2} + A_{4}.

B_{4} = A_{1} + A_{2} + A_{3}.

We have N = 4 recurrence relation here, and all are related. This is essentially not harder than solving with basic method. To show this, rewrite the equations in matrix form:

,

If we define A_{i, j} as the number of cow i in the j-th iteration, with A_{i, 0} = C_{i} (the starting number of cow i), then the above equation can be rewritten as:

.

The equation looks like what we did with the basic method, right? So, the problem is solved. Let X = the number of iterations the process is performed. The number of all cows can be found by computing:

.

Also solve SPOJ Life Game.

**SPOJ Number of Quite Different Words**

Let’s try to attack a problem where the recurrence relation is not so obvious.

In this problem, we would like to count the number of strings of length N that are quite different from W, i.e. have no common subsequence of length greater than 1 with W. The strings only use the first C letters of the alphabet. Consider one such string. The string will not have any subsequence of length two, or else it will not be quite different (as 2 > 1). This condition is sufficient. So, to construct a string that is quite different, we can place the letters one-by-one from left to right, each time ensuring that the current letter doesn’t form a pair with any previous letter that occurs as a subsequence of length two in W.

For example, let W = “ABC”. The forbidden pairs for this case are AB, AC, and BC.

We will first solve this problem with dynamic programming. Let dp[i][mask] be the number of strings of length **i** that are quite different with W, and all letters that occur in the strings are contained in **mask**. The set of “used” letters are represented with a bitmask that ranges from 0 to 2^{K}-1.

The base cases are, obviously, dp[0][0] = 1 and dp[0][x] = 0 for **x** greater than 0.

Now we will define the recurrence. How many strings of length** i** that are quite different are there, and only use the letters in **mask**? The strings are built from strings of length (**i**-1) that are quite different, using only letters in **prev **(the number of such strings is dp[i-1][prev]), plus a new character **a**, where **prev** + {**a**} = **mask**. In addition, **a** must not form a “forbidden pair” with any letter in **prev**.

In other words,

,

where **a _{prev}** is the number of “valid” letters, i.e. number of letters

**a**such that

**a**does not form a forbidden pair with any letter in

**prev**, and

**prev**+ {

**a**} =

**mask**.

The recurrence above is linear, so we can transform it into the method that we have learned before, exactly the same way as SPOJ Summing Sums. We have to determine matrix T such that

,

and proceed the solution as usual. The answer is then .

—

Have another problems that can be solved using linear recurrence? Please, share with us in the comment section.

hi fushar,

can problems like http://acm.hdu.edu.cn/showproblem.php?pid=2971 solved by this method?

Hi, 3haboys. I’ll think about this problem. If there are readers that can solve this problem, please share ðŸ™‚

Wow! What a nice writing you have here. Two thumbs up! ðŸ˜€

Google Code Jam 2008 round 1A, problem C, (Numbers, http://code.google.com/codejam/contest/dashboard?c=32016#s=p2) could also be solved using this method.

Can you provide any hints for solving the following spoj problem? http://www.spoj.com/problems/ASUMHARD/

Thanks

Thank you very much man,

ur blog gave me confidence in solving recurrence problem

Thank u very very much

I think your solution for problem “Summing Sums” will get TLE verdict, for N can be quite large (N<=50000) CMIIW~

Your solution for “Summing Sums” has complexity O(N^3*logT), which will give TLE as N<=50000