Nyaan's blog

FPS 24: 24 Problems on Formal Power Series
By Nyaan, history, 6 months ago, In English

Contest Page

Since there were more overseas participants than expected, I set up a discussion blog just in case.

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

»
6 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -22 Vote: I do not like it

Here's problem K

→ Reply
»
6 months ago, hide # |
 
Vote: I like it +67 Vote: I do not like it

Thank you for this contest, I enjoyed the problems a lot!

→ Reply
»
6 months ago, hide # |
 
Vote: I like it -31 Vote: I do not like it

I am not very much familiar with atcoder. how to see the eps from 1 to 23? if there exist any?

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is there anything wrong with my ntt? I've used this one for quite a while but I've been getting TLE'd hard on some of these. For example, my solution for C: https://pastebin.com/P0dz2S1x

→ Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I am not able to understand editorial of problem L, can somebody help me.

I solved it in slightly different way:

  • Main Observation: Count number of functional graphs which donot have length = 1, length = 2 cycles.
  • If the problem says only avoid length-1 cycles, its pretty much simple, just directly use dearrangements formula, (or its dp version too). Say $$$D(x)$$$ be number of dearrangements of permutation of length x.

  • So, we can use inclusion — exclusion on length 2 cycles (Lets call them as pair).

    • Initial $$$ans = D(N)$$$
    • Subtract 1 pair at a time: ans -= $$$C(N,2) * 1!! * D(N-2)$$$
    • Add 2 pairs at a time: ans += $$$C(N,4) * 2!! * D(N-4)$$$
    • Subtract 3 pairs at a time: ans += $$$C(N,6) * 3!! * D(N-6)$$$ and so on..

Submission
By this way, we can compute our answer in $$$O(N)$$$ I dont see a need to use FPS here, or neither I am not able to understand how to use FPS in this problem.

→ Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    wait there is an editorial? i cant find any in the contest's editorial section

    → Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Sometimes you compute a power series by DP. The answer can be described as a coefficient of a nice function.

    → Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    For what I understand, the editorial tries to exemplify the exponential formula, which is basically finding relations of the kind $$$ H=e^D $$$ for $$$H$$$, $$$D$$$ EGF's. The idea is more or less:

    I have some elements represented by $$$D$$$. $$$H$$$ can be formed by taking a single element of $$$D$$$, or taking two elements of $$$D$$$ and renaming, taking three elements of $$$D$$$ and renaming ...etc.

    Taking a single element is just adding $$$D$$$, taking two and renaming is doing $$$\sum_n(\sum_{n=i+j} \frac{n!}{i!j!}d_id_j)\frac{x^n}{2}=\frac{D^2}{2!}$$$ (the $$$/2$$$ I interpret it as preventing the overcounting for cases $$$i=a,j=b$$$ and $$$i=b,j=a$$$), in general taking $$$k$$$ elements from $$$D$$$ and renaming is

    $$$ \sum_n(\sum_{n=j_1+\dots+j_k}\frac{n!}{j_1!\dots j_k!} d_{j_1}\dots d_{j_k})\frac{x^n}{k!} = \frac{D^k}{k!}$$$

    Then $$$H=1+D+\frac{D^2}{2!}+\frac{D^3}{3!}+\dots =e^D$$$.

    For the problem L, one can think $$$H$$$ as the amount of permutations and $$$D$$$ as the cycles. The EGF for cycles is $$$\sum_{n\geq 1}(n-1)!\frac{x^n}{n!}$$$, but as we don't want any cycle of length $$$1$$$ or $$$2$$$ we just make $$$D=\sum_{n\geq 3}(n-1)!\frac{x^n}{n!}$$$

    Hope this helps. I read about this in generatingfunctinology (the whole second chapter is basically ideas related to the exponential formula)

    → Reply
    • »
      »
      »
      4 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      thanks. i will read more about these in generative functionology.

      → Reply
    • »
      »
      »
      4 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I didnt understand the overcounting scenario, (the /2 I interpret it as preventing the overcounting for cases i=a,j=b and i=b,j=a), but what happens if i = j.

      → Reply
      • »
        »
        »
        »
        4 months ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +16 Vote: I do not like it

        What we are actually counting is the number of ways to also label the nodes of the cycles, with labels from $$$1$$$ to $$$n$$$. So when the cycle lengths are the same you are still double counting, so even then the $$$/2$$$ is justified. The /k! basically makes sure that cycle $$$1$$$ gets the label $$$1$$$, cycle $$$2$$$ gets the next smallest available label, and so on.

        → Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it +26 Vote: I do not like it

    You need to count permutations s.t. no permutation has a cycle of size $$$1$$$ or $$$2$$$, which are the only two ways you can get $$$p_{p_i} = i$$$. From exponential formula, EGF for a set of structures having EGF $$$A(x)$$$ is $$$\exp A(x)$$$.

    The EGF of cycles is $$$\log\frac{1}{1-x} = \sum\limits_{k=1}^\infty (k-1)!\frac{x^k}{k!}$$$, and you need to make a set of those with $$$k \gt 2$$$, so the answer is

    $$$ \left[\frac{x^n}{n!}\right] \exp \left(\log \frac{1}{1-x} - x-\frac{x^2}{2}\right) $$$

    Here, we subtracted $$$x$$$ and $$$\frac{x^2}{2}$$$ to get rid of the "bad" cycles.

    A possible faster way here, corresponding to your linear solution is is to represent it as

    $$$ \left[\frac{x^n}{n!}\right] \frac{e^{-x}}{1-x}e^{-\frac{x^2}{2}}, $$$

    since $$$\frac{e^{-x}}{1-x}$$$ is, indeed, the generating function for derangements.

    → Reply