Help! Divide and Conquer Algorithm for Computing General Linear Recurrence???
Разница между en1 и en2, 2 символ(ов) изменены
Hallo, everyone.↵
↵
Can you please help me with the following problem?↵
↵
> If a[n] = b[k] * ba[n-k] for k = 1..n, then the generating function A(x) = a[0] / (1 — B(x)) We can compute all a[n]  with Divide and Conquer algorithm in O(nlog^2(n)). What is that Divide and Conquer algorithm?↵
↵
I have the feeling that it is strongly related to FFT but that's just my feeling. Can someone give me the exact algorithm?↵
↵
Thank you↵
↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский duckladydinh 2017-11-23 20:03:24 2 Tiny change: ' = b[k] * b[n-k] for ' -> ' = b[k] * a[n-k] for '
en1 Английский duckladydinh 2017-11-23 08:23:15 512 Initial revision (published)