QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288410#7876. Cyclic Substringsckiseki#TL 0ms0kbC++202.1kb2023-12-22 16:59:182023-12-22 16:59:19

Judging History

你现在查看的是最新测评结果

  • [2023-12-22 16:59:19]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-12-22 16:59:18]
  • 提交

answer

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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#include <experimental/iterator>
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

const int mod = 998244353;
int add(int a, int b) {
  return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
  return a - b < 0 ? a - b + mod : a - b;
}
int mul(int64_t a, int64_t b) {
  return static_cast<int>(a * b % mod);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  const int m = accumulate(all(a), 0);

  vector<int> fac(m), ifac(m), inv(m);
  inv[1] = 1;
  for (int i = 2; i < m; i++)
    inv[i] = mul(inv[mod % i], mod - mod / i);
  for (int i = 1; i < m; i++) {
    fac[i] = mul(fac[i - 1], i);
    ifac[i] = mul(ifac[i - 1], inv[i]);
  }

  const auto choose = [&](int N, int k) -> int {
    if (k < 0 || N < k) return 0;
    return mul(fac[N], mul(ifac[k], ifac[N - k]));
  };

  auto dp = vector(n + 1, vector(m + 1, 0));
  dp[0][0] = 1;

  for (int i = 0; i < n; i++) {
    debug(i);
    orange(all(dp[i]));
    for (int j = 0; j <= m; j++) {

      for (int k = 0; k < a[i]; k++) {
        for (int l = 1; l <= j; l++) {
          int nj = l + k;
          int num = a[i] - k - 1;
          int hole = j - l + 1;
          int coef = choose(num + hole - 1, hole - 1);
          if (nj <= m)
            dp[i + 1][nj] = add(dp[i + 1][nj],
                mul(dp[i][j], coef));
        }
      }

      {
        int nj = j + a[i];
        if (nj <= m)
          dp[i + 1][nj] = add(dp[i + 1][nj], dp[i][j]);
      }
    }
  }

  int ans = 0;
  for (int j = 0; j <= m; j++)
    ans = add(ans, dp[n][j]);
  cout << ans << '\n';

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

5
01010

output:


result: