QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #636687 | #9245. Bracket Sequence | ucup-team4153 | RE | 2ms | 13752kb | C++14 | 5.7kb | 2024-10-13 01:53:54 | 2024-10-13 01:53:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 1e5 + 7;
int n, q;
int a[N];
string str;
vector<array<int, 5> > Q[N];
vector<int> ans;
int f[N][42][2], g[N][42][2], h[N][42][2], s[N][42][2];
int add(int k, int L, int R, int l, int r) {
int mid = (L + R) >> 1;
if (l <= mid && r > mid)return k;
if (r <= mid)return add(k << 1, L, mid, l, r);
return add(k << 1 | 1, mid + 1, R, l, r);
}
void clear(int l, int r) {
for (int i = l; i <= r; i++) {
for (int j = 0; j <= 40; j++) {
for (int k = 0; k < 2; k++)f[i][j][k] = g[i][j][k] = h[i][j][k] = 0;
}
}
}
void add(int &x, int y) {
y = (y + mod) % mod;
x = (x + y) % mod;
}
void solve(int k, int l, int r) {
if (l == r)return;
clear(l, r);
int mid = (l + r) >> 1;
for (int i = mid; i >= l; i--) {
for (int j = 1; j <= 40; j++) {
for (int k = 0; k < 2; k++) {
int x = k;
if (j & 1)x ^= 1;
if (a[i] == x && i + 1 <= mid) {
add(f[i][j + 1][k], f[i + 1][j][k]);
add(g[i][j + 1][k], g[i + 1][j][k]);
}
if (i + 1 <= mid) {
add(f[i][j][k], f[i + 1][j][k]);
add(g[i][j][k], g[i + 1][j][k]);
}
}
}
add(f[i][1][a[i]], 1);
add(g[i][1][a[i]], i);
for (int j = 1; j <= 40; j++) {
for (int k = 0; k < 2; k++) {
if (i == mid) {
h[i][j][k] = 1ll * f[i][j][k] * i % mod;
s[i][j][k] = 1ll * g[i][j][k] * i % mod;
} else {
h[i][j][k] = (h[i + 1][j][k] + 1ll * (f[i][j][k] - f[i + 1][j][k] + mod) * i) % mod;
s[i][j][k] = (s[i + 1][j][k] + 1ll * (g[i][j][k] - g[i + 1][j][k] + mod) * i) % mod;
}
}
}
}
for (int i = mid + 1; i <= r; i++) {
for (int j = 1; j <= 40; j++) {
for (int k = 0; k < 2; k++) {
int x = k;
if (j & 1)x ^= 1;
if (a[i] == x && i - 1 > mid) {
add(f[i][j + 1][k], f[i - 1][j][k]);
add(g[i][j + 1][k], g[i - 1][j][k]);
}
if (i - 1 > mid) {
add(f[i][j][k], f[i - 1][j][k]);
add(g[i][j][k], g[i - 1][j][k]);
}
}
}
add(f[i][1][a[i]], 1);
add(g[i][1][a[i]], i);
for (int j = 1; j <= 40; j++) {
for (int k = 0; k < 2; k++) {
if (i == mid + 1) {
h[i][j][k] = 1ll * f[i][j][k] * i % mod;
s[i][j][k] = 1ll * g[i][j][k] * i % mod;
} else {
h[i][j][k] = (h[i - 1][j][k] + 1ll * (f[i][j][k] - f[i - 1][j][k] + mod) * i) % mod;
s[i][j][k] = (s[i - 1][j][k] + 1ll * (g[i][j][k] - g[i - 1][j][k] + mod) * i) % mod;
}
}
}
}
// return;
for (auto [type,l,r,x,id]: Q[k]) {
// cout << id << "\n";
if (type == 1) {
add(ans[id], f[l][2 * x][1]);
add(ans[id], f[r][2 * x][0]);
for (int j = 1; j < 2 * x; j++) {
for (int k = 0; k < 2; k++) {
if (k ^ (j & 1) ^ 1)continue;
add(ans[id], 1ll * f[l][j][k] * f[r][2 * x - j][k ^ 1] % mod);
}
}
} else {
add(ans[id], -1ll * f[l][2 * x][1] * (l - 1) % mod * (r + 1) % mod);
add(ans[id], 1ll * h[l][2 * x][1] * (r + 1) % mod);
add(ans[id], 1ll * g[l][2 * x][1] * (l - 1) % mod);
add(ans[id], -s[l][2 * x][1]);
// cout << f[l][2 * x][1] << " " << h[l][2][1] << " " << g[l][2 * x][1] << " " << s[l][2 * x][1] << "\n";
add(ans[id], -1ll * f[r][2 * x][0] * (l - 1) % mod * (r + 1) % mod);
add(ans[id], 1ll * h[r][2 * x][0] * (l - 1) % mod);
add(ans[id], 1ll * g[r][2 * x][0] * (r + 1) % mod);
add(ans[id], -s[r][2 * x][0]);
// cout << f[r][2 * x][-] << " " << h[r][2][0] << " " << g[l][2 * x][1] << " " << s[l][2 * x][1] << "\n";
// cout << ans[id] << "\n";
for (int j = 1; j < 2 * x; j++) {
for (int k = 0; k < 2; k++) {
if (k ^ (j & 1) ^ 1)continue;
add(ans[id], -1ll * f[l][j][k] * f[r][2 * x - j][k ^ 1] % mod * (l - 1) % mod * (r + 1) % mod);
add(ans[id], 1ll * h[l][j][k] * f[r][2 * x - j][k ^ 1] % mod * (r + 1) % mod);
add(ans[id], 1ll * f[l][j][k] * h[r][2 * x - j][k ^ 1] % mod * (l - 1) % mod);
add(ans[id], -1ll * h[l][j][k] * h[r][2 * x - j][k ^ 1] % mod);
// cout << f[l][j][k] << " " << h[l][j][k] << " " << f[r][2 * x - j][k ^ 1] << " " << h[r][2 * x - j][
// k ^ 1] << " " << k << "\n";
// cout << ans[id] << "\n";
}
}
}
}
solve(k << 1, l, mid);
solve(k << 1 | 1, mid + 1, r);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q >> str;
str = " " + str;
for (int i = 1; i <= n; i++)a[i] = (str[i] == ')');
ans.resize(q + 1, 0);
for (int i = 1; i <= q; i++) {
int type, l, r, k;
cin >> type >> l >> r >> k;
if (l == r)continue;
Q[add(1, 1, n, l, r)].push_back({type, l, r, k, i});
}
solve(1, 1, n);
for (int i = 1; i <= q; i++)cout << ans[i] << "\n";
return 0;
}
/*
5 1
(()()
2 3 5 1
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13752kb
input:
5 20 (()() 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 2 3 1 1 2 4 1 1 2 5 1 1 3 4 1 1 3 5 1 1 4 5 1 2 1 3 1 2 1 4 1 2 1 5 1 2 2 3 1 2 2 4 1 2 2 5 1 2 3 5 1 2 4 5 1 1 1 5 2 2 1 5 2
output:
0 2 2 5 1 1 3 0 1 1 3 6 16 1 2 7 2 1 2 3
result:
ok 20 lines
Test #2:
score: -100
Runtime Error
input:
100000 1000000 )())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...