RECURRRR - Editorial

editorial
,
1

Contest

Summer of innovation

Problem

SC and his recursion

Prerequisite

Matrix exponentiation

Statement

SC really loves recurrence relations ( the mathematical kind :wink: ). 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

Link

2

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
3

We hope you enjoyed the contest xD