Let c[i][0] = a[i], i = 1..n
    c[i][1] = c[i+1][0] - c[i][0], i = 1..n-1
    c[i][2] = c[i+1][1] - c[i][1], i = 1..n-2
     ....
    c[i][d] = c[i+1][d-1] - c[i][d-1], i = 1..n-d.

   if hardness of a[i]  is d.  so all c[i][d] = const.

    1. Find minimum d, that  all c[i][d] - is const.  (example:  binary search).
    2. build b[n+i] from c[i][d].


There can calculate c[i][j] through a[i] sequences:

    c[i][1] = a[i+1] - a[i]
    c[i][2] = c[i+1][1] - c[i][1] = (a[i+2] - a[i+1]) - (a[i+1] - a[i]) = a[i+2] - a[i+1] - a[i+1] + a[i] = a[i+2] - 2*a[i+1] + a[i].

   c[i][3] = c[i+1][2] - c[i][2] = (a[i+3] - 2*a[i+2] + a[i+1]) - (a[i+2] - 2*a[i+1] + a[i]) = a[i+3] - 3* a[i+2] + 3*a[i+1] - a[i].

   ..
   c[i][d] = SUM( c[i + d - j ] * Binom(d, j) * (-1)^j, j = 0..d)

    where Binom(d, j) - Binominal coefficients , or  coefficients of (x+y)^d .

  if d - is known,

   c[1][d] = c[2][d] = ... = c[n-d][d] = W - constanta.

  b[n+1] = x

   c[n-d+1] = b[n+1] + SUM(a[n + 1- j] * binom(d,j)*(-1)^j, j = 1..d)  = W

   b[n+1] = W - SUM(a[n+1-j] * binom(d,j)*(-1)^j, j = 1..d)

   and so on.


  Only one problem,  how fastest calculate SUM(a[i + d - j] * binom(d,j)(-1)^j, j = 1..d)   ?

DELETED

Edited by author 04.08.2019 22:55