c++ - Finding Xth term of a series -

i have simple problem.

i having array a[] of n numbers. have perform operarion:

for(i = 2; i<=n; i++)     a[i] = a[i] + a[i-1] 

to array a[] k times. , after performing operation k times, have output xth index element.

doing brute force, lead tle.

i searching pattern, but, came solution not perfect needs be.

can please me, find more efficient solution problem.

i have example, clear question.

let's array a [1,2,3] , need perform above operation 3 times then:

array after 1st turn: a=[1,3,6]
array after 2nd turn: a=[1,4,10]
array after 3rd turn: a=[1,5,15]

so, if required find 2nd element of array now, 5.

i pascal's triangle (as @mbo say) may notice after k times number of times each number added in final result equal square in triangle following diagonals. let see example here:

this image correspond iterate 4 times first 3 elements. so, can see if have input k equal number of times , n equal index of element return, have multiply each of numbers in diagonal filled in blue until red line (the image configuration correspond k = 4 , n = 2).

after that, have formula:

now, improve way calculate formula show above, can use dynamic programming , calculate factorial function 0 ... k+n (note bigger number in sequence k-1+n). can access factorial(n) in constant time. if expand combinatoric factor inside summation notice factor (k - 1 + - i)! = (k - 1)! so, can put outside summation.

here code:

#include "stdafx.h" #include "iostream"  using namespace std;  int findingxth(int a[], int n, int k, int factorial[]){      if (k == 0)         return a[n];      int result = 0;      (int = 0; <= n; ++i)     {         int = k - 1 + i;         result += (factorial[up] / factorial[i]) * a[n - i];     }     return result / factorial[k - 1]; }  int main(int argc, _tchar* argv[]) {     int a[3] = { 1, 2, 3 };     int n = 2;     int k = 3;      int factorial[100000]; // expecification of problem has upper bounds n , k (the length of factorial array can set n+k+1);     factorial[0] = 1;      (int = 1; < n + k; i++)     {         factorial[i] = factorial[i - 1] * i;     }      int result = findingxth(a, n, k, factorial);      std::cout << result;      return 0; }