Karry5307's blog

By Karry5307, history, 4 years ago, In English

Could anyone give a solution to the problem below with $$$O(n\log n)$$$ or $$$O(n\log^2n)$$$ time plz?

Given two sequences $$$g,h$$$ with length $$$n$$$ and a binary function $$$F(n,k)$$$, calculate the sequence $$$f$$$ which satisfies:

$$$f_{i}=\left(\sum\limits_{k=0}^{i}F(i,k)g_kh_{i-k}\right)\bmod 998244353$$$

And $$$F(n,k)$$$ can be arbitrary, such as $$$1$$$, $$$\binom{n}{k}$$$, $$$n^k$$$ or $$$k^n$$$.

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

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it
  • the case $$$F(n,k) = 1$$$ is trivial.
  • the case $$$F(n,k) = \binom{n}{k}$$$ can be translated into
$$$ \frac{f_{i}}{i!}=\left(\sum\limits_{k=0}^{i} \frac{g_k}{k!} \frac{h_{i-k}}{(i-k)!} \right)\bmod 998244353 $$$
  • the other case, I don't know
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    the third case with your observation of the second and with this formula "Stirling numbers of the second kind express reverse relations"

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It seems that it would be more difficult when using Stirling numbers, but thanks lol

      So how about $$$F(n,k)=k^n$$$? I tried to introduce new kernel functions, or using discrete logs and Bluestein, or simply tried to deduce algorithms similar to FFT, but nothing works.

      Furthermore, is any universal and efficient algorithms provided when $$$F(n,k)$$$ is arbitrary?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +13 Vote: I do not like it

        I myself have been quite interested in FFT, power series and gfology in competitive programming since about a year ago (I'm not good at these topics at all, though). Here are some of my thoughs about the problem.

        For the general function $$$F(n, k)$$$, (i. e., an array consisting of $$$\frac{1}{2}n(n+1)$$$ values), there definitely cannot be an $$$\text{o}(n^2)$$$ solution as the size of the input is already $$$\text{O}(n^2)$$$ without any useless information(all those values have an influence on the output). If you want a solution in which $$$F(n, k)$$$ is a fixed function given at the beginning of the input and $$$\text{O}(\text{poly}(n))$$$ queries are made afterwards, it's hardly possible to do each query in $$$\text{O}(n \log n)$$$ either, because the problem is at least as hard as matrix multiplication(with $$$h_i = 1$$$).

        For specific functions $$$F(n, k)$$$, I also don't think a general solution exists — if there was a solution it should also be able to solve the general problem mentioned in the previous paragraph. In this case, you can only deal with particular situations: for instance, when $$$F(n, k)$$$ can be represented as $$$a_nb_kc_{n-k}$$$ with three fixed arrays $$$a$$$, $$$b$$$, $$$c$$$, a simple convolution will solve anything. However, when $$$F(n, k)$$$ becomes $$$k^n$$$ or stirling numbers of the second kind (in my opinion these two are probably as difficult), the problem quickly becomes much more unsolvable: the simplest case where $$$h_i = 1$$$ is already equivalent to a multipoint evalution on an algebraic sequence $$$1, 2, ..., n$$$, which currently has only an $$$\text{O}(n \log^2 n)$$$ solution and is much more complicated than convolution. The case $$$h_i \not= 1$$$ is too hard — I guess there doesn't exist a solution with complexity $$$\text{O}(n \text{polylog}(n))$$$, and I'm pretty sure it's impossible using only techniques currently introduced into competitive programming combined with elementary algebra transformations.

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

      I don't see how you can solve the third problem with this. I also quickly understood the second case and tried to tackle the third one with the expansion $$$(a+b)^n$$$, all in vain. I just don't see how to reduce the problem to a convolution by replacing $$$F(n, k)$$$ with some summation (of 2nd kind stirling numbers time falling factorial, in this case).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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