QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405396 | #1286. Ternary String Counting | TulipeNoire | WA | 1ms | 3784kb | C++14 | 2.8kb | 2024-05-05 20:43:03 | 2024-05-05 20:43:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const int N=5005,mod=1000000007;
struct Matrix {
int l1,r1,l2,r2;
inline Matrix operator*(const Matrix o) {
return {max(l1,o.l1),min(r1,o.r1),max(l2,o.l2),min(r2,o.r2)};
}
}mat[N];
int n,m;
int Lj,Lk[N],Rk[N];
int Sj[N],Sk[N],f[N][N];
inline void solve() {
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++) mat[i]={0,n,0,n};
while (m--) {
int l,r,c;
scanf("%d %d %d",&l,&r,&c);
Matrix x;
if (c==1) x={0,l-1,0,l-1};
else if (c==2) x={l,n,0,l-1};
else x={l+1,n,l,n};
mat[r]=mat[r]*x;
}
// for (int i=1;i<=n;i++) {
// printf("%d %d %d %d\n",mat[i].l1,mat[i].r1,mat[i].l2,mat[i].r2);
// }
if (mat[1].l1!=0) {
puts("0");
return;
}
Lj=0;
for (int i=0;i<=n;i++) Lk[i]=0,Rk[i]=n;
for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) f[i][i]=0;
for (int i=0;i<=n;i++) Sj[i]=Sk[i]=0;
f[0][0]=Sj[0]=Sk[0]=3;
for (int i=1;i<n;i++) {
for (int k=0;k<i;k++) {
int d=(Sj[k]+Sk[k])%mod;
f[i][k]=d,Sk[k]=(Sk[k]+d)%mod,Sj[i]=(Sj[i]+d)%mod;
}
for (int j=0;j<mat[i+1].l1&&j<=i;j++) {
Sj[j]=0;
for (int k=Lk[j];k<=Rk[j];k++) {
Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
f[j][k]=0;
}
Lk[j]=n,Rk[j]=0;
}
for (int j=mat[i+1].r1+1;j<=i;j++) {
Sj[j]=0;
for (int k=Lk[j];k<=Rk[j];k++) {
Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
f[j][k]=0;
}
Lk[j]=n,Rk[j]=0;
}
for (int j=mat[i+1].l1;j<=i&&j<=mat[i+1].r1;j++) {
int L=max(Lk[j],mat[i+1].l2);
int R=min(Rk[j],mat[i+1].r2);
if (L>R) {
Sj[j]=0;
for (int k=Lk[j];k<=Rk[j];k++) {
Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
f[j][k]=0;
}
Lk[j]=n,Rk[j]=0;
} else {
for (int k=Lk[j];k<L;k++) Sj[j]=(Sj[j]-f[j][k]+mod)%mod,Sk[k]=(Sk[k]-f[j][k]+mod)%mod,f[j][k]=0;
for (int k=R+1;k<=Rk[j];k++) Sj[j]=(Sj[j]-f[j][k]+mod)%mod,Sk[k]=(Sk[k]-f[j][k]+mod)%mod,f[j][k]=0;
Lk[j]=L,Rk[j]=R;
}
}
}
// for (int i=0;i<=n;i++) {
// for (int j=0;j<=n;j++) {
// printf("%d ",f[i][j]);
// }
// puts("");
// }
int ans=0;
for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) ans=(ans+f[i][j])%mod;
printf("%d\n",ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
freopen("out", "w", stdout);
freopen("err", "w", stderr);
#endif
int T;
scanf("%d",&T);
while (T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3784kb
input:
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
output:
3 9 27 18
result:
ok 4 tokens
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3784kb
input:
741 5 3 1 5 3 3 4 2 1 4 3 4 3 2 4 2 1 4 1 2 3 3 10 3 9 10 2 3 6 3 1 9 1 3 4 2 3 2 1 3 2 2 3 3 1 3 3 10 4 6 6 1 9 10 2 4 8 3 4 10 3 6 3 1 4 3 2 4 2 2 2 2 4 3 1 4 1 1 1 2 2 3 1 5 3 4 5 2 4 5 1 1 4 3 9 3 2 3 2 1 9 2 2 4 2 4 3 1 3 3 2 3 2 1 2 3 8 4 5 8 1 4 8 1 3 5 3 1 3 3 9 3 4 5 1 1 5 3 3 8 2 8 3 5 7 2...
output:
90 60 0 0 24300 0 0 0 25068 24 384 25272 3564 1944 6480 864 144 0 0 0 0 0 0 0 6 0 0 0 0 0 96 96 6 0 0 0 0 0 576 0 108 576 0 0 2916 216 216 648 648 0 0 0 0 0 0 324 8748 1944 0 5832 0 0 0 4320 18 0 18 18 0 18 18 2880 0 0 0 0 0 0 0 1992 996 996 450 300 162 1956 108 0 0 0 864 54 54 72 12 0 300 0 1044 96...
result:
wrong answer 2nd words differ - expected: '0', found: '60'