|
|
back to boardmy research Posted by coder 6 Sep 2020 19:40 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) ?
|
|
|