QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563747 | #8947. 白兔迷宫 | wsyear | 4 | 53ms | 4168kb | C++14 | 5.5kb | 2024-09-14 15:39:44 | 2024-09-14 15:39:45 |
Judging History
answer
// Author: Klay Thompson
// Problem: C. 白兔迷宫
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
template <int P>
class mod_int {
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const {
Z res = 1, t = *this;
while (k) {
if (k & 1) res *= t;
if (k >>= 1) t *= t;
}
return res;
}
Z &operator++() {
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--() {
x ? --x : x = P - 1;
return *this;
}
Z operator++(int) {
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int) {
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs) {
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs) {
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z &operator*=(const Z &rhs) {
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) {\
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
};
const int P = 998244353;
using Z = mod_int<P>;
const int maxn = 310;
int n, m, s, t, deg[maxn];
Z a[maxn][maxn], noz[maxn], dp[maxn], dp2[maxn];
vector<int> e0[maxn], e1[maxn];
// dp: 走到终点的期望得分
// dp2: 走到终点且不再经过清空边的期望得分
// f: 走到终点的期望得分平方
// g: 走到终点且不再经过清空边的期望得分平方
// h: 走到终点且还会经过清空边的期望得分平方
void gauss(int n) {
rep (i, 1, n) {
int pos = i;
rep (j, i + 1, n) if (a[j][i].val()) pos = j;
if (i != pos) {
rep (j, 1, n + 1) swap(a[i][j], a[pos][j]);
}
rep (j, 1, n) if (i != j) {
Z coe = a[j][i] / a[i][i];
rep (k, 1, n + 1) a[j][k] -= coe * a[i][k];
}
}
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> n >> m >> s >> t;
rep (i, 1, m) {
int u, v, w;
cin >> u >> v >> w, deg[u]++;
if (w) e1[u].emplace_back(v);
else e0[u].emplace_back(v);
}
rep (i, 1, n) rep (j, 1, n + 1) a[i][j] = 0;
rep (i, 1, n) {
if (i != t) {
Z ideg = Z(deg[i]).inv();
a[i][i] = P - 1;
for (int j : e1[i]) a[i][j] += ideg;
} else {
a[i][i] = 1, a[i][n + 1] = 1;
}
}
gauss(n);
rep (i, 1, n) noz[i] = a[i][n + 1] / a[i][i];
rep (i, 1, n) rep (j, 1, n + 1) a[i][j] = 0;
rep (i, 1, n) {
if (i != t) {
Z ideg = Z(deg[i]).inv();
for (int j : e1[i]) a[i][j]++, a[i][n + 1] -= noz[j];
for (int j : e0[i]) a[i][j]++;
rep (j, 1, n + 1) a[i][j] *= ideg;
a[i][i] -= 1;
} else {
a[i][i] = 1;
}
}
gauss(n);
rep (i, 1, n) dp[i] = a[i][n + 1] / a[i][i];
rep (i, 1, n) rep (j, 1, n + 1) a[i][j] = 0;
rep (i, 1, n) {
if (i != t) {
Z ideg = Z(deg[i]).inv();
for (int j : e1[i]) a[i][j]++, a[i][n + 1]--;
rep (j, 1, n + 1) a[i][j] *= ideg;
a[i][i] -= 1;
} else {
a[i][i] = 1;
}
}
gauss(n);
rep (i, 1, n) dp2[i] = a[i][n + 1] / a[i][i];
rep (i, 1, 3 * n) rep (j, 1, 3 * n + 1) a[i][j] = 0;
rep (i, 1, n) {
if (i != t) {
for (int j : e1[i]) {
a[i][j + n] += noz[j], a[i][3 * n + 1] -= (2 * dp[j] + 1) * noz[j];
a[i][j + 2 * n] += 1 - noz[j];
}
for (int j : e0[i]) {
a[i][j] += 1;
}
Z ideg = Z(deg[i]).inv();
rep (j, 1, 3 * n + 1) a[i][j] *= ideg;
a[i][i] -= 1;
} else {
a[i][i] = 1;
}
}
rep (i, 1, n) {
if (i != t) {
for (int j : e1[i]) {
a[i + n][j + n] += 1, a[i + n][3 * n + 1] -= 2 * dp2[j] + 1;
}
Z ideg = Z(SZ(e1[i])).inv();
rep (j, 1, 3 * n + 1) a[i + n][j] *= ideg;
a[i + n][i + n] -= 1;
} else {
a[i + n][i + n] = 1;
}
}
rep (i, 1, n) {
if (i != t) {
for (int j : e1[i]) {
a[i + 2 * n][j + 2 * n] += 1;
}
for (int j : e0[i]) {
a[i + 2 * n][j] += 1;
}
Z ideg = Z(deg[i]).inv();
rep (j, 1, 3 * n + 1) a[i + 2 * n][j] *= ideg;
a[i + 2 * n][i + 2 * n] -= 1;
} else {
a[i + 2 * n][i + 2 * n] = 1;
}
}
gauss(3 * n);
Z f = a[1][3 * n + 1] / a[1][1];
Z ans = (n * f - dp[1] * dp[1]) / n / n;
cout << dp[1].val() << " " << ans.val() << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 4
Accepted
Test #1:
score: 4
Accepted
time: 41ms
memory: 4068kb
input:
91 90 83 8 51 8 0 74 51 0 64 74 0 12 64 0 90 12 0 80 90 0 14 80 0 53 14 0 26 53 0 88 26 0 35 88 0 28 35 0 15 28 0 37 15 0 54 37 0 72 54 0 22 72 0 43 22 0 20 43 0 24 20 0 73 24 0 65 73 0 87 65 0 17 87 0 82 17 0 58 82 0 61 58 0 25 61 0 46 25 0 79 46 0 23 79 0 40 23 0 4 40 0 75 4 0 19 75 0 50 19 0 16 5...
output:
0 0
result:
points 1.0
Test #2:
score: 4
Accepted
time: 37ms
memory: 4068kb
input:
90 7059 73 53 54 53 0 6 54 0 75 54 0 36 54 0 4 36 0 26 36 0 76 54 0 69 6 0 10 76 0 52 53 0 62 76 0 37 62 0 78 53 0 22 62 0 2 4 0 27 78 0 3 52 0 39 76 0 85 39 0 71 22 0 8 69 0 42 62 0 64 54 0 79 62 0 67 52 0 7 4 0 47 78 0 18 54 0 31 62 0 33 54 0 13 8 0 1 78 0 46 2 0 14 22 0 84 2 0 30 6 0 20 62 0 16 6...
output:
0 0
result:
points 1.0
Test #3:
score: 4
Accepted
time: 53ms
memory: 4168kb
input:
99 4727 84 99 33 99 0 5 33 0 65 99 0 51 33 0 4 33 0 89 65 0 62 89 0 68 33 0 84 4 0 59 4 0 35 59 0 53 35 0 15 68 0 10 62 0 27 15 0 80 5 0 50 65 0 63 99 0 49 89 0 57 80 0 1 50 0 56 10 0 8 89 0 31 68 0 85 80 0 39 50 0 72 15 0 55 4 0 76 57 0 96 76 0 66 62 0 13 63 0 3 76 0 11 4 0 20 80 0 79 11 0 61 63 0 ...
output:
0 0
result:
points 1.0
Test #4:
score: 4
Accepted
time: 45ms
memory: 4116kb
input:
98 9604 19 72 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 1 8 0 1 9 0 1 10 0 1 11 0 1 12 0 1 13 0 1 14 0 1 15 0 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 1 22 0 1 23 0 1 24 0 1 25 0 1 26 0 1 27 0 1 28 0 1 29 0 1 30 0 1 31 0 1 32 0 1 33 0 1 34 0 1 35 0 1 36 0 1 37 0 1 38 0 1 39 0 1 40 0 1 41 0 1 42 0 1...
output:
0 0
result:
points 1.0
Test #5:
score: 4
Accepted
time: 33ms
memory: 4136kb
input:
83 6889 26 34 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 1 8 0 1 9 0 1 10 0 1 11 0 1 12 0 1 13 0 1 14 0 1 15 0 1 16 0 1 17 0 1 18 0 1 19 0 1 20 0 1 21 0 1 22 0 1 23 0 1 24 0 1 25 0 1 26 0 1 27 0 1 28 0 1 29 0 1 30 0 1 31 0 1 32 0 1 33 0 1 34 0 1 35 0 1 36 0 1 37 0 1 38 0 1 39 0 1 40 0 1 41 0 1 42 0 1...
output:
0 0
result:
points 1.0
Test #6:
score: 4
Accepted
time: 49ms
memory: 4152kb
input:
97 3283 84 80 53 80 0 42 53 0 36 42 0 41 36 0 17 41 0 48 17 0 25 48 0 19 25 0 73 19 0 72 73 0 30 72 0 22 30 0 33 22 0 64 33 0 90 64 0 66 90 0 69 66 0 68 69 0 7 68 0 83 7 0 40 83 0 39 40 0 26 39 0 70 26 0 44 70 0 61 44 0 81 61 0 47 81 0 92 47 0 65 92 0 11 65 0 29 11 0 54 29 0 16 54 0 85 16 0 31 85 0 ...
output:
0 0
result:
points 1.0
Test #7:
score: 4
Accepted
time: 39ms
memory: 4140kb
input:
88 7044 78 88 70 88 0 51 88 0 63 88 0 18 70 0 28 51 0 47 70 0 53 47 0 66 18 0 10 51 0 48 66 0 73 47 0 87 73 0 49 63 0 16 28 0 76 51 0 17 73 0 81 70 0 12 28 0 43 73 0 8 70 0 31 88 0 69 53 0 20 81 0 30 12 0 65 70 0 80 31 0 59 81 0 29 31 0 78 76 0 6 80 0 25 63 0 40 49 0 26 70 0 2 17 0 50 48 0 56 17 0 5...
output:
0 0
result:
points 1.0
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 33ms
memory: 4068kb
input:
86 85 23 70 43 70 1 33 43 1 86 33 1 54 86 1 1 54 1 68 1 1 18 68 1 39 18 1 62 39 1 85 62 1 47 85 1 67 47 1 44 67 1 74 44 1 13 74 1 38 13 1 81 38 1 60 81 1 28 60 1 84 28 1 48 84 1 49 48 1 73 49 1 22 73 1 37 22 1 20 37 1 65 20 1 59 65 1 3 59 1 36 3 1 52 36 1 83 52 1 56 83 1 55 56 1 2 55 1 10 2 1 66 10 ...
output:
5 686056794
result:
points 0.0
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 40ms
memory: 4128kb
input:
90 89 77 72 38 72 1 9 38 1 20 9 1 39 20 1 61 39 1 55 61 1 46 55 1 28 46 1 56 28 1 74 56 1 35 74 1 64 35 1 27 64 1 69 27 1 79 69 1 88 79 1 31 88 1 48 31 1 57 48 1 7 57 1 85 7 1 6 85 1 63 6 1 32 63 1 34 32 1 4 34 1 67 4 1 50 67 1 11 50 1 13 11 1 71 13 1 2 71 1 45 2 1 26 45 1 43 26 1 73 43 1 44 73 1 33...
output:
87 850726104
result:
points 0.0
Subtask #4:
score: 0
Wrong Answer
Test #26:
score: 0
Wrong Answer
time: 31ms
memory: 4112kb
input:
81 6493 65 20 79 20 0 15 79 0 2 20 0 12 15 0 48 15 0 77 2 0 73 15 0 74 2 0 68 79 0 54 73 0 66 54 0 69 74 0 36 12 0 25 77 0 24 48 0 53 68 0 43 15 0 58 12 0 50 73 0 16 24 0 27 68 0 65 69 0 38 24 0 11 15 1 51 68 0 32 77 0 30 50 0 3 25 0 72 12 0 8 79 0 64 24 0 17 54 0 70 66 0 31 68 0 60 17 0 21 16 0 63 ...
output:
133922472 478891429
result:
points 0.0
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%