QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#704554#560. 隧道TheZone100 ✓383ms6036kbC++203.7kb2024-11-02 20:12:152024-11-02 20:12:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 20:12:15]
  • 评测
  • 测评结果:100
  • 用时:383ms
  • 内存:6036kb
  • [2024-11-02 20:12:15]
  • 提交

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