QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563747#8947. 白兔迷宫wsyear4 53ms4168kbC++145.5kb2024-09-14 15:39:442024-09-14 15:39:45

Judging History

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

  • [2024-09-14 15:39:45]
  • 评测
  • 测评结果:4
  • 用时:53ms
  • 内存:4168kb
  • [2024-09-14 15:39:44]
  • 提交

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%