# RECURRRR - Editorial

## Contest

Summer of innovation

## Problem

SC and his recursion

## Prerequisite

Matrix exponentiation

## Statement

SC really loves recurrence relations ( the mathematical kind ). He has made his own new reccurence relation. The relation is given by:
F(N)=A∗F(N−1)+N. F(0) is always equal to 1.

You are given T test cases, each test case has an input A and Q. For each test case, you are given Q queries, each query contains one number q. You have to find F(q). Can you find that?

Since the output can be very large, output the answer modulo 1000000007

## Explanation

This question is a very standard problem involving Matrix Exponentiation.
This blogpost on Codeforces is a very neat tutorial that will help you solve this question.

## Setter’s Solution

There is a mathematical solution too, which doesn’t involve matrix exponentiation.
Lets see the series-
F(0)=1
F(1)=A.F(0)+1=A+1
F(2)=A.F(1)+2=A(A+1)+2=A^2+A+2
...
F(N)=A.F(N-1)+N=A^N+A^{N-1}+2A^{N-2}+3A^{N-3}+...+NA^0
this can be written as
F(N)=A^N+N+ \sum_{i=1}^{N-1} \sum_{j=1}^{i}A^j
now \sum_{j=1}^{i}A^j is a simple GP which can be written into \frac{A(A^i-1)}{A-1}

\sum_{i=1}^{N-1} \sum_{j=1}^{i}A^j

=\frac{A(A-1)}{A-1} +\frac{A(A^2-1)}{A-1} +....+\frac{A(A^{N-1}-1)}{A-1}

=\frac{A}{A-1}[\frac{A^{N-1}-1}{A-1}.A-(N-1)]

=\frac{A.(A^N-A.N+(N-1)}{(A-1)^2}

thus finally F(N)=A^N+N+\frac{A.(A^N-A.N+(N-1)}{(A-1)^2}

now the drawback of this version is it doesn’t work for A=1, which can however be easily calculated.
Its value is \frac{N.(N+1)}{2}+1

My AC impementation here.

2 Likes

We hope you enjoyed the contest xD