QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #555819 | #9245. Bracket Sequence | JZYZ# | WA | 1034ms | 309628kb | C++14 | 6.8kb | 2024-09-10 10:27:00 | 2024-09-10 10:27:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
x=(f?-x:x);
}
const int N = 1e5+7;
const int M = 1e6+7;
int n,m;
char s[N];
struct Query
{
int op,l,r,k;
}Q[M];
int ans[M];
const int mod = 998244353;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int sub(int a,int b){return a-b<0?a-b+mod:a-b;}
inline void plu(int &a,int b){ a=(a+b>=mod?a+b-mod:a+b);}
inline int mul(int a,int b){return 1ll*a*b%mod;}
int f[N][22][2][2][2][2],g[N][22][2][2][2][2];
void calc1(int l,int r,int mid)
{
for(int i=mid+1;i<=r;i++)
{
for(int j=0;j<=20;j++)
for(int cl=0;cl<=1;cl++)
for(int cr=0;cr<=1&&j+cl+cr<=20;cr++)
if(f[i-1][j][cl][cr][0][0])
{
int v=f[i-1][j][cl][cr][0][0];
int wr=f[i-1][j][cl][cr][0][1];
int wl=f[i-1][j][cl][cr][1][0];
int wlr=f[i-1][j][cl][cr][1][0];
int t=j+cl+cr;
plu(f[i][j][cl][cr][0][0],v);
plu(f[i][j][cl][cr][0][1],wr);
plu(f[i][j][cl][cr][1][0],wl);
plu(f[i][j][cl][cr][1][1],wlr);
if(t==0)
{
if(s[i]=='(')
{
plu(f[i][0][0][1][0][0],1);
plu(f[i][0][0][1][1][0],i);
}
else
{
plu(f[i][0][1][0][0][0],1);
plu(f[i][0][1][0][0][1],i);
}
}
else
{
if(s[i]=='('&&cr==0)
{
f[i][j][cl][1][0][0]=add(f[i][j][cl][1][0][0],v);
f[i][j][cl][1][1][0]=add(f[i][j][cl][1][1][0],wl);
}
else if(s[i]==')'&&cr==1)
{
f[i][j+1][cl][0][0][0]=add(f[i][j+1][cl][0][0][0],v);
f[i][j+1][cl][0][0][1]=add(f[i][j+1][cl][0][0][1],1ll*v*i%mod);
f[i][j+1][cl][0][1][0]=add(f[i][j+1][cl][0][1][0],wl);
f[i][j+1][cl][0][1][1]=add(f[i][j+1][cl][0][1][1],1ll*wl*i%mod);
}
}
}
}
}
void calc2(int l,int r,int mid)
{
for(int i=mid;i>=l;i--)
{
for(int j=0;j<=20;j++)
for(int cl=0;cl<=1;cl++)
for(int cr=0;cr<=1&&j+cl+cr<=20;cr++)
if(g[i+1][j][cl][cr][0][0])
{
int v=g[i+1][j][cl][cr][0][0];
int wr=g[i+1][j][cl][cr][0][1];
int wl=g[i+1][j][cl][cr][1][0];
int wlr=g[i+1][j][cl][cr][1][1];
int t=j+cl+cr;
plu(g[i][j][cl][cr][0][0],v);
plu(g[i][j][cl][cr][0][1],wr);
plu(g[i][j][cl][cr][1][0],wl);
plu(g[i][j][cl][cr][1][1],wlr);
if(t==0)
{
if(s[i]==')')
{
plu(g[i][0][0][1][0][0],1);
plu(g[i][0][0][1][1][0],i);
}
else
{
plu(g[i][0][1][0][0][0],1);
plu(g[i][0][1][0][0][1],i);
}
}
else
{
if(s[i]==')'&&cr==0)
{
g[i][j][cl][1][0][0]=add(g[i][j][cl][1][0][0],v);
g[i][j][cl][1][1][0]=add(g[i][j][cl][1][1][0],wl);
}
else if(s[i]=='('&&cr==1)
{
g[i][j+1][cl][0][0][0]=add(g[i][j+1][cl][0][0][0],v);
g[i][j+1][cl][0][0][1]=add(g[i][j+1][cl][0][0][1],1ll*v*i%mod);
g[i][j+1][cl][0][1][0]=add(g[i][j+1][cl][0][1][0],wl);
g[i][j+1][cl][0][1][1]=add(g[i][j+1][cl][0][1][1],1ll*wl*i%mod);
}
}
}
}
}
void solve(int l,int r,vector<int> q)
{
if(q.empty()||l==r)return;
int mid=(l+r)>>1;
vector<int> ql,qr;
for(int i=l;i<=r;i++)
for(int j=0;j<=20;j++)
for(int cl=0;cl<=1;cl++)
for(int cr=0;cr<=1;cr++)
for(int c=0;c<=1;c++)
for(int t=0;t<=1;t++)
f[i][j][cl][cr][c][t]=g[i][j][cl][cr][c][t]=0;
f[mid][0][0][0][0][0]=1;g[mid+1][0][0][0][0][0]=1;
calc1(l,r,mid);calc2(l,r,mid);
for(int u:q)
{
if(Q[u].r<=mid)ql.push_back(u);
else if(Q[u].l>mid)qr.push_back(u);
else
{
int k=Q[u].k,L=Q[u].l,R=Q[u].r;
//cout<<L<<' '<<mid<<' '<<R<<endl;
if(Q[u].op==1)
{
int res=0;
for(int i=0;i<=k;i++)
for(int c=0;i+c<=k&&c<=1;c++)
{
res=add(res,1ll*g[L][i][c][0][0][0]*f[R][k-i-c][c][0][0][0]%mod);
}
ans[u]=res;
}
else
{
int res=0;
for(int i=0;i<=k;i++)
for(int c=0;i+c<=k&&c<=1;c++)
{
if((i+c>0)&&(k-i>0))
{
// -r*l
// (R+1)*l
// r*(L-1)
// -(R+1)*(L-1)
res=sub(res,1ll*g[L][i][c][0][0][1]*f[R][k-i-c][c][0][0][1]%mod);
res=add(res,1ll*g[L][i][c][0][0][1]*f[R][k-i-c][c][0][0][0]%mod*(R+1)%mod);
res=add(res,1ll*g[L][i][c][0][0][0]*f[R][k-i-c][c][0][0][1]%mod*(L-1)%mod);
res=sub(res,1ll*g[L][i][c][0][0][0]*f[R][k-i-c][c][0][0][0]%mod*(R+1)%mod*(L-1)%mod);
}
}
// cout<<res<<endl;
res=sub(res,1ll*g[L][k][0][0][1][1]);
// cout<<mod-res<<endl;
res=add(res,1ll*g[L][k][0][0][0][1]*(R+1)%mod);
res=add(res,1ll*g[L][k][0][0][1][0]*(L-1)%mod);
res=sub(res,1ll*g[L][k][0][0][0][0]*(R+1)%mod*(L-1)%mod);
// cout<<res<<endl;
res=sub(res,1ll*f[R][k][0][0][1][1]);
res=add(res,1ll*f[R][k][0][0][1][0]*(R+1)%mod);
res=add(res,1ll*f[R][k][0][0][0][1]*(L-1)%mod);
res=sub(res,1ll*f[R][k][0][0][0][0]*(R+1)%mod*(L-1)%mod);
ans[u]=res;
}
}
}
solve(l,mid,ql);
solve(mid+1,r,qr);
}
int main()
{
//freopen("a.in","r",stdin);
read(n);read(m);
scanf("%s",s+1);
vector<int> que;
for(int i=1;i<=m;i++)
{
int l,r;
read(Q[i].op);read(Q[i].l);read(Q[i].r);read(Q[i].k);
if(Q[i].l==Q[i].r);
else que.push_back(i);
}
solve(1,n,que);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9884kb
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
Wrong Answer
time: 1034ms
memory: 309628kb
input:
100000 1000000 )())))))())()()()(())))()())))()))))())))))()(()()))()()))((()()))()))((())(())())()(()))))()))(()()()()()(())(()((()))()((()(()))()))()))()()))(())))()()(()(()())())((()((()((())()(()()))())(())())())))))))((())(((()(())())))(()(((())())))(((((((((()))()())())(()))(())()()()()((()())...
output:
807252937 516672025 801233608 122104482 597950507 367388355 742407307 711313822 392529556 736028324 426329153 185631177 315566541 444655931 76394527 216715407 932170665 421574025 504793504 302716489 498728925 1522883 415727638 78253278 202019138 222150387 605305965 645197364 340780822 416112575 4372...
result:
wrong answer 2nd lines differ - expected: '333653009', found: '516672025'