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 ?

# | User | Rating |
---|---|---|

1 | tourist | 3764 |

2 | slime | 3592 |

3 | maroonrk | 3535 |

4 | Benq | 3513 |

5 | jiangly | 3509 |

6 | ecnerwala | 3508 |

7 | MiracleFaFa | 3466 |

8 | ksun48 | 3452 |

9 | Um_nik | 3426 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 183 |

4 | YouKn0wWho | 182 |

5 | Um_nik | 181 |

6 | antontrygubO_o | 173 |

7 | maroonrk | 168 |

8 | errorgorn | 165 |

8 | SecondThread | 165 |

10 | kostka | 164 |

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 ?

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2022 15:16:26 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Yes.thx

Blog about Mobius inversion

Read the part about harmonic lemma.

How are they related in any way?

Maybe that blog only talks about $$$\sf{\sum\limits_{i=1}^{n}\frac{n}{i}\approx n\ln n}$$$.

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

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

ok ill copy the content here

help debug https://pastebin.com/u27cQvw0 https://codeforces.com/contest/1446/problem/A

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

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.)

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.

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.

Yes, that one.

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?

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:

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}$$$.Thanks for your explaination.

But I have two questions yet.

How to solve this?

2.

In bicsi's answer, there are

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.

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

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.

Thank you!

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.

Thanks! And that article is not written by me, it is written by weng_weijie who is only $$$18$$$ now.

Could you elaborate on calculating

`shift(p, c)`

in $$$O(n)$$$?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.

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.

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.

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

Maybe that problem has no relation with this problem.

Yeah, I misunderstood because it was a related concept

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?

$$$\sum_{i=1}^n \frac{1}{i} \pmod{998244353}$$$

Is this a floor?

I assume $$$\frac{1}{i}$$$ denotes the modular inverse of $$$i$$$.

Oh, ok.

Auto comment: topic has been updated by zero4338 (previous revision, new revision, compare).