Hi! I found a type of problems I couldn't solve, but I read that we can solve them using FFT or generating functions. I don't know how to use these approaches here, can someone help me please? (I didn't found a tutorial, just discussions) The problems are: - Square Grid - The last problem in this note of Petr's blog - Kalel, The Jumping Frog Would be nice for me a more detailed explanation or a resource to check
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 11:45:07 (i1).
Desktop version, switch to mobile version.
Supported by
Problems are nice. +1 on that.
I tried to solve the first problem using ChatGPT, but it's struck on solving the easier version only.
Gave a DP solution.
Long reply, but it ends with
It ends with,
It ends with,
At this point, I gave up.
I tried to calculate $$$\text{lcm}(1, 2, \dots, 16)$$$ using ChatGPT, but it's not as easy as it seems. Apparently ChatGPT is not so good at manipulating formulas and doing calculations.
For the last problem: you can simply treat the problem as usual matrix exponentiation problem but using a polynomial in every entry of the matrix to represent the energy spent, naive multiplication is enough for AC in something like O(D^3 K^2 logN). You can further optimize it using some polynomial operations down to O(KD logKD logN).
As for the others, I have no idea.
Ohh interesting approach, it's a really cool solution. Thx!
Firstly, try to solve a problem only on x-axis.
This means try to implement a function F(x1, x2) that returns Poly, whose k'th coefficient is number of ways to go from x1 to x2 without visiting 0. Here, it would be convenient to assume that we can visit x2 more than one time.
Secondly, let $$$X = F(x_1, x_2)$$$, $$$X' = F(x_2, x_2)$$$, same for $$$Y$$$ and $$$Y'$$$.
Then, divide k'th coefficient of every Poly by $$$k!$$$.
Let $$$A = X \times Y$$$, $$$A' = X' \times Y'$$$
Multiply k'th coefficients of $$$A$$$ and $$$A'$$$ by $$$k!$$$. Now, one can see that $$$A_k = \sum_{i=0}^{k} X_i \times Y_{k-i} \times \binom{k}{i}$$$ =
"from $$$x_1$$$ to $$$x_2$$$ in $$$i$$$ moves" $$$\times$$$ "from $$$y_1$$$ to $$$y_2$$$ in $$$k-i$$$ moves" $$$\times$$$ "choose $$$i$$$ moves from $$$(k-i)+i$$$". Same for $$$A'$$$.
Now, the answer is just $$$A \div A'$$$, because $$$A_k$$$ is the number of ways to go from (x1, y1) to (x2, y2) in k moves, but we can visit (x2, y2) more that once, and $$$A'_k$$$ is the number of ways to go from (x2, y2) to (x2, y2) in k moves.