括号序列问题

(Updated: )
(13 mins to read)

前置结论

定义左括号’(‘为+1，右括号’)'为-1，作前缀和得到一个序列p当且仅当$p_n = 0 \wedge \forall i \ p_i >=0$时，该括号序列合法

取$mn = \min_{i=1}^n p_i$​，则该括号序列的最长合法括号子序列的长度为$n - p_n + 2mn$考虑位置pos，其中$p_{pos}=mn$，则在$1…pos$中，有-mn个右括号失配，在$pos+1…n$中有$p_n-mn$个左括号失配

一个长度为n，右括号个数为m，对应的序列p的最小值为t的括号序列的个数有$\binom{n}{n-m-t} - \binom{n}{n-m-t+1}$先考虑对应的序列p的最小值不小于t的方案数：利用计算卡特兰数的方法，所有减去不合法。其中所有即$\binom{n}{m}$。不合法的即序列p的最小值是<=t-1的，考虑位置pos，其中$p_{pos}=t-1$，则在$1…pos$中左括号比右括号少$−(t−1)$个，$pos+1…n$中左括号比右括号多$n−2m−(t−1)$，将$1…pos$的左右括号翻转，则$1…n$中左括号比右括号多$n−2m−2(t−1)$个，容易发现不合法的括号序列与左括号比右括号多$n−2m−2(t−1)$个的括号序列一一对应，所以不合法即为$\binom{n}{n-m-t+1}$那么对应的序列p的最小值不小于t+1的方案数为$\binom{n}{m} - \binom{n}{n-m-t}$则对应的序列p的最小值为t的方案数为$\binom{n}{n-m-t} - \binom{n}{n-m-t+1}$

一个括号序列循环移位后合法的方案数：

  • 若左括号数不等于右括号数，显然无解
  • ans = p中最小值出现的次数，若$p_{pos} = mn$，则将$1…pos$移到后面，$pos+1…n$移到前面则合法

洛谷p6689 序列

题意

一个长度为n，初始全为’(‘的括号序列，给定参数k，每次随机在[1,n]选择一个位置然后翻转该位置的括号，当翻转了一个’('，就让k-1，重复直至k=0。询问最后生成的括号序列的最长合法子序列的期望长度$n, k<=5\times 10^3$

做法

知道一个括号序列的左右括号的个数以及其对应的序列p的最小值就可以得到该括号序列的最长合法子序列的长度。先求出长度为n的括号序列中有m个右括号的概率，再枚举序列p的最小值即可解决，这是两个独立的问题。首先概率dp：$f_{ij}$表示当前参数为i，已经有j个右括号的概率$f_{ij} = \dfrac{n-j+1}{n}\sum_{k=j-1}^{n} f_{ik}\prod_{l=j}^{k}\dfrac{l}{n}$$f_{ij}$​可以由$j-1…n$个右括号的情况转移过来，相当于先连续将x个右括号变成左括号，然后再将1个左括号变成右括号$\dfrac{f_{0m}}{\binom{n}{m}}$​​就等于生成一个有m个右括号的括号序列的概率最后枚举这个括号序列的最小值，然后依据上面的公式计算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, N = 5e3 + 5;
inline void mul(int &a, int b) { a = 1ll*a*b%mod; }
inline int Mul(int a, int b) { return 1ll*a*b%mod; }
inline void add(int &a, int b) { a+=b; if(a>=mod) a-=mod; }
inline int Add(int a, int b) { a+=b; if(a>=mod) return a-mod; return a; }
inline void sub(int &a, int b) { a-=b; if(a<0) a+=mod; }
inline int Sub(int a, int b) { a-=b; if(a<0) return a+mod; return a; }
int n, k, f[N][N], fac[N], inv[N];
int powmod(int a, int b)
{
  int ans = 1;
  while(b)
  {
    if(b&1) mul(ans, a);
    mul(a, a);
    b >>= 1;
  }
  return ans;
}
void init(int n)
{
  fac[0] = 1;
  for(int i=1;i<=n;i++) fac[i] = 1ll*fac[i-1]*i%mod;
  inv[n] = powmod(fac[n], mod-2);
  for(int i=n-1;i>=0;i--) inv[i] = 1ll*inv[i+1]*(i+1)%mod;
}
int comb(int a, int b)
{
  if(a<b||b<0||a<0) return 0;
  return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
  scanf("%d%d", &n, &k);
  int invn = powmod(n, mod-2);
  f[0][0] = 1;
  init(n);
  for(int i=1; i<=k; i++)
  {
    int sum = f[i-1][n];
    for(int j=n; j>=1; j--)
    {
      mul(sum, Mul(j, invn));
      add(sum, f[i-1][j-1]);
      f[i][j] = Mul(Mul(invn, (n-j+1)), sum);
    }
  }
  for(int i=1; i<=n; i++) mul(f[k][i], powmod(comb(n, i), mod-2));
  int ans = 0;
  auto cal = [](int x, int y, int z)->int //长度为x的括号序列，有y个右括号，对应序列p的最小值为z的方案数
  {
    return Sub(comb(x, x-y-z), comb(x, x-y-z+1));
  };
  for(int i=1; i<=n; i++) //枚举右括号个数
    for(int j=2; j<=n&&min(i, n-i)>=j/2; j+=2) //枚举最长合法子序列的长度为j，则此时p序列的mn=(j-2i)/2
      add(ans, Mul(Mul(j, f[k][i]), cal(n, i, (j-2*i)/2)));
  printf("%d\n", ans);
  return 0;
}

D2. The World Is Just a Programming Task (Hard Version)

题意

给定一个括号序列，要求交换其中两个位置的括号，使得该括号序列循环移位后合法的方案数最多$n<=3\times 10^5$

做法

由上面结论可得，就是要最大化该括号序列对应的p序列的最小值的个数显然交换两个相同的括号是没有意义的当交换一个左括号和一个右括号时，相当于对这段区间的p序列-2当交换一个右括号和一个左括号时，相当于对这段区间的p序列+2显然区间+2只会使最小值个数减少下面考虑区间-2：如果操作的区间中包含了原来最小值的某个位置，显然答案不会更优所以设$pos_1,…,pos_x$​为p序列最小值所处的位置，那么操作的区间只可能是$(pos1,pos2)…$，也可能是$(pos_x,pos_1)$，准确来说是对$[pos_1,pos_x]+2$，相当于是对$(posx,n]$，$[1,pos_1)-2(posx​,n]$，$[1,pos1​)−2$最优的情况只有两种：

  • 让最小值变成mn-1，只要统计出以上区间中等于mn+1的最多个数即可（显然操作区间越大越好，即$[pos_i, pos_{i+1}]$）
  • 让最小值仍为mn，需要统计出以上区间中连续的且不包含mn+1的然后mn+2值最多的个数，还要再加上原本等于mn的个数（在以上每个操作区间中作尺取法即可，遇见mn+1就让计数器清空，否则不断往右移动）以上两者取优即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 3e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, p[N];
char s[N];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> (s+1);
  for(int i=1; i<=n; i++) p[i] = (p[i-1] + (s[i]=='(' ? 1 : -1));
  if(p[n]) { cout << 0 << '\n' << 1 << ' ' << 1 << '\n'; return 0; }
  int mn = *min_element(p+1, p+n+1);
  vector<int> vec;
  for(int i=1; i<=n; i++) if(p[i]==mn) vec.pb(i);
  int ans = sz(vec);
  pii pos = {1, 1};
  for(int i=0; i<sz(vec)-1; i++)
  {
    int j = vec[i] + 1, k = vec[i+1] - 1;
    if(j>k) continue;
    int one = 0, two = 0, tmp = 0, st = 0;
    pii pp = {0, 0};
    for(int _=j; _<=k; _++)
    {
      if(p[_]==mn+1)
      {
        ++one;
        tmp = st = 0;
      }
      if(p[_]==mn+2)
      {
        ++tmp;
        if(!st) st = _;
      }
      if(tmp>two)
      {
        two = tmp;
        pp = {st, _%n+1};
      }
    }
    if(one>ans) ans = one, pos = {j, k%n+1};
    if(two+sz(vec)>ans) ans = two+sz(vec), pos = pp;
  }
  int one = 0, two = 0, tmp = 0, st = 0;
  pii pp = {0, 0};
  for(int _=vec.back()%n+1; _!=vec.front(); _=_%n+1)
  {
    if(p[_]==mn+1)
    {
      ++one;
      tmp = st = 0;
    }
    if(p[_]==mn+2)
    {
      ++tmp;
      if(!st) st = _;
    }
    if(tmp>two)
    {
      two = tmp;
      pp = {st, _%n+1};
    }
  }
  if(one>ans) ans = one, pos = {vec.back()%n+1, vec.front()};
  if(two+sz(vec)>ans) ans = two+sz(vec), pos = pp;
  cout << ans << '\n';
  cout << pos.fi << ' ' << pos.se << '\n';
  return 0;
}