zero4338's blog

Need help in Harmonic series
By zero4338, history, 3 years ago, In English

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 ?

  • Vote: I like it
  • +53
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Blog about Mobius inversion

Read the part about harmonic lemma.

→ Reply
»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +34 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, that one.

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          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}$$$.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Thanks for your explaination.

            But I have two questions yet.

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
»
3 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply