| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Try to solve the following problem, only by combining meaning but not the generating function.
There are q times inquiries, Given k, P, a, each time, print the value of this sum, $$$q,k,P,a \leq 1e5$$$.
I'll give an answer in 24 hours. If solved, please write the method in the comments and try the harder problems below, which replace 2 by t, t will be given before all queries.
interesting
Consider translate it into counting the number of paths in a grid.
sad that no one is interested in it. If anyone wants an answer, please reply to me and I will give the answer as soon as possible
I'm interested. Please share the solution.
it can be seen as the number of intersections from (0,0) to (n,m) with $$$y=x+k$$$.
We count the last time of intersection, then we can recurse the subproblems.
$$$Ans=\sum_{i=0}^{a+b} 2^{a+b-i} \binom{i}{b}$$$ , which can be solved by sweepline Mo.
But I think there should be a more direct combination explanation, I very much hope that who are interested will come to discuss.
Motivated by your problem, I once encountered this long time back but left it because couldn't make any progress.
There are q times inquiries, Given k, l, n, each time, print the value of this sum
I thought it seems like choosing l object out of n but it was wrong iirc.
Any hints?
Yubai
Thank you
This is a classic combinatorial problem. Consider there are n+1 balls, and you need to choose l+1 balls. One way to calculate it is enumerate the position of the (k+1)th ball, suppose its current position is $$$i+1$$$, then you only need to choose k balls from the first i balls, and choose (l+1-1-k) balls from the last (n+1-i-1) balls, got the sum you gave.
so, the answer is $$$\binom{n+1}{l+1}$$$, which can make $$$q\leq 2e6$$$ too.