QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108127 | #1286. Ternary String Counting | youngsystem | TL | 438ms | 83172kb | C++20 | 2.7kb | 2023-05-23 17:18:46 | 2023-05-23 17:18:48 |
Judging History
answer
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int l1[5005],r1[5005];
int l2[5005],r2[5005];
int nl[5005],nr[5005];
int dp[5005][5005];
int heh[5005],hel[5005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t,n,m;
int l,r,x;
cin>>t;
for(int greg=1;greg<=t;greg++)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
l1[i]=0;
r1[i]=i-1;
l2[i]=0;
r2[i]=i-1;
}
for(int i=1;i<=n;i++)
{
nl[i]=1;
nr[i]=0;
heh[i]=0;
hel[i]=0;
}
for(int i=1;i<=m;i++)
{
cin>>l>>r>>x;
if(x==3)
{
l1[r]=max(l1[r],l);
}
else if(x==2)
{
r1[r]=min(r1[r],(l-1));
l2[r]=max(l2[r],l);
}
else if(x==1)
{
r2[r]=min(r2[r],(l-1));
}
}
//for(int i=1;i<=n;i++)printf("%d %d %d %d\n",l1[i],r1[i],l2[i],r2[i]);
heh[1]=3;
hel[1]=3;
dp[1][1]=3;
nl[1]=1;
nr[1]=1;
if(l1[1]>0||l2[1]>0)
{
cout<<"0\n";
continue;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=i-2;j++)
{
dp[j+1][i]=(heh[j+1]+hel[j+1]>=mod)?heh[j+1]+hel[j+1]-mod:heh[j+1]+hel[j+1];
}
nl[i]=1;
nr[i]=i-1;
for(int j=0;j<=i-2;j++)
{
heh[j+1]=(heh[j+1]+dp[j+1][i]>=mod)?heh[j+1]+dp[j+1][i]-mod:heh[j+1]+dp[j+1][i];
hel[i]=(hel[i]+dp[j+1][i]>=mod)?hel[i]+dp[j+1][i]-mod:hel[i]+dp[j+1][i];
}
for(int j=1;j<=i;j++)
{
if(j-1<l2[i]||j-1>r2[i])
{
for(int sth=nl[j];sth<=nr[j];sth++)
{
//printf("del:%d %d\n",sth,j);
heh[sth]=(heh[sth]-dp[sth][j]>=0)?heh[sth]-dp[sth][j]:heh[sth]+mod-dp[sth][j];
hel[j]=(hel[j]-dp[sth][j]>=0)?hel[j]-dp[sth][j]:hel[j]+mod-dp[sth][j];
dp[sth][j]=0;
}
nl[j]=1;
nr[j]=0;
}
else
{
for(int sth=nl[j];sth<l1[i]+1;sth++)
{
//printf("del:%d %d\n",sth,j);
heh[sth]=(heh[sth]-dp[sth][j]>=0)?heh[sth]-dp[sth][j]:heh[sth]+mod-dp[sth][j];
hel[j]=(hel[j]-dp[sth][j]>=0)?hel[j]-dp[sth][j]:hel[j]+mod-dp[sth][j];
dp[sth][j]=0;
}
nl[j]=max(nl[j],l1[i]+1);
for(int sth=r1[i]+2;sth<=nr[j];sth++)
{
//printf("del:%d %d\n",sth,j);
heh[sth]=(heh[sth]-dp[sth][j]>=0)?heh[sth]-dp[sth][j]:heh[sth]+mod-dp[sth][j];
hel[j]=(hel[j]-dp[sth][j]>=0)?hel[j]-dp[sth][j]:hel[j]+mod-dp[sth][j];
dp[sth][j]=0;
}
nr[j]=min(nr[j],r1[i]+1);
}
}
/*printf("orz%d\n",i);
for(int j=1;j<=i;j++)
{
for(int k=1;k<=i;k++)printf("%d ",dp[j][k]);
printf("\n");
}*/
//for(int j=1;j<=i;j++)printf("%d %d\n",nl[j],nr[j]);
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=nl[i];j<=nr[i];j++)
{
ans=(ans+dp[j][i]>=mod)?ans+dp[j][i]-mod:ans+dp[j][i];
}
}
cout<<ans<<"\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3452kb
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: 0
Accepted
time: 3ms
memory: 3536kb
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 0 0 0 24300 0 0 0 768 0 0 972 2916 0 6480 864 0 0 0 0 0 0 0 0 6 0 0 0 0 0 96 0 6 0 0 0 0 0 0 0 108 0 0 0 2916 0 0 0 0 0 0 0 0 0 0 324 8748 0 0 0 0 0 0 4320 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 1992 0 0 450 0 162 1656 0 0 0 0 0 54 0 18 0 0 0 0 744 0 1620 324 0 0 36 36 0 0 60 6 54 0 0 0 0 0 0 0 0 243 810...
result:
ok 741 tokens
Test #3:
score: 0
Accepted
time: 3ms
memory: 3580kb
input:
332 17 5 4 9 1 4 6 1 7 17 1 5 5 1 5 6 3 13 5 10 12 3 8 13 2 1 10 3 2 9 1 9 10 1 19 5 11 13 1 9 17 2 1 7 1 4 4 2 3 9 1 15 4 8 11 2 9 14 3 10 12 2 4 5 2 12 4 3 9 2 7 8 1 1 7 3 6 7 3 16 5 4 14 3 1 5 1 2 10 1 2 12 3 6 9 3 20 4 10 17 3 4 20 3 17 19 3 8 17 1 20 5 11 11 1 9 13 1 1 5 3 17 17 3 3 18 3 17 5 1...
output:
0 0 0 2047032 0 0 0 0 0 839808 0 0 0 0 0 0 0 0 0 0 0 0 44641044 0 20412 0 0 0 0 0 0 0 6 0 0 0 0 81 0 0 0 0 0 0 0 0 0 0 0 313155072 0 0 0 0 0 0 0 0 0 5400 0 10368 0 0 0 0 14580 0 0 0 217728 40310784 0 0 218700 0 0 0 0 1620 0 0 0 0 0 108 146304 0 0 0 466560 288 0 0 0 0 0 0 0 276138 0 0 0 0 0 0 0 52488...
result:
ok 332 tokens
Test #4:
score: 0
Accepted
time: 23ms
memory: 14816kb
input:
5 1000 0 1000 5 779 779 2 543 840 3 30 477 1 10 295 3 463 741 1 1000 6 379 569 1 249 826 2 194 819 3 90 400 1 614 808 2 102 868 2 1000 8 463 981 1 680 857 3 560 623 1 209 659 1 55 957 2 244 327 1 321 888 3 37 204 3 1000 5 336 851 3 410 676 1 522 911 2 165 962 1 258 330 3
output:
56888193 0 0 0 0
result:
ok 5 tokens
Test #5:
score: 0
Accepted
time: 28ms
memory: 14024kb
input:
5 1000 9 190 765 1 212 745 3 437 798 3 682 814 3 122 289 1 44 821 1 115 448 3 400 936 2 562 639 3 1000 5 561 808 3 23 160 2 57 915 2 211 943 3 125 596 2 1000 1 398 739 2 1000 3 629 973 2 7 721 2 591 815 2 1000 10 536 708 1 217 256 2 690 913 3 418 871 2 302 325 2 334 830 2 496 573 2 396 865 1 240 837...
output:
0 0 722271060 85306976 0
result:
ok 5 tokens
Test #6:
score: 0
Accepted
time: 64ms
memory: 24752kb
input:
2 2000 1 1501 1703 2 2000 5 1230 1521 3 1022 1939 3 1241 1283 3 767 1944 2 303 1163 3
output:
841960641 0
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 72ms
memory: 26208kb
input:
2 2000 2 640 1942 1 1473 1917 3 2000 4 490 887 1 670 1163 3 824 1434 2 1221 1746 1
output:
0 0
result:
ok 2 tokens
Test #8:
score: 0
Accepted
time: 438ms
memory: 83172kb
input:
1 5000 9 2821 3377 2 798 1535 2 3563 4161 3 2205 2946 3 1320 1594 3 278 1624 1 1243 2759 3 2882 4939 1 2639 3559 3
output:
0
result:
ok "0"
Test #9:
score: 0
Accepted
time: 375ms
memory: 70412kb
input:
1 5000 2 539 4252 1 906 3821 1
output:
101862333
result:
ok "101862333"
Test #10:
score: 0
Accepted
time: 0ms
memory: 5780kb
input:
111 34 0 30 0 18 0 35 0 3 0 43 0 13 0 28 0 57 0 75 0 31 0 4 0 92 0 1 0 53 0 85 0 74 0 43 0 59 0 72 0 79 0 40 0 70 0 36 0 86 0 56 0 53 0 66 0 50 0 100 0 60 0 74 0 50 0 51 0 92 0 49 0 50 0 78 0 95 0 4 0 59 0 44 0 92 0 84 0 7 0 75 0 99 0 56 0 54 0 13 0 27 0 33 0 22 0 80 0 14 0 79 0 29 0 39 0 21 0 97 0 ...
output:
582926302 130653412 387420489 748778899 27 738321955 1594323 792294829 998064805 100094381 391960236 81 587240675 3 172815616 473062299 700031465 738321955 982583189 966670169 107644805 953271190 662963356 246336683 419186890 666021604 172815616 909419307 710104287 886041711 947749553 700031465 7101...
result:
ok 111 tokens
Test #11:
score: 0
Accepted
time: 4ms
memory: 9160kb
input:
16 350 0 453 0 485 0 361 0 498 0 149 0 433 0 435 0 279 0 240 0 166 0 152 0 393 0 159 0 219 0 222 0
output:
378029361 68761795 621961191 766744305 24977444 679213660 705815658 352340880 186665231 458529104 150230246 338768694 907169137 887128598 322586612 709838468
result:
ok 16 tokens
Test #12:
score: 0
Accepted
time: 366ms
memory: 70348kb
input:
1 5000 0
output:
22443616
result:
ok "22443616"
Test #13:
score: -100
Time Limit Exceeded
input:
1 5000 1000000 4736 4854 3 405 1465 3 835 4720 3 633 1954 3 2182 4257 3 1920 3098 3 302 3157 3 63 3964 3 4032 4116 3 734 1980 3 1083 4515 3 44 4768 3 20 4466 3 1160 2774 3 794 1531 3 2301 4714 3 255 4939 3 2699 2967 3 1835 2733 3 582 2071 3 430 1857 3 249 2013 3 922 4833 3 13 1973 3 3150 3812 3 2904...