### zero4338's blog

By zero4338, history, 7 months ago,

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 ?

• +53

 » 7 months ago, # | ← Rev. 2 →   +39 I knew a blog,but it is in Chinese. Can you read Chinese?
•  » » 7 months ago, # ^ |   +10 Yes.thx
•  » » 7 months ago, # ^ |   +12 How are they related in any way?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Maybe that blog only talks about $\sf{\sum\limits_{i=1}^{n}\frac{n}{i}\approx n\ln n}$.
 » 7 months ago, # |   -36
•  » » 7 months ago, # ^ |   0 sorry but codeforces said I'm not allow to read the requested page
•  » » » 7 months ago, # ^ |   -37 ok ill copy the content here
 » 7 months ago, # |   +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.)
•  » » 7 months ago, # ^ | ← 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.
•  » » » 7 months ago, # ^ |   0 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.
•  » » » » 7 months ago, # ^ |   0 Yes, that one.
•  » » » » 7 months ago, # ^ |   0 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?
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   +5 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}$.
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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?2.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.
•  » » » » » » » 7 months ago, # ^ |   0 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.
•  » » » » » » » » 7 months ago, # ^ |   0 Thank you!
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 7 months ago, # ^ |   0 Thanks! And that article is not written by me, it is written by weng_weijie who is only $18$ now.
•  » » » » » » » 7 months ago, # ^ |   0 Could you elaborate on calculating shift(p, c) in $O(n)$?
•  » » » » » » » » 7 months ago, # ^ |   0 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.
 » 7 months ago, # |   +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.
•  » » 7 months ago, # ^ |   -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.
 » 7 months ago, # |   -18 A recent problem using this technique. Look at it's editorial.
•  » » 7 months ago, # ^ |   0 Maybe that problem has no relation with this problem.
•  » » » 7 months ago, # ^ |   0 Yeah, I misunderstood because it was a related concept
 » 7 months ago, # |   -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?
•  » » 7 months ago, # ^ |   +6 $\sum_{i=1}^n \frac{1}{i} \pmod{998244353}$
•  » » » 7 months ago, # ^ |   -11 Is this a floor?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +4 I assume $\frac{1}{i}$ denotes the modular inverse of $i$.
•  » » » » » 7 months ago, # ^ |   -11 Oh, ok.
 » 7 months ago, # |   0 Auto comment: topic has been updated by zero4338 (previous revision, new revision, compare).