| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3845 |
| 2 | tourist | 3798 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3589 |
| 6 | Ormlis | 3532 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3463 |
| 9 | ecnerwala | 3451 |
| 10 | Um_nik | 3450 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | Qingyu | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 157 |
| 5 | Dominater069 | 156 |
| 6 | adamant | 154 |
| 7 | djm03178 | 151 |
| 8 | luogu_official | 149 |
| 9 | awoo | 147 |
| 10 | TheScrasse | 145 |
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(n2))?
In this blog(https://mirror.codeforces.com/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 s1=s2=...sk=( and sk+1=)