# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

4 | Um_nik | 182 |

6 | antontrygubO_o | 171 |

7 | maroonrk | 169 |

8 | kostka | 165 |

9 | SecondThread | 164 |

9 | errorgorn | 164 |

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2022 04:15:59 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).How to solve these Div.

2:[

L]ooking For Plagiarism?[

M]egafactorial?[

O]dds For Palindrome?Problem L is equivalent to number of correct bracket sequences length of 2*n. Answer for this is Catalan number.

In problem M you could notice, that K! = 0 mod M for all K >= M, because M = 0 mod M and (n+1)! = (n + 1) * n!. So, answer for n > 12 is 0, otherwise we compute factorials

In M you can precalc answer for 12!! and notice for getting zero for greater n.

In L just use Catalan numbers.

Is it possible to upsolve the problems of Div.2? The status of the contest on opentrains is

`OVER`

(instead of`/ RUNNING (xxx attempts out of 2000) / UPSOLVING`

), and I can't submit or upsolve problems.Thanks in advance.

Solution to D without multipoint evaluation:

Let $$$T(x) = \sum_{i=1}^{N} \frac{C_i}{1 - A_ix}$$$.

Let $$$P_{[L, R]}(x) = \prod_{j=L}^{R} (x + B_j)$$$

Then, the answer for a given $$$k$$$ is the coefficient of $$$x^0$$$ in $$$T(x)P_{[1, k]}(1/x)$$$

To solve for a given $$$(T(x), L, R)$$$, recursively solve $$$(T(x), L, M)$$$ and $$$(T(x)P_{[L, M]}(1/x), M + 1, R)$$$. We only need to maintain the first $$$R - L + 2$$$ coefficients of $$$T(x)$$$ and hence it works in $$$O(N \log^2 N)$$$.

Allow me to ask you some questions:

Solving for $$$(T(x), L, R)$$$ means finding the coefficient of $$$x^0$$$ in $$$T(x) P_{[L, k]}(1/x)$$$ for each $$$k$$$ in $$$[L, R]$$$. We only need $$$R - L + 2$$$ coefficients as the degree of $$$P_{[L, k]}$$$ is going to be $$$\leq R - L + 1$$$ for each valid $$$k$$$.

We call the function on $$$\sum_{i=1}^{N} \frac{C_i}{1 - A_i x}, 1, N$$$ to get all the answers. No multipoint evaluation needed.

Code

Guys, how can we solve I?

I mean, knowing the number of 'pockets' we can insert some number to, how do we calculate an answer?

Can anybody explain task B? What does it mean: ”choose an element, and then delete its left or right neighbor”?

You can find that for all 4 possible consecutive two elements (i.e. 00,01,10,11) one of the following is always true:

· picking left element <-> apply AND operator, and picking right element <-> apply OR operator;

· picking left element <-> apply OR operator, and picking right element <-> apply AND operator.

But how do we calculate an answer for "each i"?

Let's use $$$(x,y)$$$ to denote the state that we need to delete $$$x$$$ elements to the left and $$$y$$$ elements to the right. We can find that there are $$$2x-1$$$ ways to get to state $$$(x-1,y)$$$ from state $$$(x,y)$$$. Similarly, there are $$$2y-1$$$ ways to get to state $$$(x,y-1)$$$ from state $$$(x,y)$$$. Since there are $$$\binom{x+y}{x}$$$ paths from $$$(x,y)$$$ to $$$(0,0)$$$, we can see that the answer is just $$$\binom{x+y}{x}(2x-1)!!(2y-1)!!$$$.

For each $$$i$$$ with $$$A_i=1$$$, we just apply the formual above with $$$x=i-1$$$ and $$$y=n-i$$$, which can be done in $$$O(1)$$$ time if we precalculate all the things we need.

Such a beautiful reduction to the problem of the number of paths in a rectangle! Thanks!

5 out of 10 problems use FFT, all of them in a very non-trivial way. Nice balanced contest.

Yeah in our team only one guy is really good with FFT and the rest of us were just: O_O

Grand Prix of 998244353 :)

Fun fact: There is "modulo 998244353" in all the problems.

Can someone explain the solution to problem A broadly?

For each $$$1 \le i \le K$$$, consider the "boundary line" between the squares $$$\le i$$$ and $$$> i$$$ (from bottom-left corner to top-right corner), and shift the $$$i$$$-th path $$$1$$$ unit to the right and $$$1$$$ unit downwards. If there were no $$$A_{R,C} = V$$$ condition, then the problem is just counting set of disjoint paths with some set of starting points and ending points that can be solved using Lindstrom-Gessel-Viennot Lemma.

To handle the $$$A_{R,C}=V$$$ condition, note that it is equivalent to saying that $$$V-1$$$ paths continue on the "top-left" of some point $$$p$$$ in the lattice and the other paths continue on the "bottom-right" of the same point $$$p$$$. To keep track of this information, instead of setting all edge weights as $$$1$$$ in LGV Lemma, set the edges adjacent to $$$p$$$ as $$$0$$$ and then for the row of edges below $$$p$$$, set the left side as $$$1$$$ and right side as $$$x$$$. This will multiply the weight all paths that go from the bottom-right by $$$x$$$. By LGV Lemma, you just need to find the determinant of the matrix, which is a polynomial in $$$x$$$. To find it fast, substitute values and use Lagrange Interpolation.

Hey, I still am not getting the solution. What is it meant by

the "boundary line" between the squares $$$\le i$$$ and $$$\gt i$$$?.Draw the edges of the grid that separates a square with value $$$<i$$$ and square with value $$$>i$$$ (also include some edges of the big rectangle so that it is a path between opposite corners of the rectangle).

more explanation for H?

Are there any more explanation of D?

$$$\sum_{1\leq i\leq n} C_i*f(A_i)$$$

This gives the value of $$$\sum_{1\leq k \leq n} Z_i$$$

Is this solving the transposing of the original problem?

If yes,then what's the matrix that is transposed?

This is definitely a bit of a strange concept, I think you should look at the linked paper for more details.

The original problem can be thought of as a linear transformation of given $$$[x]$$$, find the values $$$[Z_1 x, Z_2 x, Z_3 x, \ldots, Z_k x]$$$, which is just a left-multiplication by a $$$k \times 1$$$ matrix. The transpose then, is given $$$[D_1, D_2, \ldots, D_k]$$$, find $$$[\sum_{i=1}^k D_i Z_i]$$$, which is multiplying by the $$$1 \times k$$$ matrix. Then, we can essentially take any algorithm which solves the transposed problem and "reverse+transpose" it to get a solution to the former; this is because we can treat the algorithm as a sequence of linear transformations, and $$$(AB)^T = B^TA^T$$$. It is definitely a little strange, but seems like a pretty interesting concept to me.

I think that makes sense.Thanks~

Problem C:

`time limit per test: 4 seconds`

is too strictly for me.It takes me 23s to compute $$$\frac{e^{Nx} - 1}{e^x - 1} \mod x^B, B = 10^6$$$ in my machine.

109185142

Wow, 17234ms in my poor computer and 1824 ms in Codeforces!

Can someone explain the solution to C? I have already understood the combinatorial meaning of $$$z$$$, but I don't know why this implies $$$z={W+H+1\choose W}$$$.

PS : It is very interesting that $$$f(H,W,A,B)$$$ does not depend on $$$B$$$. Is there a combinatorial proof avoiding binomial coefficient identities?

I realized that the first question is silly.

Now imagine a path from $$$(0,0)$$$ to $$$(p,Ap+B)$$$ (let's denote this part of the path by $$$u$$$) and then to $$$(W,H)$$$ (denote this by $$$v$$$).

Consider paths shaped like $$$u+\uparrow+v$$$, they are exactly all the paths from $$$(0,0)$$$ to $$$(W,H+1)$$$. $$$p$$$ indicates the last time for them to touch $$$y=Ax+B$$$. (it is obvious that it must go $$$\uparrow$$$ after touching $$$y=Ax+B$$$ for the last time, or it will never reach $$$(W,H+1)$$$ since $$$(W,H+1)$$$ is above $$$y=Ax+B$$$)

This also explained why $$$z$$$ does not depend on $$$A$$$ or $$$B$$$, because $$$A$$$ and $$$B$$$ only effect how we classify these paths.

Hard problems with the famous 998244353

Why downvote?

Necroposting