## PROBLEM LINK:

Contest

Practice

**Author:**Tapish Pratap Singh

**Tester:**Arnab Samanta

**Editorialist:**Tapish Pratap Singh

## DIFFICULTY:

Hard

## PREREQUISITES:

Math, Combinatorics, Pascal Triangles

## EXPLANATION:

The sequence in the question is the generalisation of Moessner sequencce. In Moessner sequence d_1=d_2=........d_{m-1}=d_{m}.

Consider N=8, m=2, d_1=d_2=4

As we can observe every group satisfy the Pascal property (each interior element is the sum of the elements immediately above it and to its left).

Lets add a new row and column of 1’s in the first group.

*Pascal Traingle*

Similarly for Second group add a new row of 1’s and a column containing previously marked numbers,

Now we will represent the above sequence algebraically using Pascal triangle.

Let h_k(x,y) be the algebraic representation of the kth triangle.

So, h_k(x,1) will be the polynomial having coefficients as the marked numbers for the kth triangle then,

Each triangle is obtained from the previous by taking the homogeneous component of degree diff_k, and multiplying by ∆(x,y) and then putting y=1 in the obtained triangle.

h_{k+1}(x,y)=[h_k(x,1)*∆(x,y)]_{d_k} and h_0(x,1)=1 where d_k is the size of group k and

∆(x,y) =\frac{1}{1-(x+y)}=(x+y)^0+(x+y)^1+(x+y)^2+...=\sum_{d=0}^{\infty}(x+y)^d

(Note:-∆(x,y) is the algebraic representation of pascal triangle.

The nth north-east to south-west row of the pascal triangle will be:-

[[\Delta(x,y)]_{n-1}]_{y=1}=(1+x)^{n-1})

which simplifies to

h_k(x,1) = \prod_{i=0}^{k-1}((k-i)*x+1)^{diff_i}) where diff_i=d_i-d_{i-1} and d_0=0

Now what we require is the sum of all marked numbers in the original group which is:h_k(x,1)-1 (subtracting 1 as we added the rows of 1’s ,so 1 needed to be subtracted)

Final ans:-

\sum_{k=1}^{m}(h_k(x,1)-1)

Eg:-

Consider n=4,m=2,d_1=d_2=2

now h_0(x,1)=1

now

h_1(x,y)=[h_0(x,1)*∆(x,y)]_2=[1*((x+y)^0+(x+y)^1+(x+y)^2+...)]_2=(x+y)^2

h_2(x,y)=[h_1(x,1)*∆(x,y)]_2=[(x^2+2x+1)(1+x+y+x^2+y^2+2xy+...)]_2=4x^2+4xy+y^2

now h_1(x,1)=1+2x+x^2 represents the first modified triangle

and

h_2(x,1)=1+4x+4x^2 represents the second modified triangle

## TIME COMPLEXITY:

O(m*m*log(max(diff[i])))