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} = )$$$