2021年蓝桥杯省赛B组题解（C/C++）

来自微信公众号：算法梦工厂，二维码见文末。可关注公众号获取往年试题题解。

试题 A: 空间

涉及知识点：计算机基础知识

答案：67108864

主要考察一些计算机的基础知识， 32 32 32 位二进制数需要占 4 4 4 个字节， 256 M B = 256 ∗ 1024 K B = 256 ∗ 1024 ∗ 1024 256MB = 256*1024KB = 256*1024*1024 256MB=256∗1024KB=256∗1024∗1024 字节，所以一共可以存储的 32 32 32 位二进制整数的数量就是： 256 ∗ 1024 ∗ 1024 / 4 = 67108864 256*1024*1024/4 = 67108864 256∗1024∗1024/4=67108864 。

#include <bits/stdc++.h>
int main() {
  printf("%d", 256 * 1024 * 1024 / 4);
  return 0;
}

---

试题 B: 卡片

答案：3181

• 涉及知识点：枚举，十进制拆分
• 做法：初始化 res_num 数组记录当前每种卡牌剩余数量，从1向上枚举需要组合的卡片，直到剩余卡片不足则停止累加，最后成功组合成的卡片即为答案。

#include <bits/stdc++.h>
using namespace std;

vector<int> Split(int x) { // 将x按照十进制拆分每一位
  vector<int> ret;
  if (x == 0) {
    ret.push_back(0);
    return ret;
  }
  while (x > 0) {
    ret.push_back(x % 10);
    x /= 10;
  }
  return ret;
}

const int maxn = 2021;
int rest_num[10] = {0}; // 记录当前每种数字卡牌剩余数量

bool Sub(const vector<int> &x) { // 将当前需要的数字卡牌从卡牌库中去除，卡牌库剩余卡牌不足则返回false
  for (unsigned int i = 0; i < x.size(); i++) {
    rest_num[x[i]]--;
    if (rest_num[x[i]] < 0) {
      return false;
    }
  }
  return true;
}

int main() {
  for (int i = 0; i < 10; i++) {
    rest_num[i] = maxn;
  }
  int ans = 1;
  while (1) { // 尝试利用剩余卡牌组合出数字ans，剩余卡牌不足则跳出循环
    vector<int> need = Split(ans);
    bool succFlag = Sub(need);
    if (!succFlag) {
      break;
    }
    ans++;
  }
  printf("ans = %d\n", ans - 1);
  return 0;
}

---

试题 C: 直线

答案：40257

• 涉及知识点：枚举、浮点数判
• 做法：
  • 枚举所有点的两两组合，对于每一对两个点的组合就确定了一条直线，对于每条直线都判断其是否和之前已经出现过的直线相同，如果相同则忽略。
  • 判断两个直线是否相同的做法：每个直线存储直线上两个点，对于直线 L 0 ( p 0 , p 1 ) L_0(p_0,p_1) L0​(p0​,p1​) 和直线 L 1 ( p 2 , p 3 ) L_1(p_2,p_3) L1​(p2​,p3​)，当且仅当点 p 2 p_2 p2​ 和 p 3 p_3 p3​ 均在直线 L 1 L_1 L1​ 上，则直线 L 1 L_1 L1​ ， L 2 L_2 L2​ 重合。
  • 判断一个点是否在直线上的做法：假设存在点 p 2 p_2 p2​ 和直线 L ( p 0 , p 1 ) L(p_0,p_1) L(p0​,p1​)，如果三个点两两之间的距离 a + b = c a+b=c a+b=c，则说明三个点在一条直线上。（注意这里判断距离相等因为是浮点类型可能存在误差，所以不可以之间判断是否相等，而是需要判断两个浮点数之间的差是否小于一个较小值，如： 1 0 − 7 10^{-7} 10−7）。

#include <bits/stdc++.h>
using namespace std;
struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) {
    this->x = x;
    this->y = y;
  }
};

struct Line {
  Point a, b;
  Line(Point a, Point b) {
    this->a = a;
    this->b = b;
  }
};

vector<Line> lineList;

double Dis(Point p0, Point p1) { // 计算点p0和p1之间的直线距离
  return sqrt((p0.x - p1.x) * (p0.x - p1.x) + (p0.y - p1.y) * (p0.y - p1.y));
}

bool CheckPointInLine(Line x, Point p) { // 检查点p是否在直线x上
  double dis[3];
  dis[0] = Dis(x.a, x.b);
  dis[1] = Dis(x.a, p);
  dis[2] = Dis(x.b, p);
  sort(dis, dis + 3);
  if (fabs(dis[0] + dis[1] - dis[2]) < 1e-5) { // 三点在一条直线则较短两距离相加等于较长距离
    return true;
  } else {
    return false;
  }
}

// 检查当先直线cur是否和之前已经出现过得直线集合（lineList）中的某一直线重合
bool CheckLineRepeat(Line cur) {
  for (unsigned int i = 0; i < lineList.size(); i++) {
    if (CheckPointInLine(lineList[i], cur.a) &&
        CheckPointInLine(lineList[i], cur.b)) {
      return true;
    }
  }
  return false;
}

int main() {
  vector<Point> pointList;
  // 将所有点记入pointList中
  for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 21; j++) { 
      pointList.push_back(Point(i, j));
    }
  }

  // 尝试任意两点的组合组成的直线，如果直线没出现过则记录下来，否则跳过
  int ans = 0;
  for (unsigned int i = 0; i < pointList.size(); i++) {
    for (unsigned int j = i + 1; j < pointList.size(); j++) {
      Line curLine = Line(pointList[i], pointList[j]);
      if (!CheckLineRepeat(curLine)) {
        ans++;
        lineList.push_back(curLine);
      }
    }
  }
  printf("ans = %d\n", ans);
  return 0;
}

---

试题 D: 货物摆放

答案：2430

• 涉及知识点：质因数分解
• 做法：
  1. 问题可以转化成，将 2021041820210418 2021041820210418 2021041820210418 分解成三个数 a ∗ b ∗ c a*b*c a∗b∗c 的形式，有多少种拆分方法。
  2. 将 2021041820210418 2021041820210418 2021041820210418 质因数分解成： p 0 n 0 ∗ p 1 n 1 ∗ . . . ∗ p n n n p_0^{n_0} *p_1^{n_1}* ... *p_n^{n_n} p0n0​​∗p1n1​​∗...∗pnnn​​ 的形式（其中 p 0 , p 1 , . . . , p n p_0, p_1, ... , p_n p0​,p1​,...,pn​ 均为质数），可得： 2021041820210418 = 2 1 ∗ 3 3 ∗ 1 7 1 ∗ 13 1 1 ∗ 285 7 1 ∗ 588235 3 1 2021041820210418 = 2^1* 3^3 *17^1* 131^1 *2857^1* 5882353^1 2021041820210418=21∗33∗171∗1311∗28571∗58823531 。
  3. 对于质因数： 2 , 17 , 131 , 2857 , 5882353 2,17,131,2857,5882353 2,17,131,2857,5882353 ，每个均可以分别分配给 a , b , c a,b,c a,b,c 三个位置，所以总共方法数是 3 5 3^5 35 。
  4. 对于出现了 3 3 3 次的质数 3 3 3 ，可以枚举出其所有的分配方式，共10种。故总方法数为： 3 5 ∗ 10 = 2430 3^5 * 10 = 2430 35∗10=2430 。

#include <bits/stdc++.h>
using namespace std;

vector<long long int> primeNum, primeVal;
// 将x质因数分解
void CalaPrime(long long int x) {
  printf("%lld = ", x);
  for (long long int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int num = 0;
      while (x % i == 0) {
        x /= i;
        num++;
      }
      primeNum.push_back(num);
      primeVal.push_back(i);
    }
  }
  if (x > 1) {
    primeNum.push_back(1);
    primeVal.push_back(x);
  }

  for (unsigned int i = 0; i < primeNum.size(); i++) {
    if (i != 0) {
      printf("  *  ");
    }
    printf("\n(%lld ^ %lld)", primeVal[i], primeNum[i]);
  }
  printf("\n");
}

int main() {
  CalaPrime(2021041820210418);

  long long int ans = 0;
  ans = 3 * 3 * 3 * 3 * 3;
  ans *= 10;

  printf("ans = %lld\n", ans);
  return 0;
}

---

试题 E: 路径

答案：10266837

• 涉及算法：图论，最短路，最大公约数
• 做法：
  1. 建图：共2021个结点组成的图，枚举任意两点组合，通过计算最大公约数，记录这两个点之间的距离，即增加一条边。
  2. 公式： l c m ( x , y ) = x ∗ y g c d ( x , y ) lcm(x,y) = \frac {x*y} {gcd(x,y)} lcm(x,y)=gcd(x,y)x∗y​ （ l c m ( x , y ) lcm(x,y) lcm(x,y) 表示 x x x 和 y y y 的最小公倍数， g c d ( x , y ) gcd(x,y) gcd(x,y) 表示 x x x 和 y y y 的最大公约数）
  3. 最短路求解：可以使用Floyd算法或DijkStra算法计算最短路。（这里因为是填空题，建议使用Floyd算法更加好写，可以考虑两个算法都实现用来相互验证）

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2021;

vector<int> u[maxn + 52];
vector<int> v[maxn + 52];
int disDijk[maxn + 52];
int disFloyd[maxn + 52][maxn + 52];
bool vis[maxn + 52];

// 初始化建图，u[i][j]表示i的第j条出边编号，v[i][j]表示i的第j条边的长度，也就是i和u[i][j]的距离
void InitGroup() {
  for (int i = 1; i <= maxn; i++) {
    for (int j = i + 1; j <= maxn; j++) {
      if (j - i <= 21) {
        u[i].push_back(j);
        v[i].push_back(i * j / __gcd(i, j));
        u[j].push_back(i);
        v[j].push_back(i * j / __gcd(i, j));
      }
    }
  }
}

// floyd算法计算最短路，disFloyd[i][j] 表示i到j的最短距离
void Floyd() {
  // 初始化disFloyd为一个较大值
  memset(disFloyd, 0x3f, sizeof(disFloyd));
  for (unsigned int i = 1; i <= maxn; i++) {
    for (unsigned int j = 0; j < v[i].size(); j++) {
      disFloyd[i][u[i][j]] = v[i][j];
      disFloyd[u[i][j]][i] = v[i][j];
    }
  }

  // 执行floyd算法
  for (int k = 1; k <= maxn; k++) {
    for (int i = 1; i <= maxn; i++) {
      for (int j = 1; j <= maxn; j++) {
        disFloyd[i][j] = disFloyd[j][i] = min(disFloyd[i][j], disFloyd[i][k] + disFloyd[k][j]);
      }
    }
  }
  printf("floyd ans = %d\n", disFloyd[1][maxn]);
}

// Dijkstra算法计算最短路，disDijk[i]表示i距离结点1的最短距离
void Dijkstra() {
  memset(disDijk, 0x3f, sizeof(disDijk));
  memset(vis, 0, sizeof(vis));

  disDijk[1] = 0;

  for (int i = 1; i <= maxn; i++) {
    int curMin = 0x3f3f3f3f;
    int curIndex = -1;
    for (int j = 1; j <= maxn; j++) {
      if (vis[j]) {
        continue;
      }
      if (curMin > disDijk[j] || curIndex == -1) {
        curMin = disDijk[j];
        curIndex = j;
      }
    }
    vis[curIndex] = true;

    for (unsigned int j = 0; j < u[curIndex].size(); j++) {
      int t = u[curIndex][j], val = v[curIndex][j];
      disDijk[t] = min(disDijk[t], disDijk[curIndex] + val);
    }
  }
  printf("Dijkstra ans = %d  vis = %d\n", disDijk[2021], vis[2021]);
}

int main() {
  InitGroup();
  Floyd();
  Dijkstra();

  return 0;
}

---

试题 F: 时间显示

涉及知识点：取模，时间计算，格式化输出

注意题目中给定的是毫秒，利用整除和取模就可以完成计算。具体细节可以参照代码中的注释。

#include <bits/stdc++.h>
using namespace std;

int main() {

  long long int dayMs = 24 * 60 * 60 * 1000; //一天包含多少毫秒
  long long int n;
  scanf("%lld", &n);

  // 扣除整天的描述之后，得到最后一天剩下了多少毫秒
  n = n % dayMs;
  // 忽略毫秒，得到还剩多少秒
  n = n / 1000;

  // 一小时3600秒，走过了多少个完整的3600秒就代表当前小时数是多少
  int hour = n / (3600);

  // 扣除整小时之后剩下的秒数，可以走过多少个完整的60秒就代表当前分钟数是多少
  int minutes = (n - hour * 3600) / 60;

  // 走完全部的完整60秒之后剩下的秒数就是秒数
  int second = n % 60;

  printf("%02d:%02d:%02d\n", hour, minutes, second);
}

---

试题 G: 砝码称重

1. 涉及知识点：动态规划，类背包问题

2. 思路一：问题可以转化成：给定 n n n 个正整数，计算从中选出若个数字组合，每个数字可以加或者减，最终能得到多少种正整数结果。

   • 状态定义： d p ( i , j ) dp(i,j) dp(i,j) 表示前 i i i 个数字选择若干个加或者减，能否获得和为 j j j 。( − 1 0 5 ≤ j ≤ 1 0 5 -10^5\le j \le 10^5 −105≤j≤105 )
   • 状态转移方程： d p ( i , j ) = d p ( i − 1 , j ) ∣ d p ( i − 1 , j − a [ i ] ) ∣ d p ( i − 1 , j + a [ i ] ) dp(i,j) = dp(i-1,j) | dp(i-1, j-a[i]) | dp(i-1,j+a[i]) dp(i,j)=dp(i−1,j)∣dp(i−1,j−a[i])∣dp(i−1,j+a[i]) 。
   • 初始状态： d p ( 0 , 0 ) = 1 dp(0,0) = 1 dp(0,0)=1 。
   • 时间复杂度分析：状态数 n ∗ s u m ∗ 2 n*sum* 2 n∗sum∗2 ，状态转移方程复杂度 O ( 1 ) O(1) O(1) ，总时间复杂度 O ( n ∗ s u m ) O(n*sum) O(n∗sum) ， s u m sum sum 表示所有数总和的最大值为 1 0 5 10^5 105 。

3. 思路二：问题还可以转化成：给定 2 ∗ n 2*n 2∗n 个正整数， a 0 , a 1 , . . . , a n , − a 0 , − a 1 , . . . , − a n a_0,a_1,...,a_n,-a_0,-a_1,...,-a_n a0​,a1​,...,an​,−a0​,−a1​,...,−an​ ，每个数字可以选或者不选，问相加可以组合成多少种不同的正整数。这样就是一个经典的01背包问题了，只要注意一下负数问题即可。

4. 其它技巧注意事项：

   1. 利用滚动数组，反复交换 c u r cur cur 和 p r e pre pre 来节约空间。
   2. 使用 o f f s e t offset offset 偏移来保证 d p dp dp 过程中可以记录获取负数重量的可能性，以便后续转移。

#include <bits/stdc++.h>
using namespace std;

const int offset = 100052; // 为处理负数情况引入的偏移量
const int maxn = 100052 + offset;
int n, vis[2][maxn], a[2000];

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }

  memset(vis, 0, sizeof(vis));
  vis[0][offset] = 1;
  int pre = 0, cur = 1;

  // 三种情况分别是，不选择a[i]，选择a[i]，选择-a[i]
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < maxn; j++) {
      vis[cur][j] = max(vis[cur][j], vis[pre][j]);
      if (j - a[i] >= 0) {
        vis[cur][j] = max(vis[pre][j - a[i]], vis[cur][j]);
      }
      if (j + a[i] < maxn) {
        vis[cur][j] = max(vis[pre][j + a[i]], vis[cur][j]);
      }
    }
    swap(pre, cur); // 滚动循环利用数组的pre行和cur行
  }

  // 注意要从offset+1开始，因为能称出来的重量不应该是负数
  int ans = 0;
  for (int i = offset + 1; i < maxn; i++) {
    if (vis[pre][i]) {
      ans++;
    }
  }
  printf("%d", ans);
  return 0;
}

---

试题 H: 杨辉三角形

涉及知识点：二分，组合数计算，打表

这里其实需要知道或者自己分析出一些杨辉三角的性质，首先为了方便表示，将这个杨辉三角表示成这种形式：

第 i i i 行第 j j j 个数表示成 c ( i , j ) c(i,j) c(i,j) ，行数和列数都从 0 0 0 开始计算。
可以发现如下的结论：

1. c ( n , m ) = n ! m ! ∗ ( n − m ) ! c(n,m) = \frac{n!}{m!*(n-m)!} c(n,m)=m!∗(n−m)!n!​
2. c ( n , m ) = c ( n , n − m ) c(n,m) = c(n,n-m) c(n,m)=c(n,n−m)
3. c ( n , m ) = c ( n − 1 , m − 1 ) + c ( n − 1 , m ) c(n,m) = c(n-1,m-1) + c(n-1,m) c(n,m)=c(n−1,m−1)+c(n−1,m)

考虑到每一行是对称的，所以如果如果一个数字在某一行的右半边出现，那么它一定也在这一行的左半边出现，因此每一行右半边的数字一定不会作为第一个出现的数字。此外可以发现 c ( i , 1 ) = i c(i,1) = i c(i,1)=i ，所以任意一个数字 n n n 一定会在这个杨辉三角矩阵中出现过。另外根据上面的公式1可以发现，每一行的数字都是呈现一个先增后减的形式，并且增长速度极快。每一列数字则是完全单调递增的。因此可以尝试在每一列二分搜索是否有该数字。只需要考虑前 20 20 20 列即可，因为后面的数字大小已经完全超过了 n n n 的最大范围，所以一定不会等于 n n n。

#include <bits/stdc++.h>
using namespace std;

// 打印杨辉三角前x行，帮助直观感受
void Print(int x) {
  long long int c[100][100];

  for (int i = 1; i <= x; i++) {
    c[i][0] = 1;
    printf("%lld\t", c[i][0]);
    for (int j = 1; j < i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      printf("%lld\t", c[i][j]);
    }
    printf("\n");
  }
}

// 二分方法
long long int n;
long long int C(long long int a, long long int b) {
  long long int ret = 1;
  for (long long int i = a, j = 1; j <= b; i--, j++) {
    ret = ret * i / j;
    if (ret > n) {
      return n + 1;
    }
  }
  return ret;
}

long long int GetAns(int col) {
  long long int l = col, r = max(n, (long long int)col);
  while (l < r) {
    long long int mid = (l + r) / 2;
    if (C(mid, col) >= n)
      r = mid;
    else
      l = mid + 1;
  }

  if (C(r, col) != n) { // 没有出现则返回出现位置无限大
    return 4e18;
  } else {
    return r * (r + 1) / 2 + col + 1;
  }
}

int main() {
  scanf("%lld", &n);

  long long int ans = 4e18;
  for (int i = 0; i < 20; i++) { // 枚举前20列，记录最早出现位置
    long long int cur = GetAns(i);
    ans = min(ans, cur);
  }

  printf("%lld\n", ans);
  return 0;
}

---

试题 I: 双向排序

涉及知识点：贪心，线段树，排序

此题完全通过较为困难，此处给出简单版本使用sort函数代码。可以考虑，对于连续的0操作或者1操作，只需要执行覆盖数组长度最长的操作即可，这样就可以一定程度上减少操作次数，从而提高程序运行效率。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100052;
int a[maxn];
bool cmp(int x, int y) { return x > y; }

struct Oper {
  int pos, op;
};

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    a[i] = i + 1;
  }

  // 读取操作列表
  vector<Oper> opList;
  for (int i = 0; i < m; i++) {
    Oper temp;
    scanf("%d%d", &temp.op, &temp.pos);
    opList.push_back(temp);
  }

  // 操作去重转变成01交错的操作序列
  vector<Oper> newList;
  Oper curOp = opList[0];
  for (unsigned int i = 0; i < opList.size(); i++) {
    if (curOp.op != opList[i].op) { // 操作01转换则保存当前等价操作并重新记录
      newList.push_back(curOp);
      curOp = opList[i];
      continue;
    }
    if (opList[i].op == 0 && opList[i].pos > curOp.pos) {
      curOp = opList[i];
    }
    if (opList[i].op == 1 && opList[i].pos < curOp.pos) {
      curOp = opList[i];
    }
  }
  newList.push_back(curOp);

  // 模拟执行操作
  for (unsigned int i = 0; i < newList.size(); i++) {
    if (newList[i].op == 0) {
      sort(a, a + newList[i].pos, cmp);
    } else {
      sort(a + newList[i].pos - 1, a + n);
    }
  }

  // 打印结果
  for (int i = 0; i < n; i++) {
    if (i != 0) {
      printf(" ");
    }
    printf("%d", a[i]);
  }

  return 0;
}

---

试题 J: 括号序列

1. 涉及知识点：动态规划，取模
2. 动态规划设计：
   • 状态设计： d p ( i , j ) dp(i,j) dp(i,j) 表示前 i i i 个括号插入若干个括号之后，左括号比右括号多 j j j 个的插入方法数。
   • 状态转移方程： d p ( i , j ) = d p ( i − 1 , j − 1 ) dp(i,j) = dp(i-1,j-1) dp(i,j)=dp(i−1,j−1)（ s t r i str_i stri​ 是左括号）， d p ( i , j ) = ∑ k = 0 j + 1 d p ( i − 1 , k ) dp(i,j) = \sum_{k=0}^{j+1}dp(i-1,k) dp(i,j)=∑k=0j+1​dp(i−1,k) （ s t r i str_i stri​ 是右括号）
   • 状态转移优化：当 s t r i str_i stri​ 是右括号时，因为： d p ( i , j − 1 ) = ∑ k = 0 j d p ( i − 1 , k ) dp(i,j-1) = \sum_{k=0}^{j}{dp(i-1,k)} dp(i,j−1)=∑k=0j​dp(i−1,k) ，所以 d p ( i , j ) = d p ( i − 1 , j + 1 ) + d p ( i , j − 1 ) dp(i,j) = dp(i-1,j+1) + dp(i,j-1) dp(i,j)=dp(i−1,j+1)+dp(i,j−1) 。相当于是利用一个前缀和来把 O ( n ) O(n) O(n) 的状态转移方程优化成 O ( 1 ) O(1) O(1) 。
   • 初始状态： d p ( 0 , 0 ) = 1 dp(0,0) = 1 dp(0,0)=1
3. 注意事项：要增加 v i s vis vis 数组用于表示 d p dp dp 数组每个位置取模前的实际值是否为 0 0 0 ，如果只判断 d p dp dp 值可能会出现 d p dp dp 值实际不为 0 0 0 但是因为取模恰好为 0 0 0 的情况（虽然因为这个模数的特殊性，这个情况出现的概率几乎为 0 0 0 ）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5052;
const long long int MOD = 1e9 + 7;

int dp[maxn][maxn];
bool vis[maxn][maxn];
char str[maxn];
int n;

long long int mod(long long int x) { return x % MOD; }

long long int GetAns() {
  memset(dp, 0, sizeof dp);
  memset(vis, 0, sizeof vis);
  dp[0][0] = 1;
  vis[0][0] = true;

  for (int i = 1; i <= n; i++) {
    if (str[i - 1] == '(') {
      for (int j = 1; j <= n; j++) {
        dp[i][j] = dp[i - 1][j - 1];
        vis[i][j] = vis[i - 1][j - 1];
      }
    } else {
      dp[i][0] = mod(dp[i - 1][0] + dp[i - 1][1]);
      vis[i][0] = vis[i-1][0] | vis[i-1][1];
      for (int j = 1; j <= n; j++) {
        dp[i][j] = mod(dp[i - 1][j + 1] + dp[i][j - 1]);
        vis[i][j] = vis[i - 1][j + 1] | vis[i][j - 1];
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    if (vis[n][i] != 0) {
      return dp[n][i];
    }
  }
  return -1;
}
int main() {
  scanf("%s", str);
  n = strlen(str);

  long long int ansL = GetAns();

  reverse(str, str + n);
  for (int i = 0; i < n; i++) {
    if (str[i] == ')') {
      str[i] = '(';
    } else {
      str[i] = ')';
    }
  }
  long long int ansR = GetAns();

  printf("%lld\n", mod(ansL * ansR));
  return 0;
}

获取更多题解，算法讲解欢迎关注公众号：算法梦工厂