QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693254 | #1286. Ternary String Counting | cwfxlh | ML | 85ms | 161624kb | C++14 | 1.8kb | 2024-10-31 15:48:56 | 2024-10-31 15:49:27 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
int sakuzyo,n,m,mnlmt[5003][4],mxlmt[5003][4],k1,k2,k3,k4,k5,k6,k7,k8,k9;
ll ans,vv[5003];
struct dpv{
int nxth;
int nxtw;
ll val;
}dp[5003][5003];
ll sumh[5003],sumw[5003];
int headh[5003],headw[5003];
void setval(int X,int Y,ll v){
dp[X][Y].val=v;
sumh[X]=(sumh[X]+v)%MOD;
sumw[Y]=(sumw[Y]+v)%MOD;
dp[X][Y].nxth=headh[X];
dp[X][Y].nxtw=headw[Y];
headh[X]=Y;
headw[Y]=X;
return;
}
void clnh(int X){
for(int i=headh[X];i!=-1;i=dp[X][i].nxth){
sumw[i]=(sumw[i]-dp[X][i].val)%MOD;
dp[X][i].val=0;
}
headh[X]=-1;
sumh[X]=0;
return;
}
void clnw(int X){
for(int i=headw[X];i!=-1;i=dp[i][X].nxtw){
sumh[i]=(sumh[i]-dp[i][X].val)%MOD;
dp[i][X].val=0;
}
headw[X]=-1;
sumw[X]=0;
return;
}
void getlmt(int X){
for(int i=X-1;i>=mnlmt[X][1];i--)clnh(i);
for(int i=0;i<mxlmt[X][2];i++)clnh(i);
for(int i=X-1;i>=mnlmt[X][2];i--)clnw(i);
for(int i=0;i<mxlmt[X][3];i++)clnw(i);
return;
}
void sol(){
cin>>n>>m;
for(int i=0;i<=n+1;i++){
for(int j=0;j<4;j++){
mnlmt[i][j]=n+1;
mxlmt[i][j]=0;
}
}
for(int i=1;i<=m;i++){
cin>>k1>>k2>>k3;
mnlmt[k2][k3]=min(mnlmt[k2][k3],k1);
mxlmt[k2][k3]=max(mxlmt[k2][k3],k1);
}
for(int i=0;i<=n;i++){
sumh[i]=sumw[i]=0;
headh[i]=headw[i]=-1;
for(int j=0;j<=n;j++){
dp[i][j].nxth=dp[i][j].nxtw=-1;
dp[i][j].val=0;
}
}
setval(0,0,3);
getlmt(1);
for(int i=2;i<=n;i++){
for(int j=0;j<i-1;j++)vv[j]=(sumh[j]+sumw[j])%MOD;
for(int j=0;j<i-1;j++)setval(i-1,j,vv[j]);
getlmt(i);
}
ans=0;
for(int i=0;i<=n;i++)ans=(ans+sumh[i])%MOD;
ans%=MOD;
ans+=MOD;
ans%=MOD;
cout<<ans<<'\n';
return;
}
signed main(){
ios::sync_with_stdio(false);
cin>>sakuzyo;
while(sakuzyo--)sol();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
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: 2ms
memory: 3708kb
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: 0ms
memory: 3692kb
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: 34ms
memory: 81932kb
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: 37ms
memory: 81812kb
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: 67ms
memory: 160072kb
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: 85ms
memory: 161624kb
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: -100
Memory Limit Exceeded
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