QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288415 | #7876. Cyclic Substrings | ckiseki# | TL | 0ms | 0kb | C++20 | 2.2kb | 2023-12-22 17:02:23 | 2023-12-22 17:02:24 |
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 + 1);
for (int i = 0; i < n; i++) {
cin >> a[i + 1];
}
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 + 1]; k++) {
for (int l = 1; l <= j; l++) {
int nj = l + k;
int num = a[i + 1] - 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 + 1];
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