QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#760172 | #1286. Ternary String Counting | music0908 | WA | 310ms | 200228kb | C++14 | 2.6kb | 2024-11-18 15:23:04 | 2024-11-18 15:23:06 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e3+5;
const int Mod=1e9+7;
int T;
int n,m;
int rem;
int l[MAXN],r[MAXN];
int cnt[MAXN],sum[MAXN];
int minj[MAXN],maxj[MAXN],mink[MAXN],maxk[MAXN];
int dp[MAXN][MAXN];
int t[MAXN];
struct Node{
int min;
int max;
}a[MAXN],b[MAXN];
struct Q{
int l;
int r;
int x;
}q[MAXN];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%Mod;
}
a=a*a%Mod;
b>>=1;
}
return res;
}
void Clear(int x){
for(int i=rem;i<=x-1;i++){
if(i>=a[x].min&&i<=a[x].max){
for(int j=l[i];j<b[x].min;j++){
(((cnt[i]-=dp[i][j])%=Mod)+=Mod)%=Mod;
(((sum[j]-=dp[i][j])%=Mod)+=Mod)%=Mod;
dp[i][j]=0;
}
for(int j=r[i];j>b[x].max;j--){
(((cnt[i]-=dp[i][j])%=Mod)+=Mod)%=Mod;
(((sum[j]-=dp[i][j])%=Mod)+=Mod)%=Mod;
dp[i][j]=0;
}
l[i]=max(l[i],b[x].min);
r[i]=min(r[i],b[x].max);
continue;
}
l[i]=n;
r[i]=0;
for(int j=0;j<=n;j++){
(((cnt[i]-=dp[i][j])%=Mod)+=Mod)%=Mod;
(((sum[j]-=dp[i][j])%=Mod)+=Mod)%=Mod;
dp[i][j]=0;
}
}
rem=max(rem,a[x].min);
return ;
}
void init(){
for(int i=0;i<=n;i++){
cnt[i]=0;
sum[i]=0;
a[i]=(Node){0,n};
b[i]=(Node){0,n};
l[i]=0;
r[i]=n;
q[i]=(Q){0,0,0};
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]=0;
}
}
dp[0][0]=1;
return ;
}
signed main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
scanf("%lld",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
if(n==0){
printf("%lld\n",0);
continue;
}
if(m==0){
printf("%lld\n",qpow(3,n));
continue;
}
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
q[i]=(Q){u,v,w};
}
for(int i=1;i<=m;i++){
switch(q[i].x){
case 3:{
a[q[i].r].min=max(a[q[i].r].min,q[i].l+1);
b[q[i].r].min=max(b[q[i].r].min,q[i].l);
break;
}
case 2:{
a[q[i].r].min=max(a[q[i].r].min,q[i].l);
b[q[i].r].max=min(b[q[i].r].max,q[i].l-1);
break;
}
default:{
a[q[i].r].max=min(a[q[i].r].max,q[i].l-1);
break;
}
}
}
rem=0;
cnt[0]=sum[0]=1;
for(int i=1;i<=n;i++){
for(int k=0;k<i;k++){
t[k]=(cnt[k]+sum[k])%Mod;
}
if(a[i].min<=i-1&&a[i].max>=i-1){
for(int k=b[i].min;k<=min(b[i].max,max(0ll,i-2));k++){
(dp[i-1][k]+=t[k])%Mod;
(sum[k]+=t[k])%=Mod;
(cnt[i-1]+=t[k])%Mod;
}
}
Clear(i);
}
int ans=0;
for(int i=0;i<=n;i++){
(ans+=cnt[i])%=Mod;
}
printf("%d\n",ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3756kb
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: 0ms
memory: 5952kb
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: 2ms
memory: 5840kb
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: 56ms
memory: 43032kb
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: 58ms
memory: 45020kb
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: 66ms
memory: 82084kb
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: 81ms
memory: 82632kb
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: 310ms
memory: 199856kb
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: 301ms
memory: 200228kb
input:
1 5000 2 539 4252 1 906 3821 1
output:
101862333
result:
ok "101862333"
Test #10:
score: 0
Accepted
time: 1ms
memory: 10080kb
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: 0ms
memory: 24344kb
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: 3ms
memory: 199740kb
input:
1 5000 0
output:
22443616
result:
ok "22443616"
Test #13:
score: -100
Wrong Answer
time: 138ms
memory: 199860kb
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...
output:
980901228
result:
wrong answer 1st words differ - expected: '905890933', found: '980901228'