Codeforces Round 901 (Div. 1)

A.

考虑奇偶性，贪心就可以。

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
#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

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> b(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  sort(all(a));
  sort(all(b));
  if (a[0] < b[m - 1]) {
    swap(a[0], b[m - 1]);
    k -= 1;
    if (k % 2 == 1) {
      int p1 = max_element(all(a)) - a.begin();
      int p2 = min_element(all(b)) - b.begin();
      swap(a[p1], b[p2]);
    }
  } else {
    k -= 1;
    if (k) {
      int p1 = max_element(all(a)) - a.begin();
      int p2 = min_element(all(b)) - b.begin();
      swap(a[p1], b[p2]);
      k -= 1;
      if (k % 2 == 1) {
        int p1 = min_element(all(a)) - a.begin();
        int p2 = max_element(all(b)) - b.begin();
        swap(a[p1], b[p2]);
      }
    }
  }
  cout << accumulate(all(a), 0LL) << "\n";
}

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

B.

考虑 (0/1, 0/1, 0/1)，一共 8 种情况。

然后把每一位的情况记录下来。然后跑 bfs，一共的情况数量只有 1552 种。

复杂度 $O(T \times 1552)$

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
#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 dp[256][256];
vector<tuple<int, int, int>> tuples;
void solve() {
  int a, b, c, d, m;
  cin >> a >> b >> c >> d >> m;
  array<int, 8> X;
  rep(i, 8) X[i] = 0;
  rep(i, 30) {
    int e = 0;
    if (a >> i & 1) {
      e += 1;
    }
    if (b >> i & 1) {
      e += 2;
    }
    if (m >> i & 1) {
      e += 4;
    }
    X[e] ^= 1 << i;
  }

  int ans = inf;
  for (auto [x, y, dist] : tuples) {
    int xx = 0, yy = 0;
    rep(i, 8) xx |= (x >> i & 1) * X[i];
    rep(i, 8) yy |= (y >> i & 1) * X[i];
    if (xx == c && yy == d) {
      cmin(ans, dist);
    }
  }
  if (ans == inf) ans = -1;
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  memset(dp, 0x3f, sizeof dp);
  {
    int a = 0, b = 0, m = 0;
    rep(i, 0, 2) {
      rep(j, 0, 2) {
        rep(k, 0, 2) {
          int v = i + j * 2 + k * 4;
          if (i) {
            a |= 1 << v;
          }
          if (j) {
            b |= 1 << v;
          }
          if (k) {
            m |= 1 << v;
          }
        }
      }
    }
    dp[a][b] = 0;
    queue<pair<int, int>> q;
    q.emplace(a, b);
    auto add = [&](int x, int y, int d) {
      if (dp[x][y] > d) {
        dp[x][y] = d;
        q.emplace(x, y);
      }
    };
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop();
      int d = dp[x][y];
      add(x & y, y, d + 1);
      add(x | y, y, d + 1);
      add(x, x ^ y, d + 1);
      add(x, y ^ m, d + 1);
    }
  }
  rep(x, 256) rep(y, 256) if (dp[x][y] != 0x3f3f3f3f) {
    tuples.emplace_back(x, y, dp[x][y]);
  }
  debug(tuples.size());
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

C.

倒着考虑，定义 $f_x$ 为 $x$ 走到 $n$ 的概率。

考虑 $x$ 的所有出边为 ${y}$，按照 $f_y$ 排序，肯定是贪心的走最大的。

然后就是走第几个相关的概率了。

定义 $prob_{i,j}$ 为 $i$ 条出边下，能成功走到第 $j$ 条边的概率。

显然 $prob_{1,1} = 1, prob_{2,1}=1/2,prob_{2,2}=0, prob_{k, 1} = 1/k$。

然后来考虑 $prob_{i, j}$ 怎么转移。

  • 考虑如果在前 $j$ 条里面删了两条边（此时肯定选的是 $1$ 和 $1 < k < j$），那么问题规模变成 $(i-2,j-2)$。
  • 考虑如果在前 $j$ 条里面删了一条，后面又删了一条（选的是 $1$ 和 $j < k \leq i$），那么问题规模变成 $(i-2,j-1)$。
  • 如果选了 1 或者 $j$，那么显然走 $j$ 的概率为 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
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#include <iomanip>
#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 N = 5005;
double prob[N][N];
void solve() {
  int n, m;
  cin >> n >> m;
  vc<vi> e(n);
  while (m--) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    e[x].pb(y);
  }
  vc<double> f(n);
  f[n - 1] = 1;
  for (int i = n - 1; i >= 0; i--) {
    vc<double> p;
    for (auto j : e[i]) {
      p.pb(f[j]);
    }
    sort(all(p), greater<double>());
    for (int j = 0; j < sz(p); j++) {
      f[i] += p[j] * prob[sz(p)][j + 1];
    }
  }
  cout << fixed << setprecision(20) << f[0] << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  for (int i = 1; i < N; i += 2) {
    for (int j = 1; j <= i; j++) {
      prob[i][j] = 1. / i;
    }
  }
  prob[2][1] = .5;
  for (int i = 4; i < N; i++) {
    prob[i][1] = 1. / i;
    for (int j = 2; j < i; j++) {
      prob[i][j] = (1. * (j - 2) * prob[i - 2][j - 2] +
                    1. * (i - j) * prob[i - 2][j - 1]) /
                   i;
    }
  }
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

D.

$f_0 = 0, f_1 = 1$。

$f_{i} = f_{i-1} + 1 + \frac{a_{i-1}}{a_{i-1}+a_{i}} \times (f_i - f_{i-2})$.

$\to f_i = f_{i-1}+1+ \frac{a_{i-1}}{a_i} \times (f_{i-1} - f_{i-2} + 1)$.

令 $g_1 = 1, g_i = f_i - f_{i-1}$.

$g_i = 1 + \frac{a_{i-1}}{a_i} \times (g_{i-1} + 1)$

考虑求出 $g_i$，$f_n = \sum g_i = n+2 \sum\frac{s_{i-1}}{a_i}$。

具有决策单调性，直接分治就做完了。

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
#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 N = 3005;
double dp[N][N];
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i][j] = inf;
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    auto solve = [&](auto self, int l, int r, int L, int R) -> void {
      if (l > r) {
        return;
      }
      int m = (l + r) / 2, p = L;
      rep(x, L, min(R + 1, m)) {
        if (dp[i - 1][x] + 1. * x / (m - x) < dp[i - 1][p] + 1. * p / (m - p)) {
          p = x;
        }
      }
      dp[i][m] = dp[i - 1][p] + 1. * p / (m - p);
      self(self, l, m - 1, L, p);
      self(self, m + 1, r, p, R);
    };
    solve(solve, i, m, i - 1, m);
  }
  cout << fixed << setprecision(12) << dp[n][m] * 2 + n - 2 << "\n";

}

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

E.

考虑暴力 $n^6$ 的 $dp$。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 7, M = 4e4 + 7, p = 1e9 + 7;
int n, k, dp[N][M], c[N][N];
int binom(int a, int b) { return c[a][b]; }
int main() {
  for (int i = 0; i <= 200; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;
  }
  cin >> n >> k;
  int ans = 0;
  dp[1][1] = 1, dp[0][0] = 1;
  for (int x = 2; x <= n; x++)
    for (int i = 0; i < x; i++) {
      int j = x - 1 - i;
      for (int a = 0; a <= i * i; a++)
        for (int b = 0; b <= j * j; b++)
          dp[i + j + 1][a + b + x] =
              (dp[i + j + 1][a + b + x] +
               1ll * dp[i][a] * dp[j][b] % p * binom(i + j, i)) %
              p;
    }
  for (int i = 0; i <= n * n; i++) {
    cout << dp[n][i] << " \n"[i == n * n];
  }
  return 0;
}

$F_{i+j+1} = F_i F_j \binom{i+j}{i} x^{i+j+1}$

就是这个多项式相乘，最后的 $F_n$ 就是答案。

考虑怎么求出 $F_n$，$F_n$ 一共有 $O(n^2)$ 项。

考虑直接算出 $F_{n}(z), z \in [0, n^2]$ 的答案，然后插值出来 $F_n$ 这个多项式。

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
#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 = 1e9 + 7;
ll power(ll x, ll y) {
  ll res = 1;
  while (y) {
    if (y % 2 == 1) {
      res = res * x % P;
    }
    x = x * x % P;
    y /= 2;
  }
  return res;
}

void solve() {
  int n, k;
  cin >> n >> k;
  int m = n * (n + 1) / 2 + 1;
  vector<ll> op(m + 1);
  vector<ll> fac(m + 1), ifac(m + 1);
  fac[0] = 1;
  for (int i = 1; i <= m; i++) {
    fac[i] = fac[i - 1] * i % P;
  }
  ifac[m] = power(fac[m], P - 2);
  for (int i = m - 1; i >= 0; i--) {
    ifac[i] = ifac[i + 1] * (i + 1) % P;
  }

  auto binom = [&](int x, int y) {
    return fac[x] * ifac[x - y] % P * ifac[y] % P;
  };

  for (int x = 1; x <= m; x++) {
    vector<ll> pw(n + 1);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
      pw[i] = pw[i - 1] * x % P;
    }
    vector<ll> dp(n + 1);
    dp[0] = 1, dp[1] = x;
    for (int t = 2; t <= n; t++) {
      for (int i = 0; i < t; i++) {
        int j = t - 1 - i;
        dp[t] += dp[i] * dp[j] % P * binom(i + j, i) % P * pw[t] % P;
        if (dp[t] >= P) {
          dp[t] -= P;
        }
      }
    }
    op[x] = dp[n];
  }
  for (int i = 1; i <= m; i++) {
    op[i] = op[i] * ifac[i - 1] % P * ifac[m - i] % P;
    if ((m - i) % 2 == 1) {
      op[i] = P - op[i];
    }
  }
  vector<array<ll, 2>> f(m + 2);
  f[0][0] = 1;
  for (int i = 1; i <= m; i++) {
    vector<array<ll, 2>> g(m + 2);
    for (int j = 0; j <= i; j++) {
      g[j][1] += f[j][0] * op[i] % P;
      g[j][1] += f[j][1] * (P - i) % P;
      g[j][1] %= P;
      g[j + 1][1] += f[j][1];
      if (g[j + 1][1] >= P) {
        g[j + 1][1] -= P;
      }
      g[j][0] += f[j][0] * (P - i) % P;
      if (g[j][0] >= P) {
        g[j][0] -= P;
      }
      g[j + 1][0] += f[j][0];
      if (g[j + 1][0] >= P) {
        g[j + 1][0] -= P;
      }
    }
    f.swap(g);
  }
  ll ans = 0;
  for (int i = k; i <= m; i++) {
    ans += f[i][1];
    if (ans >= P) {
      ans -= P;
    }
  }
  cout << ans << "\n";
}

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