We will hold AtCoder Grand Contest 076. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc076
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20251228T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 5
- Writer: maroonrk
- Tester: maspy, HIR180
- Rated range: 2000 -
The point values will be 700-1100-1200-1400-1400.
We are looking forward to your participation!
For the problem D editorial, does "by hand" mean via the Lagrange inversion theorem? Or is there a different way?
References:
Also, is there somewhere I can find a list of problems involving power series composition?
I don't think there's a proper list, just some blogs on it that can link to problems. Do you mean composition in general (of any two functions) or including any specific cases? If it's the latter, there's a few in the recent FPS24 on Atcoder, which is a great source of FPS problems in general.
I mean problems related to https://judge.yosupo.jp/problem/composition_of_formal_power_series_large
Huh, I did most of those problems and I don't remember any of them using composition aside from the last one.
Aside from the last one, there were specific cases like exp(f), that's what I mean.
There are several ways to calculate the inverse of $$$x \exp(-x)$$$. Lagrange inversion theorem is the easiest one, but here's more tricky approach.
Let's consider the case of $$$A=(0)$$$ in this problem, then $$$\exp(-x) g(x \exp(-x)) = 1$$$. Let $$$h(x)=x g(x)$$$ and we have $$$h(x \exp(-x))=x$$$. This means that $$$h$$$ is the compositional inverse of $$$x \exp(-x)$$$. $$$[x^n] h(x) = [x^{n-1}] g(x)$$$, and considering the original problem with $$$A=(0)$$$, this equals the volume of the $$$(y_1,\cdots,y_{n-1})$$$ where $$$0 \leq y_1 \leq \cdots \leq y_{n-1} \leq n-1$$$ and $$$y_i \geq i-1$$$. Now we can calculate this value by hand and get the result of $$$n^{n-1}/n!$$$.
Thanks.
Btw, do you know how to solve the problem without using polynomial composition? It looked like some of the in-contest solutions did not use it.
(maybe this one? https://atcoder.jp/contests/agc076/submissions/72070401)
Could you give some insight into the intuition for the solution for problem B? In particular, the construction to sort any array with $$$2$$$ steps.