Need help in Harmonic series

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
36:14:22
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 38:24:20

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя zero4338

Need help in Harmonic series

Автор zero4338, история, 3 года назад, По-английски

I heard that it is possible to compute $$$\sum\limits_{i=1}^n\frac{1}{i}\pmod{998244353}$$$ in $$$O(\sqrt n)$$$ complexity with some polynomial technology .

But I don't know how. Can someone give a solution ?

zero4338
3 года назад
32

Комментарии (27)

Показать архивные | Написать комментарий?

realRainFestivalqwq

3 года назад, # |

← Rev. 2 →

+39

I knew a blog,but it is in Chinese. Can you read Chinese?

→ Ответить

zero4338

3 года назад, # ^ |

+10

Yes.thx

→ Ответить

TranGiaHuy

3 года назад, # |

-25

Blog about Mobius inversion

Read the part about harmonic lemma.

→ Ответить

cfdiv2E

3 года назад, # ^ |

+12

How are they related in any way?

→ Ответить

mac_n_cheese_pog

3 года назад, # |

-36

https://mirror.codeforces.com/blog/entry/96505

→ Ответить

yspm

3 года назад, # ^ |

sorry but codeforces said I'm not allow to read the requested page

→ Ответить

clyring

3 года назад, # |

+13

Though it looks at least very close to what's written in the blog already linked, it's also possible to reason:

$$$ \begin{array}{rl} \sum_{i=1}^n \frac{1}{i} & = \sum_{i = 1}^n \frac{1}{x+i} \mid_{x = 0} \\ & = \frac{d}{dx} \sum_{i = 1}^n \ln{(x+i)} \\ & = \frac{f'(0)}{f(0)}, \end{array} $$$

where $$$f(x) = \prod_{i=1}^n (x+i)$$$. Then you can use the well-known small-step big-step trick for calculating $$$n!$$$ in $$$\tilde{O}(\sqrt{n})$$$, but just also calculate the derivative of the relevant polynomial. (And derivatives don't need to be propagated until the multi-point evaluation step, which is convenient.)

→ Ответить

realRainFestivalqwq

3 года назад, # ^ |

← Rev. 2 →

+34

Then you can use the well-known small-step big-step trick for calculating $$$n!$$$ in $$$\tilde{O}(\sqrt n).$$$

I don't know your means clearly and I can't do that. I tried to google it but I found nothing useful. How to solve this? Wait and thanks for your answer.

→ Ответить

bicsi

3 года назад, # ^ |

I also don’t know, but I would asaume what he means is computing the polynomial product $$$\prod_{i=1}^\sqrt{n} (X+ i)$$$ via FFT D&C and then use multipoint evaluation on multiples of $$$\sqrt{n}$$$ (and then use brute force to account for the remaining part that is non-divisible by $$$\sqrt{n}$$$).

Not sure if it’s clear enough, let me know.

→ Ответить

clyring

3 года назад, # ^ |

Yes, that one.

→ Ответить

realRainFestivalqwq

3 года назад, # ^ |

Thanks for your explaination.

I think your solution is $$$\sf{O(\sqrt n\log^2n)}$$$, maybe it is enough in $$$n<998244353$$$. Am I right?

→ Ответить

Golovanov399

3 года назад, # ^ |

← Rev. 2 →

It depends. If you do something like this: fun calc(l, r) { // calculate (x + l)...(x + r) if (l == r) { return x + l } else { m = (l + r) / 2 return multiply(calc(l, m), calc(m + 1, r)) } }

then yes, the time complexity is $$$O(n\log{n}^2)$$$. But if you do something like in the binary exponentiation:

fun shift(p, c) { // calculate the coefficients of p(x + c)
  ...
}

fun calc(n) { // calculate (x + 1)...(x + n)
  if (n == 1) {
    return x + 1
  } else if (n % 2 == 1) {
    return calc(n - 1) * (x + n)
  } else {
    p = calc(n / 2)
    return multiply(p, shift(p, n / 2))
  }
}

then it is possible to do shift(smth of size n) in $$$O(n\log{n})$$$, hence the total time complexity is $$$O\left(n\log{n} + \frac{n}{2}\log\frac{n}{2} + \ldots\right) = O(n\log{n})$$$.

UPD: of course, by $$$n$$$ I denote your $$$\sqrt{n}$$$.

→ Ответить

realRainFestivalqwq

3 года назад, # ^ |

← Rev. 2 →

Thanks for your explaination.

But I have two questions yet.

then it is possible to do shift(smth of size n) in $$$\mathcal O(nlogn)$$$.

How to solve this?

In bicsi's answer, there are

use multipoint evaluation on multiples of $$$\mathcal{\sqrt n}$$$.

I know we can do multipoint evaluation in $$$\mathcal{O(n\log^2n)}$$$.

I think it means we should do $$$\sqrt n$$$ points evaluation polynomial of degree $$$\sqrt n$$$, so we should cost $$$\mathcal{O(\sqrt n\log^2\sqrt n)}=O(\sqrt n\log^2 n)$$$.

I wonder that how to solve this faster.

Thanks for your answer in advance.

→ Ответить

Golovanov399

3 года назад, # ^ |

1 . If you say that $$$p(x) = \sum_{i=0}^na_ix^i$$$ then

$$$p(x + c) = \sum_{i=0}^na_i(x+c)^i = \sum_{i=0}^n\sum_{j=0}^i\frac{a_ii!}{j!(i-j)!}x^jc^{i-j} = \sum_{j=0}^n\frac{x^j}{j!}\sum_{i=j}^na_ii!\cdot\frac{c^{i-j}}{(i-j)!},$$$

and its coefficients can be found by myltiplying some two polynomials.

2 . Yes, I forgot about multipoint evaluation. My comment was entirely about calculating that divide-and-conquer thing.

→ Ответить

clyring

3 года назад, # ^ |

← Rev. 2 →

I̶n̶ ̶t̶e̶r̶m̶s̶ ̶o̶f̶ ̶t̶h̶e̶ ̶c̶o̶e̶f̶f̶i̶c̶i̶e̶n̶t̶s̶,̶ ̶̶f̶u̶n̶ ̶s̶h̶i̶f̶t̶(̶p̶,̶ ̶c̶)̶̶ ̶i̶s̶ ̶t̶r̶i̶v̶i̶a̶l̶ ̶t̶o̶ ̶i̶m̶p̶l̶e̶m̶e̶n̶t̶ ̶i̶n̶ ̶$̶O̶(̶n̶)̶$, but the multi-point evaluation itself is still something like $$$O(\sqrt{n} (\log{n})^2)$$$ when implemented normally, so this doesn't improve the asymptotic complexity on its own. Increasing the big step size to around $$$O(\sqrt{n \log{n}})$$$ combined with this optimization does reduce the complexity to $$$O(\sqrt{n} (\log{n})^{3/2})$$$.

The article realRainFestivalqwq linked to above appears to get $$$O(\sqrt{n} \log{n})$$$ anyway by working in a point-value-basis instead of a coefficients-basis so that the necessary multi-point evaluation becomes free; this comes with the drawback of making fun shift(p, c) actually be a somewhat tricky $$$O(n \log{n})$$$ function that needs to be called multiple times per size-doubling rather than only one.

It should be possible and I expect it to be somewhat faster to differentiate $$$f$$$ in this basis rather than propagating the derivative terms $$$g_t$$$ at each scale as is done in the article, but that isn't really so important.

→ Ответить

Golovanov399

3 года назад, # ^ |

Could you elaborate on calculating shift(p, c) in $$$O(n)$$$?

→ Ответить

clyring

3 года назад, # ^ |

I cannot. I now think I lost an $$$x$$$ in one of my mental manipulations last night to reach a wrong result there. And since this doesn't propagate (dominated by the multiplication) I didn't check it as carefully as I perhaps should have.

→ Ответить

box

3 года назад, # |

+46

If we are talking about practicality, we can precompute the answers for $$$n=10^6,2\times 10^6,\dots,999\times 10^6$$$ locally, and then use this as a lookup table.

→ Ответить

bicsi

3 года назад, # ^ |

-8

Judging by your argument, you could precompute the harmonic sums up to $$$n = 10^6, 2 \times 10^6, \ldots, 999 \times 10^6$$$ locally as well.

→ Ответить

ojus_single

3 года назад, # |

-18

A recent problem using this technique. Look at it's editorial.

→ Ответить

realRainFestivalqwq

3 года назад, # ^ |

Maybe that problem has no relation with this problem.

→ Ответить

ojus_single

3 года назад, # ^ |

Yeah, I misunderstood because it was a related concept

→ Ответить

dthompson

3 года назад, # |

-12

Wait, did you just ask for (for loop from 1..n) the sum of 1 / n? If so, isn't this just n * 1 / n? So 1? Or did you want the sum of (for loop from 1..n) the sum of i / n?

→ Ответить