跃迁引擎启动

ExaWizards 2019 题解

发表于 更新于 分类于 阅读次数：

开始日常 AtCoder 的 ABC 场以外题解（不咕咕咕的话。

A Regular Triangle

B Red or Blue

C Snuke the Wizard

给定一个长度为 $n$ 的一排房间，每个房间有个字母，一开始每个房间只有一个人。

之后有 $q$ 次操作，每次操作将待在所有房间字母为 $s_i$ 的房间内的所有人，向左或右平移一个格子。

若移动到最左边和最右边之外，这个人就没得了，求最后剩多少人。

注意到，人是一个格子一个格子平移的，不会有人跨越的现象。

因此掉落到左边一定是一个前缀，掉到右边的一定是一个后缀，二分前缀和后缀的长度即可。

降智严重，sb 二分竟然没想到。

D Modulo Operations

好题！

给定一个数字 $x$，有一个集合 $S$，每次随机从集合内删除一个数 $y$，将当前数字 $x$ 变成 $x$ mod $y$。

求将集合删光时，当前数字的期望。

注意到，每次都是取模操作，所以当前数字一定是单调不增的。其次，若一开始选了一个比较小的数字，则后面可以任意选择较大的数而不会产生影响。

这就等价于，给定一个单调递减的操作序列 $S$，对于第 $i$ 个操作，有 $1 \over n-i+1$ 的概率，对当前数取模。

对于已经进行过的 $i-1$ 次操作，每个数都有一个出现的概率，于是我们考虑第 $i$ 个数对于每个概率的影响，若选了这个数，进行这个操作，反之代表这个数会进行之后的操作。

也就是对于 $f(i,x)$ 表示进行到第 $i$ 次操作时，当前数为 $x$ 的概率，有转移方程

$$
f(i,x \text{ mod } a_i)=f(i-1,x) \cdot {1 \over n-i+1} \
f(i,x) = f(i-1,x) \cdot (1 - {1 \over n-i+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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int a, b, c;

int main() {
    cin >>a >> b >> c;
    if (a == b && b == c) puts("Yes");
    else puts("No");
    return 0;
}

B

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int n; char s[maxn];

int main() {
    cin >> n >> s + 1;
    int c1 = 0, c2 = 0;
    for (int i = 1; i <= n; i++) if (s[i] == 'R') c1++; else c2++;
    if (c1 > c2) puts("Yes");
    else puts("No");
    return 0;
}

C

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;

int n, q;
char s[maxn], t[maxn], d[maxn];

int check(int x) {
    int tot = x;
    for (int i = 1; i <= q; i++) {
        if (t[i] == s[tot]) {
            if (d[i] == 'L') tot--;
            else tot++;
            if (tot == 0) return 1;
            else if (tot == n + 1) return -1;
        }
    }
    return 0;
}

int main() {
    scanf("%d%d%s", &n, &q, s + 1);
    for (int i = 1; i <= q; i++) {
        char tmp1[3], tmp2[3]; scanf("%s%s", tmp1, tmp2);
        t[i] = tmp1[0]; d[i] = tmp2[0];
    }
    int l = 1, r = n, ans1 = 0, ans2 = n + 1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m) == 1) l = m + 1, ans1 = m;
        else r = m - 1;
    }
    l = 1, r = n;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m) == -1) r = m - 1, ans2 = m;
        else l = m + 1;
    }
    cout << n - ans1 - (n - ans2 + 1) << endl;
    return 0;
}

D

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
#ifdef XLor
  #define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
  #define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 1e9 + 7;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

ll qpow(ll x, ll n) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        n >>= 1; x = x * x % mod;
    }
    return r;
}
ll inv(ll x) { return qpow(x, mod - 2); }
inline void add(ll& x, ll y) {
    x += y; if (x >= mod) x -= mod;
}

int n, x, a[205];
ll dp[205][maxn];

int main() {
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n); dp[n][x] = 1;
    for (int i = n - 1; i >= 0; i--) {
        ll iv = inv(i + 1);
        for (int j = 0; j <= x; j++) {
            add(dp[i][j % a[i]], dp[i + 1][j] * iv % mod);
            add(dp[i][j], (dp[i + 1][j] - dp[i + 1][j] * iv % mod + mod) % mod);
        }
    }
    ll ans = 0, f = 1;
    for (int i = 1; i <= n; i++) f = f * i % mod;
    for (int i = 0; i <= x; i++) add(ans, i * dp[0][i] % mod);
    cout << ans * f % mod << endl;
    return 0;
}