QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #5889 | #560. 隧道 | Qingyu | 100 ✓ | 189ms | 32936kb | C++17 | 3.2kb | 2021-01-27 14:25:29 | 2021-12-19 07:07:02 |
Judging History
answer
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 120, md = 1000000007;
inline int pow(int a, int b) {
int ans = 1;
for (; b; b>>=1) {
if (b & 1) {
ans = (ll)ans * a % md;
}
a = (ll)a * a % md;
}
return ans;
}
int n, m, inv = pow(10000, md - 2);
int vt, l[N][N], u[N][N], _l[N][N], _u[N][N];
int t1[3628805], t2[3628805], t3[120000], t4[120000], t[3628805];
int *f = t1, *g = t2, *lf = t3, *lg = t4, lenf, leng;
int cid, p[N], occ[N], id[N];
inline int pack() {
int S = 0;
for (int i=1; i<=cid; ++i) {
occ[i] = 0;
}
for (int i=1; i<=m; ++i) {
p[i] = occ[id[i]], occ[id[i]] = i;
}
for (int i=m; i; --i) {
S *= i, S += p[i];
}
return S;
}
inline void unpack(int S) {
cid = 0;
for (int i=1; i<=m; ++i) {
p[i] = S % i, S /= i;
if (p[i]) {
id[i] = id[p[i]];
} else {
id[i] = ++cid;
}
}
}
inline void add(int S, int poss) {
if (t[S] == vt) {
g[S] = (g[S] + poss) % md;
} else {
g[S] = poss, lg[++leng] = S, t[S] = vt;
}
}
int run() {
int S, poss, idj, ans = 0;
lenf = 1; f[0] = 1; lf[1] = 0;
for (int i=1; i<=n; ++i) {
for (int j=2; j<=m; ++j) {
++vt, leng = 0;
for (int t=1; t<=lenf; ++t) {
unpack(S = lf[t]);
if (id[1] == id[m]) {
ans = (ans + f[S]) % md;
continue;
}
idj = id[j];
// u
poss = (ll)f[S] * u[i][j] * (100 - l[i][j]) % md * inv % md;
if (poss) add(S, poss);
// l
poss = (ll)f[S] * (100 - u[i][j]) * l[i][j] % md * inv % md;
if (poss) {
id[j] = id[j - 1];
add(pack(), poss);
}
// neither
poss = (ll)f[S] * (100 - u[i][j]) * (100 - l[i][j]) % md * inv % md;
if (poss) {
id[j] = ++cid;
add(pack(), poss);
--cid;
}
// both
poss = (ll)f[S] * u[i][j] * l[i][j] % md * inv % md;
if (poss) {
id[j] = id[j - 1];
for (int k=1; k<=m; ++k)
if (id[k] == idj)
id[k] = id[j - 1];
add(pack(), poss);
}
}
swap(f, g), swap(lf, lg), swap(lenf, leng);
}
}
for (int t=1; t<=lenf; ++t) {
unpack(S = lf[t]);
if (id[1] == id[m]) {
ans = (ans + f[S]) % md;
continue;
}
}
return ans;
}
void conv() {
int _m = n + 1, _n = m - 1;
for (int i=1; i<=_n; ++i) {
for (int j=2; j<=_m; ++j) {
_l[i][j] = 100 - l[j - 1][i + 1];
}
}
for (int i=2; i<=_n; ++i) {
_u[i][1] = _u[i][_m] = 100;
for (int j=2; j<_m; ++j) {
_u[i][j] = 100 - u[j][i];
}
}
n = _n, m = _m;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
l[i][j] = _l[i][j],
u[i][j] = _u[i][j];
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
for (int j=2; j<=m; ++j) {
scanf("%d", &l[i][j]);
l[i][j] = 100 - l[i][j];
}
}
for (int i=2; i<=n; ++i) {
u[i][1] = u[i][m] = 100;
for (int j=2; j<m; ++j) {
scanf("%d", &u[i][j]);
u[i][j] = 100 - u[i][j];
}
}
bool rev = 0;
if (m > n) {
conv();
rev = 1;
}
int ans = run();
if (rev) {
printf("%d\n", (1 - ans + md) % md);
} else {
printf("%d\n", ans);
}
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 9840kb
input:
4 3 79 70 69 17 89 7 2 56 30 86 2
output:
491814732
result:
ok Good Job
Test #2:
score: 10
Accepted
time: 3ms
memory: 9748kb
input:
3 4 77 35 78 84 86 81 25 45 54 38 73 18 88
output:
549348278
result:
ok Good Job
Test #3:
score: 10
Accepted
time: 1ms
memory: 7692kb
input:
4 4 54 69 55 68 71 62 49 88 7 74 46 34 75 44 28 58 68 33
output:
831695263
result:
ok Good Job
Test #4:
score: 10
Accepted
time: 11ms
memory: 10036kb
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:
746595068
result:
ok Good Job
Test #5:
score: 10
Accepted
time: 50ms
memory: 12336kb
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 99 36 34 7 79 60 92 73 45 36 77 32 24 98 36 41 40 58 41 25 1 67 82 66 67 98 50 49 67 55 74 84 40 38 93 90 63 85 36 59 42 71 69 73 83 69 79 66 97 30 24 11 73 10 19 24 94 87 12 62 37 42 60 79 37 20 90 88...
output:
141256967
result:
ok Good Job
Test #6:
score: 10
Accepted
time: 184ms
memory: 32816kb
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 99 36 34 7 79 60 92 73 45 36 77 32 24 98 36 41 40 58 41 25 1 67 82 66 67 98 50 49 67 55 74 84 40 38 93 90 63 85 36 59 42 71 69 73 83 69 79 66 97 30 24 11 73 10 19 24 94 87 12 62 37 42
output:
829679200
result:
ok Good Job
Test #7:
score: 10
Accepted
time: 52ms
memory: 14368kb
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 66 12 58 19 84 46 88 71 53 63 46 95 70 80 79 15 81 49 1 33 64 32 34 96 98 96 33 9 47 67 79 75 86 80 26 70 70 17 82 41 37 46 65 38 58 31 93 59 47 20 46 18 36 46 88 73
output:
791997773
result:
ok Good Job
Test #8:
score: 10
Accepted
time: 189ms
memory: 32728kb
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 76 80 50 71 48 37 37 82 12 73 87 28 81 94 58 67 61 57 1 88 25 87 23 96 48 13 88 59 71 28 91 22 51 44 79 31 48 37 62 64 60 69 92 94 18 53 92 2 54 56 70 21 74 20 86 68 58 11 18 30
output:
768441589
result:
ok Good Job
Test #9:
score: 10
Accepted
time: 182ms
memory: 32416kb
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 30 61 87 49 43 25 12 28 84 94 70 84 28 60 93 8 38 20 42 64 1 43 85 42 12 95 97 29 44 11 95 88 5 67 15 7 34 92 27 56 43 87 82 93 20 50 76 74 90 45 62 92 93 24 14 93 83 63 95 97 63 77
output:
165778886
result:
ok Good Job
Test #10:
score: 10
Accepted
time: 183ms
memory: 32936kb
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 98 18 36 77 75 19 33 6 29 94 69 92 5 21 18 72 22 72 1 98 46 97 1 94 47 44 99 62 21 50 18 13 79 70 87 54 5 75 23 11 5 18 47 7 36 95 89 87 69 29 18 27 53 68 81 59 32 84 8 24
output:
68964096
result:
ok Good Job