QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403389 | #1286. Ternary String Counting | cqbzly | WA | 1ms | 3780kb | C++14 | 2.8kb | 2024-05-02 10:28:16 | 2024-05-02 10:28:16 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ull unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
const int mod=1e9+7;
int T,n,m;
int f[N][N],a[N],b[N],c[N],d,a0[N],b0[N],c0[N],d0,pl[N],pr[N];
vector<pair<int,int>>q[N];
void add(int i,int j,int x){
f[i][j]=(f[i][j]+x)%mod;
a0[i]=(a0[i]+x)%mod;
b0[j]=(b0[j]+x)%mod;
}
void del(int i,int j){
int x=f[i][j];
a0[i]=(a0[i]-x)%mod;
b0[j]=(b0[j]-x)%mod;
f[i][j]=0;
}
void sol(){
cin>>n>>m;
for(int i=1;i<=n;i++)a[i]=b[i]=c[i]=0,q[i].clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=0;
}
}
d=1;
for(int i=1;i<=m;i++){
int l,r,x;
cin>>l>>r>>x;
q[r].pb({l,x});
}
for(int i=1;i<=n;i++)pl[i]=1,pr[i]=i;
int f1=1,f2=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i-1;j++)a0[j]=a[j],b0[j]=b[j],c0[j]=c[j];
d0=0;
for(int j=1;j<=i-2;j++){
add(i-1,j,a[j]);
add(i-1,j,b[j]);
c0[i-1]=(c0[i-1]+c[j])%mod;
add(i-1,j,c[j]);
}
c0[i-1]+=d;
int l1=1,r1=i-1,l2=1,r2=i-1;
for(auto j:q[i]){
if(j.se==1){
r1=min(r1,j.fi-1);
}
else if(j.se==2){
f1=0;
l2=max(l2,j.fi);
r1=min(r1,j.fi-1);
}
else{
f1=f2=0;
l1=max(l1,j.fi);
}
}
if(!f2){
for(int j=1;j<=i-1;j++)c0[j]=0;
}
else{
for(int j=r1+1;j<=i-1;j++)c0[j]=0;
}
if(f1)d0=1;
if(l1>r1||l2>r2)l1=i,r1=i-1;
for(int j=1;j<l1;j++){
for(int k=pl[j];k<=pr[j];j++)del(j,k);
pl[j]=1,pr[j]=0;
}
for(int j=l1;j<=r1;j++){
if(max(pl[j],l2)>min(pr[j],r2)){
for(int k=pl[j];k<=pr[j];j++)del(j,k);
pl[j]=1,pr[j]=0;
}
else{
while(pl[j]<l2)del(j,pl[j]),pl[j]++;
while(pr[j]>r2)del(j,pr[j]),pr[j]--;
}
}
for(int j=r1+1;j<=i-1;j++){
for(int k=pl[j];k<=pr[j];k++)del(j,k);
pl[j]=1,pr[j]=0;
}
for(int j=1;j<=i-1;j++)a[j]=a0[j],b[j]=b0[j],c[j]=c0[j];
d=d0;
}
int res=d*3;
for(int i=1;i<n;i++)res=(res+1ll*a[i]*6)%mod;
for(int i=1;i<n;i++)res=(res+1ll*c[i]*6)%mod;
cout<<(res+mod)%mod<<"\n";
}
int main(){
//freopen("data.in","r",stdin);
// freopen("own.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
sol();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
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: 3780kb
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:
0 0 12150 0 16254 0 0 18 1080 0 6 0 594 18 54 216 162 0 1572 1458 0 54 12 66 0 0 90 0 162 0 0 18 0 54 6 0 0 0 0 0 0 108 36450 1182 2916 999999791 0 90 0 0 0 0 0 6 0 324 8748 999999761 0 1458 0 0 0 4842 6 18 0 0 0 18 54 0 0 0 0 0 0 450 0 0 4374 54 450 162 324 6 0 0 0 0 18 54 0 0 0 0 12 0 0 0 0 0 0 0 ...
result:
wrong answer 1st words differ - expected: '90', found: '0'