Submission #64376825

---

Source Code Expand

#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

const ll MOD = 998244353;
ll pw(ll a, ll b) {
  ll ans = 1;
  while (b) {
    while (!(b & 1))
      b >>= 1, a = (a * a) % MOD;
    ans = (ans * a) % MOD, --b;
  }
  return ans;
}

const int N = 2e7 + 100;

ll fc[N];
ll iv[N];

void init() {
  fc[0] = 1;
  for (int i = 1; i < N; ++i) {
    fc[i] = fc[i - 1] * i % MOD;
  }
  iv[N - 1] = pw(fc[N - 1], MOD - 2);
  for (int i = N - 2; i >= 0; --i) {
    iv[i] = iv[i + 1] * (i + 1) % MOD;
  }
}

ll cnk(int n, int k) {
  if (k > n) {
    return 0;
  }
  return fc[n] * iv[k] % MOD * iv[n - k] % MOD;
}

ll solve(int x, int y) {
  if (x < 0) {
    return 0;
  }
  return cnk(x + y - 1, y - 1);
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  init();
  int n, k;
  string s;
  cin >> n >> k;
  cin >> s;
  int cnt = 0;
  int cur = 0;
  while (cur < s.size() && s[cur] == '(' && s[cur + 1] == ')') {
    cnt += 2;
    cur += 2;
  }
  if (cur == s.size()) {
    ll ans = 0;
    ll m = 1;
    for (int i = 0; i <= n - k; ++i, m = m * 2 % MOD) {
      ans = (ans + solve(n - k - i, cnt) * m) % MOD;
    }
    cout << ans << endl;
  } else {
    // starting )))
    ++cnt;
    // middle (((
    ++cnt;
    // ending ))))
    ++cnt;
    int b = 0;
    ++cur;
    ++b;
    while (b != 0) {
      if (s[cur] == '(') {
        ++b;
      } else {
        --b;
      }
      ++cur;
    }

    int blocks = 0;
    while (cur != s.size()) {
      b = 1;
      ++cur;
      while (b != 0) {
        if (s[cur] == '(') {
          ++b;
        } else {
          --b;
        }
        ++cur;
      }
      ++blocks;
    }
    // ending (((
    ++cnt;
    ll ans = 0;
    for (int i = 0; i < blocks; ++i) {
      ans = (ans + solve(n - k - 1, cnt + blocks)) % MOD;
    }
    ans = (ans + solve(n - k, cnt + blocks)) % MOD;
    cout << ans << endl;
  }
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:84:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   84 |   while (cur < s.size() && s[cur] == '(' && s[cur + 1] == ')') {
      |          ~~~~^~~~~~~~~~
Main.cpp:88:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   88 |   if (cur == s.size()) {
      |       ~~~~^~~~~~~~~~~
Main.cpp:115:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  115 |     while (cur != s.size()) {
      |            ~~~~^~~~~~~~~~~

Judge Result