| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
I came up on a problem and got it to solving this one, but now I am stuck. Can someone help please?
How can we efficiently count the number of regular bracket sequences with length $$$2n$$$ that have first closing bracket on position $$$k + 1$$$ (any way faster than $$$O(nk)$$$ or $$$O(n^2))$$$?
In this blog(https://codeforces.me/blog/entry/87585) you can find number of bracket sequences with lenght 2n with a prefix on k open brackets. I belive(if i didnt missunderstand)your problem reduces to the number with a prefix of k minus the number with a prefix of k+1.(The first k will be open and the k+1th will be closed)
Isn't this similar to the CSES problem: https://cses.fi/problemset/task/2187 ?
But with the input:
if the first closing bracket is on $$$k + 1$$$, then first $$$k$$$ brackets are opening right?
if so, just solve cses bracket sequences II with $$$s_1 = s_2 = ... s_k = ($$$ and $$$s_{k+1} = )$$$