QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#704554 | #560. 隧道 | TheZone | 100 ✓ | 383ms | 6036kb | C++20 | 3.7kb | 2024-11-02 20:12:15 | 2024-11-02 20:12:15 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=115,M=1000000,P=1000000007;
int n,m,o,i,j,k,_id[N][N],_wr[N][N],_wd[N][N],id[N][N],wr[N][N],wd[N][N];
struct E{
ll x;int y,v;
E(){}
E(ll _x,int _y,int _v){x=_x,y=_y,v=_v;}
}e[2][M];
int cnt[2];
inline bool cmp(const E&a,const E&b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
inline int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}
inline int read(){
int x;
scanf("%d",&x);
return 1LL*x*po(100,P-2)%P;
}
inline int read2(){
int x=read();
x=(P+1-x)%P;
return x;
}
inline void fix(){
int m=cnt[o],t=0,i,j,k;
sort(e[o],e[o]+m,cmp);
for(i=0;i<m;i=j){
for(k=0,j=i;j<m&&e[o][i].x==e[o][j].x&&e[o][i].y==e[o][j].y;j++)up(k,e[o][j].v);
if(k)e[o^1][t++]=E(e[o][i].x,e[o][i].y,k);
}
cnt[o^=1]=t;
}
inline ll get(ll x,int y){return x>>(y<<2)&15;}
inline void cal(ll&A,int&B){
static int v[N],f[N];
int i,x,t=0,C=0;
for(i=0;i<=m;i++)v[i]=-1;
for(t=i=0;i<m;i++){
x=get(A,i);
if(v[x]==-1){
C|=(B>>(x<<1)&3)<<(t<<1);
v[x]=t++;
}
f[i]=v[x];
}
for(A=0,B=C,i=m-1;~i;i--)A=A<<4|f[i];
}
inline void up0(ll A,int B,int C,int x,int y){
A^=(get(A,x)^m)<<(x<<2);
B|=y<<(m<<1);
cal(A,B);
e[o^1][cnt[o^1]++]=E(A,B,C);
}
inline void upl(ll A,int B,int C,int x,int y){
int t=get(A,x-1);
if(y+(B>>(t<<1)&3)==3)return;
A^=(get(A,x)^t)<<(x<<2);
B|=y<<(t<<1);
cal(A,B);
e[o^1][cnt[o^1]++]=E(A,B,C);
}
inline void upu(ll A,int B,int C,int x,int y){
int t=get(A,x);
if(y+(B>>(t<<1)&3)==3)return;
B|=y<<(t<<1);
e[o^1][cnt[o^1]++]=E(A,B,C);
}
inline void upul(ll A,int B,int C,int x,int y){
int t=get(A,x),z=get(A,x-1);
if(y+(B>>(t<<1)&3)==3)return;
B|=y<<(t<<1);
if((B>>(z<<1)&3)+(B>>(t<<1)&3)==3)return;
B|=(B>>(z<<1)&3)<<(t<<1);
ll S=z^t;
for(int i=0;i<m;i++)if(get(A,i)==z)A^=S<<(i<<2);
cal(A,B);
e[o^1][cnt[o^1]++]=E(A,B,C);
}
int solve(){
if(n<m){
for(i=1;i<=n;i++)for(j=1;j<m;j++)wd[j][i]=_wr[i][j];
for(i=1;i<n;i++)for(j=1;j<=m;j++)wr[j][i]=_wd[i][j];
for(i=1;i<=n;i++)for(j=1;j<=m;j++)id[j][i]=_id[i][j];
swap(n,m);
}else{
for(i=1;i<=n;i++)for(j=1;j<=m;j++)wd[i][j]=_wd[i][j],wr[i][j]=_wr[i][j],id[i][j]=_id[i][j];
}
cnt[o=0]=1;
e[0][0]=E(0,0,1);
for(i=m-1;~i;i--)e[0][0].x=e[0][0].x<<4|i;
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
int pl=j>1?wr[i][j-1]:0,npl=(P+1-pl)%P,
pu=i>1?wd[i-1][j]:0,npu=(P+1-pu)%P,
pul=1LL*pl*pu%P,p0=1LL*npl*npu%P,t=id[i][j];
pl=1LL*pl*npu%P;
pu=1LL*pu*npl%P;
cnt[o^1]=0;
for(k=0;k<cnt[o];k++){
if(pl)upl(e[o][k].x,e[o][k].y,1LL*e[o][k].v*pl%P,j-1,t);
if(pu)upu(e[o][k].x,e[o][k].y,1LL*e[o][k].v*pu%P,j-1,t);
if(pul)upul(e[o][k].x,e[o][k].y,1LL*e[o][k].v*pul%P,j-1,t);
if(p0)up0(e[o][k].x,e[o][k].y,1LL*e[o][k].v*p0%P,j-1,t);
}
o^=1;
fix();
}
int ret=0;
for(i=0;i<cnt[o];i++)up(ret,e[o][i].v);
return ret;
}
int main(){
int r,c,flag=0;
scanf("%d%d",&r,&c);
if(c<=1)return puts("1"),0;
if(min(r,c)<min(r+1,c-1)){
flag=1;
for(i=1;i<=r;i++)for(j=1;j<c;j++)_wr[i][j]=read();
for(i=1;i<r;i++)for(j=2;j<c;j++)_wd[i][j]=read();
for(i=1;i<r;i++)_wd[i][1]=_wd[i][c]=1;
for(i=1;i<=r;i++)_id[i][1]=1,_id[i][c]=2;
n=r,m=c;
}else{
for(i=1;i<=r;i++)for(j=1;j<c;j++)_wd[i][j]=read2();
for(i=1;i<r;i++)for(j=2;j<c;j++)_wr[i+1][j-1]=read2();
for(i=1;i<c-1;i++)_wr[1][i]=_wr[r+1][i]=1;
for(i=1;i<c;i++)_id[1][i]=1,_id[r+1][i]=2;
n=r+1,m=c-1;
}
int ans=solve();
if(flag)ans=(P+1-ans)%P;
return printf("%d",ans),0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 5728kb
input:
4 3 79 70 69 17 89 7 2 56 30 86 2
output:
975471183
result:
ok Good Job
Test #2:
score: 10
Accepted
time: 0ms
memory: 3668kb
input:
3 4 77 35 78 84 86 81 25 45 54 38 73 18 88
output:
788006418
result:
ok Good Job
Test #3:
score: 10
Accepted
time: 0ms
memory: 3676kb
input:
4 4 54 69 55 68 71 62 49 88 7 74 46 34 75 44 28 58 68 33
output:
497731994
result:
ok Good Job
Test #4:
score: 10
Accepted
time: 17ms
memory: 5708kb
input:
8 8 31 4 32 51 57 43 73 32 59 11 18 51 62 16 91 87 2 49 93 13 18 20 36 68 11 27 37 81 15 65 56 14 34 67 50 28 57 56 53 72 22 32 92 35 96 88 78 20 55 57 50 78 58 67 66 70 18 5 44 49 2 57 81 25 95 21 55 91 89 40 39 93 76 47 45 75 5 37 14 68 71 67 82 11 59 87 17 86 35 62 82 43 24 66 27 68 12 35
output:
567454986
result:
ok Good Job
Test #5:
score: 10
Accepted
time: 118ms
memory: 3836kb
input:
8 13 31 4 32 51 57 43 73 32 59 11 18 51 62 16 91 87 2 49 93 13 18 20 36 68 11 27 37 81 15 65 56 14 34 67 50 28 57 56 53 72 22 32 92 35 96 88 78 20 55 57 50 78 58 67 66 70 18 5 44 49 2 57 81 25 95 21 55 91 89 40 39 93 76 47 45 75 5 37 14 68 71 67 82 11 59 87 17 86 35 62 82 43 24 66 27 68 12 35 7 45 9...
output:
291352153
result:
ok Good Job
Test #6:
score: 10
Accepted
time: 374ms
memory: 5988kb
input:
10 10 31 4 32 51 57 43 73 32 59 11 18 51 62 16 91 87 2 49 93 13 18 20 36 68 11 27 37 81 15 65 56 14 34 67 50 28 57 56 53 72 22 32 92 35 96 88 78 20 55 57 50 78 58 67 66 70 18 5 44 49 2 57 81 25 95 21 55 91 89 40 39 93 76 47 45 75 5 37 14 68 71 67 82 11 59 87 17 86 35 62 82 43 24 66 27 68 12 35 7 45 ...
output:
435397171
result:
ok Good Job
Test #7:
score: 10
Accepted
time: 106ms
memory: 5796kb
input:
11 9 61 7 63 2 13 84 46 63 18 20 35 1 24 31 82 73 3 97 86 25 35 39 70 35 20 52 73 61 29 30 11 27 66 34 99 54 13 12 5 44 42 62 84 69 91 76 55 38 9 14 99 56 15 33 32 40 35 8 86 97 2 13 61 48 89 41 9 82 77 79 76 86 51 92 88 50 8 73 27 36 42 34 64 21 17 73 33 72 68 23 63 84 47 31 52 35 23 68 12 89 97 71...
output:
119328160
result:
ok Good Job
Test #8:
score: 10
Accepted
time: 383ms
memory: 6008kb
input:
9 11 38 41 40 84 98 65 70 8 71 56 8 18 11 3 46 3 37 14 84 62 41 13 15 90 24 94 52 87 1 19 62 64 44 89 16 62 31 30 22 2 16 72 48 14 56 6 47 77 60 98 16 48 67 88 87 62 73 42 34 47 35 65 88 55 87 14 27 46 73 59 89 84 76 8 4 8 75 19 31 91 65 23 91 25 36 68 38 34 13 10 57 64 88 20 93 25 93 47 14 71 64 16...
output:
523005857
result:
ok Good Job
Test #9:
score: 10
Accepted
time: 377ms
memory: 5956kb
input:
10 10 15 74 17 68 83 46 94 51 24 92 79 34 97 74 10 31 70 30 81 99 46 85 60 46 27 36 31 14 71 7 14 2 21 45 33 71 49 48 39 59 89 82 13 58 21 35 39 17 11 84 32 41 20 43 43 85 13 76 81 96 68 17 15 63 85 87 44 10 69 39 2 81 1 23 18 66 43 64 35 47 88 11 19 28 56 63 44 96 57 96 51 45 30 8 36 14 63 25 15 52...
output:
855223857
result:
ok Good Job
Test #10:
score: 10
Accepted
time: 374ms
memory: 6036kb
input:
10 10 91 9 94 51 69 27 19 94 76 29 52 51 84 46 73 60 4 46 79 37 52 58 5 2 30 78 10 41 43 94 65 40 98 1 49 80 68 67 56 16 62 92 76 4 86 64 32 57 62 70 49 33 71 98 97 9 51 11 29 46 2 69 42 71 83 60 62 73 65 19 15 79 26 38 33 24 11 10 40 4 12 99 46 31 75 59 49 58 2 84 44 26 70 96 77 3 34 3 17 34 96 6 9...
output:
375965290
result:
ok Good Job