2023年中国大学生程序设计竞赛女生专场

A.

模拟。

B.

假设点在 $(a,b)$，做一条直线 $x=a$，然后查询 $(0,0)$ 到这个点的 $f(d_0)$，可以知道 $f(d)$ 在 $(x_0,0) \leq f(d_0), x0 \leq 2a$。

所以只需要二分出来第一个 $f(d) \geq f(d_0)$ 的位置即可。

对 $y=b$ 也做一次同样的操作。次数是 $2 \times \log$

C.

对于一个 $1$ 为根的有向树，只需要套用模板。邻接矩阵减掉度数矩阵删掉第一行第一列。

剩下都是消元的东西了，变成一个下三角。

然后可以分块矩阵，就是把一个行列式当成一个值，直接对角线乘法就可以了。

最后是三种矩阵相乘。

具体过程在这里。

https://codeforces.com/gym/104725/attachments/download/22701/solution.pdf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
const int P = 998244353;
vector<vector<int>> operator*(vector<vector<int>> a,
                              const vector<vector<int>> &b) {
  int N, M, K;
  N = (int)a.size();
  K = min((int)a[0].size(), (int)b.size());
  M = (int)b[0].size();
  vector<vector<int>> c(N, vector<int>(M, 0));
  rep(i, 0, N) {
    rep(k, 0, K) {
      rep(j, 0, M) {
        c[i][j] += (long long)a[i][k] * b[k][j] % P;
        if (c[i][j] >= P) {
          c[i][j] -= P;
        }
      }
    }
  }
  return c;
}
int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = (long long)res * x % P;
    }
    x = (long long)x * x % P;
    y /= 2;
  }
  return res;
}
int inverse(int x) { return power(x, P - 2); }
int val(vector<vector<int>> &a) {
  int N = (int)a.size();
  bool rev = false;
  int res = 1;
  rep(i, 0, N) {
    if (!a[i][i]) {
      rep(j, i + 1, N) {
        if (a[j][i]) {
          swap(a[i], a[j]);
          rev ^= 1;
          break;
        }
      }
    }
    rep(j, i + 1, N) {
      int d = (long long)a[j][i] * inverse(a[i][i]) % P;
      rep(k, i + 1, N) {
        a[j][k] -= (long long)d * a[i][k] % P;
        a[j][k] += a[j][k] >> 31 & P;
      }
      a[j][i] = 0;
    }
    if (!a[i][i]) {
      return 0;
    }
    res = (long long)res * a[i][i] % P;
  }
  if (rev) {
    return P - res;
  } else {
    return res;
  }
}

void md(int &x) {
  if (x >= P) {
    x -= P;
  }
}
void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vc<vi> a(n, vi(n));
  vi deg(n);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    a[x][y] = 1;
    deg[y]++;
  }
  vc<vi> x(n - 1, vi(n - 1));
  vc<vi> y(n, vi(n)), z(n, vi(n));
  rep(i, n) rep(j, n) {
    if (i == j) {
      int dd = 1ll * n * k % P - deg[i] - 1;
      md(y[i][j] = dd + P);
    } else {
      int v = a[i][j];
      y[i][j] = v;
      md(y[i][j] += P - 1);
    }
  }
  if (k == 1) {
    rep(i, n - 1) rep(j, n - 1) x[i][j] = y[i + 1][j + 1];
    cout << val(x) << "\n";
    return;
  }
  rep(i, n - 1) rep(j, n - 1) md(x[i][j] = y[i + 1][j + 1] + P - y[0][j + 1]);
  rep(i, n) rep(j, n) if (i == n - 1) z[i][j] = 1;
  else z[i][j] = y[i][j];
  rep(i, n) rep(j, n) md(y[i][j] += 1);
  debug(x, y, z);
  debug(val(x), val(y), val(z));
  cout << 1ll * val(x) * power(val(y), k - 2) % P * val(z) % P << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

D.

E.

考虑一个状态：没被摧毁并且没看见，那么那一位为 1，否则别的情况都不产生贡献，为 0。

然后直接状压倒着转移就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
int n, m, k;
const int N = 33;
vi g[N], a;
int c[N], id[N];
double dp[N][N][1 << 12];

// 没被摧毁且没看见 1
// 否则 0

double solve(int x, int y, int mask) {
  if (!mask)
    return 0;
  if (dp[x][y][mask] != -lnf) {
    return dp[x][y][mask];
  }
  double &ans = dp[x][y][mask] = 0;
  for (auto v : g[x]) {
    int ii = id[v];
    int msk = mask;
    double res = 0;
    if (ii != -1) {
      if (msk >> ii & 1) {
        msk ^= 1 << ii;
        res += a[ii];
      }
    }
    int ms = 0;
    rep(i, k) {
      if (msk >> i & 1) {
        res += 1ll * 1. / (n - y) * solve(v, y + 1, msk ^ (1 << i));
        ms++;
      }
    }
    if (n - ms - y > 0) {
      res += 1. * (n - ms - y) * 1. / (n - y) * solve(v, y + 1, msk);
    }
    cmax(ans, res);
  }
  return ans;
}

void solve() {
  cin >> n >> m >> k;
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    g[x].pb(y);
    g[y].pb(x);
  }
  int bas = 0;
  rep(i, k) {
    int x;
    cin >> x;
    --x;
    if (x == 0)
      bas++;
    else
      c[x]++;
  }
  rep(i, n) {
    id[i] = -1;
    if (c[i])
      a.pb(c[i]), id[i] = a.size() - 1;
  }
  k = a.size();
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      rep(l, 1 << 12) dp[i][j][l] = -lnf;
  double ans = bas + solve(0, 0, (1 << k) - 1);

  cout << fixed << setprecision(10);
  cout << ans << "\n";
}

F.

先考虑判定无解情况：在 $d_i$ 前没有一个 $d_i - 1$。

考虑按 $d_i$ 分层。

按照 $d_i$ 从小到大填入数字，对于 $d_i$ 相同的，我们倒序填放。

这样可以满足 $d_i$ 大的数字一定大，$d_i$ 相同的话前面大于后面，符合条件。

G.

模拟。

H.

翻译一下题目

给定若干个字符串 $s_{1…n}$，每次给出一个 $t$。

求 $\sum_{i} \sum_{l<r} (l+1)(n-r+1) \times [t[l:r]=s_i]$。

考虑怎么做这个东西，首先可以枚举 $r$，然后可以提出来一个 $(n-r+1)$，剩下的问题就是怎么求出所有合法的 $l+1$。

可以想到用 $AC$ 自动机求解，每次在 $AC$ 自动机的 $fail$ 树上跳。

$fail$ 树上一个点 $i$，$i$ 的祖先和 $i$ 具有相同的后缀，而 $l=r-len_i$，我们只需要把 $len_i$ 放到 $fail$ 树上，然后做一个链前缀和就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
const int P = 1e9 + 7;
const int N = 2e5 + 5;
int ch[N][26];
int cnt = 1;
int hav[N];
ll w[N];
int fail[N];
 
void solve() {
  int n, m;
  cin >> n >> m;
  rep(i, n) {
    string s;
    cin >> s;
    int p = 1;
    for (char x : s) {
      int c = x - 'a';
      if (!ch[p][c]) {
        ch[p][c] = ++cnt;
      }
      p = ch[p][c];
    }
    hav[p] += 1;
    w[p] += sz(s);
  }
  queue<int> q;
  rep(i, 26) if (ch[1][i]) fail[ch[1][i]] = 1, q.emplace(ch[1][i]);
  else ch[1][i] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    rep(i, 26) {
      if (ch[u][i])
        fail[ch[u][i]] = ch[fail[u]][i], q.emplace(ch[u][i]);
      else
        ch[u][i] = ch[fail[u]][i];
    }
  }
  vc<vi> g(cnt + 1);
  debug(g);
  rep(i, 2, cnt + 1) g[fail[i]].pb(i);
  auto dfs = [&](auto &self, int u) -> void {
    debug(u);
    for (auto v : g[u]) {
      w[v] += w[u];
      hav[v] += hav[u];
      self(self, v);
    }
  };
  dfs(dfs, 1);
 
  while (m--) {
    string t;
    cin >> t;
    int l = sz(t);
    int p = 1;
    ll ans = 0;
    for (int i = 0; i < l; i++) {
      int c = t[i] - 'a';
      p = ch[p][c];
      ll val = 1ll * hav[p] * (i + 2) - w[p];
      val %= P;
      ans += 1ll * val * (l - i) % P;
      if (ans >= P) {
        ans -= P;
      }
    }
    cout << ans << "\n";
  }
}

I.

https://www.luogu.com.cn/problem/CF895C

感觉和这个题非常类似。

考虑这里面一定会有 $[1,r]$ 所有质数构成的一个线性基。

意味着假设有 $x$ 个基，那么我们先拿出来这 $x$ 个，还剩下 $n-x$ 个元素，我们可以随意选择， $2^{n-x}$ 种方案，最后通过 $x$ 个基来调整出来一个完全平方数。

卷积即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
namespace Poly {
const int P = 998244353;
const int G = 3;
int power(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = 1ll * x * x % P)
    if (y & 1)
      res = 1ll * res * x % P;
  return res;
}
int inc(int x, int y) { return ((x += y) >= P) ? x - P : x; }
int dec(int x, int y) { return ((x -= y) < 0) ? x + P : x; }
vector<int> rev, rt;
int lim = 1;
void init(const int &len) {
  int l = 0;
  lim = 1;
  while (lim <= len) {
    lim <<= 1, l++;
  }
  rev.resize(lim), rt.resize(lim);
  for (int i = 0; i < lim; i++)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
  for (int len = 1; len < lim; len <<= 1) {
    int w = power(G, (P ^ 1) / (len << 1));
    rt[len] = 1;
    for (int i = 1; i < len; i++) {
      rt[i + len] = 1ll * rt[i + len - 1] * w % P;
    }
  }
}
void ntt(vector<int> &f) {
  f.resize(lim);
  for (int i = 0; i < lim; i++)
    if (i < rev[i]) {
      swap(f[i], f[rev[i]]);
    }
  for (int len = 1; len < lim; len <<= 1) {
    for (int i = 0; i < lim; i += len << 1) {
      for (int j = 0; j < len; j++) {
        int x = f[i + j], y = 1ll * f[i + j + len] * rt[j + len] % P;
        f[i + j] = inc(x, y), f[i + j + len] = dec(x, y);
      }
    }
  }
}

vector<int> operator*(vector<int> f, vector<int> g) {
  int n = f.size(), m = g.size(), inv;
  init(n + m - 2), inv = power(lim, P - 2), ntt(f), ntt(g);
  for (int i = 0; i < lim; i++)
    f[i] = 1ll * f[i] * g[i] % P;
  reverse(f.begin() + 1, f.end()), ntt(f), f.resize(n + m - 1);
  for (int &x : f)
    x = 1ll * x * inv % P;
  return f;
}
} // namespace Poly
using namespace Poly;

const int N = 1e7 + 5;
bool isprime[N];
int pr[N / 10], c = 0;
// const int P = 998244353;
// int power(int x, int y) {
//   int r = 1;
//   while (y) {
//     if (y % 2)
//       r = 1ll * r * x % P;
//     x = 1ll * x * x % P;
//     y /= 2;
//   }
//   return r;
// }
int inv(int x) { return power(x, P - 2); }

ll sp, sq;
int pw[N], ipw[N];

void md(int &x) {
  if (x >= P) {
    x -= P;
  }
}
void solve() {
  int n, l, r;
  cin >> n >> l >> r;
  vi p(n + 1), q(n + 1);

  for (int i = 1; i <= n; i++)
    cin >> p[i], sp += p[i];
  for (int i = 1; i <= n; i++)
    cin >> q[i], sq += q[i];
  sp %= P, sq %= P;
  for (int i = 1; i <= n; i++) {
    p[i] = 1ll * p[i] * inv(sp) % P;
    q[i] = 1ll * q[i] * inv(sq) % P;
  }

  vector<int> f(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    f[i] = 1ll * ipw[l + i] * p[i] % P;
  }
  vector<int> g(n + 1, 0);
  for (int j = 1; j <= n; j++) {
    int bas = upper_bound(pr, pr + c, r - j) - pr;
    g[j] = 1ll * pw[r + 1 - j - bas] * q[j] % P;
  }
  // for (int i = 1; i <= n; i++) {
  //   for (int j = 1; j <= n; j++) {
  //     int bas = upper_bound(pr, pr + c, r - j) - pr;
  //     d[i + j] += 1ll * pw[r - l + 1 - i - j - bas] * p[i] % P * q[j] % P;
  //     if (d[i + j] >= P) {
  //       d[i + j] -= P;
  //     }
  //   }
  // }
  vector<int> d = f * g;
  for (int i = 2; i <= n * 2; i++) {
    cout << d[n * 2 - i + 2] << " \n"[i == n * 2];
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int i = 2; i < N; i++)
    isprime[i] = 1;
  for (int i = 2; i < N; i++) {
    if (isprime[i]) {
      pr[c++] = i;
      for (int j = i * 2; j < N; j += i) {
        isprime[j] = 0;
      }
    }
  }
  pw[0] = 1;
  rep(i, 1, N) pw[i] = pw[i - 1] + pw[i - 1], md(pw[i]);
  const int inv = (P + 1) / 2;
  ipw[0] = 1;
  rep(i, 1, N) ipw[i] = 1ll * ipw[i - 1] * inv % P;
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

J.

考虑设定一个状态 $f_{i,j}$ 表示选择了 $i$ 个技能，成功发动了 $j$ 个的概率。

设定一个状态 $g_{i,j}$ 表示选择了 $i$ 个技能，提早发动了 $j$ 个的概率。

那么对于选择了 $l$ 个技能，答案显然是 $\sum_{i=k}^{l} f_{l,i}-g_{l,i}$。

考虑安排一个顺序让这个式子最大，$f_{i,j}$ 是一个固定的东西，$g_{i,j}$ 显然是按照提早发动的概率排序之后选择最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int n, m, R, q, P;
const int N = 5005;
const int M = 2500 + 2;
double f[N][N], g[N][N];
// f[i][j], 选择了 i 个技能，成功发动了 j 个的概率
// g[i][j]，选择了 i 个技能，成功提前发动了 j 个的概率
// 至少发动 k 个技能，至多 k-1 个技能提前发动的概率

void solve() {
  cin >> n >> m >> R >> q >> P;
  double p = P / 100.;
  f[0][0] = 1.;
  for (int i = 1; i <= n; i++) {
    f[i][0] = f[i - 1][0] * (1 - p);
    for (int j = 1; j <= i; j++) {
      f[i][j] = p * f[i - 1][j - 1] + (1 - p) * f[i - 1][j];
    }
  }
  vc<double> prob;
  rep(i, n) {
    int l, r;
    cin >> l >> r;
    if (r < R)
      prob.pb(1.);
    else if (l < R) {
      int len = r - R;
      prob.pb(1. - 1. * len / (r - l));
    } else {
      prob.pb(0);
    }
  }
  prob.pb(0);
  sort(all(prob));
  debug(prob);
  g[0][0] = 1.;
  for (int i = 1; i <= n; i++) {
    g[i][0] = g[i - 1][0] * (1 - p * prob[i]);
    for (int j = 1; j <= i; j++)
      g[i][j] = p * prob[i] * g[i - 1][j - 1] + (1 - p * prob[i]) * g[i - 1][j];
    // for(int j=0;j<=i;j++)cout<<g[i][j]<<" \n"[j==i];
  }
  cout << fixed << setprecision(10);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      f[i][j] += f[i][j - 1];
  for (int i = 1; i <= n; i++)
    for (int j = n - 1; j >= 0; j--)
      g[i][j] += g[i][j + 1];
  while (q--) {
    int k;
    cin >> k;
    double ans = 0;
    for (int l = k; l <= n; l++) {
      cmax(ans, 1 - f[l][k - 1] - g[l][k]);
    }
    cout << ans << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

K.

$n$ 个人地位等同，输出 $\frac{1}{n}$。

1
2
3
4
5
6
7

void solve() {
  int n, m;
  cin >> n >> m;
  cout << "1/" << n << "\n";
}

L.

$k+1$ 进制暴力枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vc<array<int, 7>> t(m);
  rep(i, m) {
    rep(j, 7) cin >> t[i][j];
    --t[i][0];
    --t[i][1];
  }
  int w = 1;
  rep(i, n) { w *= (k + 1); }
  ll res = 0;
  rep(y, w) {
    int x = y;
    vi a(n);
    rep(j, n) a[j] = x % (k + 1), x /= (k + 1);
    ll ans = 0;
    for (auto [i, j, op, A, B, d, v] : t) {
      int val = A * a[i] + B * a[j];
      bool ok = false;
      if (op == 0 && val <= d)
        ok = true;
      if (op == 1 && val >= d)
        ok = true;
      if (ok)
        ans += v;
    }
    cmax(res, ans);
  }
  cout << res << "\n";
}