AtCoder Beginner Contest 212

发表于2021-08-26更新于2023-09-15字数统计2.4k阅读时长25分

比赛链接

D Querying Multiset

Description

题目链接

Solution

记录一个全局增量，然后用 multiset 维护即可。具体怎么维护可参考 Venice Technique。

Code

Querying Multiset
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;

struct VeniceSet {
    multiset<int> S;
    int water_level = 0;
    void add(int v) { S.insert(v + water_level); }
    void remove(int v) { S.erase(S.find(v + water_level)); }
    void updateAll(int v) { water_level += v; }
    int getMin() { return *S.begin() - water_level; }
    int size() { return S.size(); }
};

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    VeniceSet s;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        if (m == 1)
            cin >> T, s.add(T);
        else if (m == 2)
            cin >> T, s.updateAll(-T);
        else {
            int v = s.getMin();
            cout << v << endl;
            s.remove(v);
        }
    }
    return 0;
}

E Safety Journey

Description

题目链接

Solution

首先要知道如果给出的图是完全图该怎么处理：

设 dpi,jdp_{i,j} 表示从 1 号点出发，走 kk 步到达 ii 的方案数。假设 dpi,kdp_{i,k} 已求出，考虑求解 dpi,k+1dp_{i,k+1}。由于是完全图，因此从除了 ii 以外的点再走一步都可以到达 ii。记 Sk=∑i=1ndpi,kS_k = \sum \limits_{i=1}^{n}dp_{i,k}，于是有 dpi,k+1=Sk−dpi,kdp_{i,k+1} = S_k-dp_{i,k}，从而可以在 O(NK)O(NK) 时间内得到答案 dp1,Kdp_{1,K}。

本题在完全图中去掉了一些边，但可以借鉴上述做法，记录哪些点不和当前节点直接相连，然后将这些点对 SS 的贡献扣除即可。

Code

Safety Journey
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 5005;
const int MOD = 998244353;
int n, m, k, u, v;
vector<int> G[MAXN];
int dp[MAXN], f[MAXN];

signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dp[1] = 1;
    for (int i = 1; i <= k; i++) {
        int tot = 0;
        for (int j = 1; j <= n; j++) tot = (tot + dp[j]) % MOD;
        for (int j = 1; j <= n; j++) {
            f[j] = 0;
            for (auto& to : G[j]) f[j] = (f[j] + dp[to]) % MOD;
        }
        for (int j = 1; j <= n; j++) dp[j] = ((tot - dp[j]) % MOD - f[j]) % MOD;
    }
    cout << (dp[1] + MOD) % MOD;
    return 0;
}

F Greedy Takahashi

Description

题目链接

Solution

以各个班车为节点，根据转乘关系，由当前班车向下一次乘坐的班车连边，最后得到一个森林。给定起始城市和时间，可以二分查找首次搭乘的班车号，然后再利用树上倍增可以知道 TakahashiTakahashi 在结束时刻会停留在哪一个城市或者在哪辆车上。

Code

Greedy Takahashi
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

const int MAXN = 1E5 + 5;
const int MOD = 1E9 + 7;
int n, m, q;
vector<int> G[MAXN];
vector<pair<int, int>> city[MAXN];
array<int, MAXN> in, a, b, s, t, p[22];

void dfs(int now) {
    for (auto& to : G[now]) {
        for (int j = 1; j <= 20; j++)
            if (p[j - 1][to]) p[j][to] = p[j - 1][p[j - 1][to]];
        dfs(to);
    }
}

signed main() {
    read(n, m, q);
    for (int i = 1; i <= m; i++) {
        read(a[i], b[i], s[i], t[i]);
        city[a[i]].push_back({s[i], i});
    }
    for (int i = 1; i <= n; i++) sort(city[i].begin(), city[i].end());
    for (int i = 1; i <= n; i++) {
        for (auto& [s, j] : city[i]) {
            auto it = lower_bound(city[b[j]].begin(), city[b[j]].end(),
                                  make_pair(t[j], 0));
            if (it != city[b[j]].end()) {
                G[it->second].push_back(j);
                p[0][j] = it->second;
                in[j]++;
            }
        }
    }
    for (int i = 1; i <= m; i++)
        if (!in[i]) dfs(i);
    for (int i = 1; i <= q; i++) {
        int x, y, z;
        read(x, y, z);
        auto it = lower_bound(city[y].begin(), city[y].end(), make_pair(x, 0));
        if (it == city[y].end())
            printf("%d\n", y);
        else {
            int bus = it->second;
            if (z <= s[bus])
                printf("%d\n", y);
            else {
                for (int j = 20; ~j; j--)
                    if (p[j][bus] && s[p[j][bus]] < z) bus = p[j][bus];
                if (z <= t[bus])
                    printf("%d %d\n", a[bus], b[bus]);
                else
                    printf("%d\n", b[bus]);
            }
        }
    }
    return 0;
}

G Power Pair

Description

题目链接

Solution

显然 x=0,y=0x=0,y=0 是一个解，下面仅讨论 x≠0,y≠0x \neq 0, y \neq 0 的情况。

设 rr 为 PP 的原根，令 x≡ra(modP),y≡rb(modP)x≡r^a\pmod P,y≡r^b\pmod P，其中 1≤a,b≤P−11 \le a,b \le P-1，则：

xn≡y(modP)⇔ran≡rb(modP)⇔an≡b(modP−1)x^n≡y\pmod P⇔ r^{an}≡r^b\pmod P ⇔ an≡b\pmod {P−1}

上式最右边的等价关系由费马小定理推得。

an≡b(modP−1)an≡b\pmod {P−1} 有解当且仅当 gcd(a,P−1)∣bgcd(a,P-1)|b，对于给定的 aa，可知满足条件的 bb 的个数是 P−1gcd(a,P−1)\frac{P-1}{gcd(a,P-1)}，因此总的答案为 ∑a=1P−1P−1gcd(a,P−1)\sum\limits_{a=1}^{P-1}\frac{P-1}{gcd(a,P-1)}。

注意到 gcd(a,P−1)gcd(a,P-1) 的个数不会超过 P−1P-1 的因数的个数，我们可以 O(P)O(\sqrt{P}) 求出 P−1P-1 的所有因数，设为 g1,g2,…,gdg_1,g_2,\dots,g_d，那么答案可以写成 ∑i=1dP−1gi∗f(gi)\sum\limits_{i=1}^{d}\frac{P-1}{g_i}*f(g_i)，其中 f(gi)f(g_i) 表示满足 gi=gcd(a,P−1)g_i=gcd(a,P-1) 的 aa 的个数。考虑容斥可以 O(d2)O(d^2) 求解 f(g1),f(g2),…,f(gd)f(g_1),f(g_2),\dots,f(g_d)，因此总的时间复杂度为 O(N+d2)O(\sqrt{N}+d^2)。

官方题解中提到 101210^{12} 内因数最多的数是 963761198400963761198400，它的因数个数是 67206720，故上述解法的效率可以得到保证。

Code

Power Pair
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MOD = 998244353;
LL p;
vector<LL> fac;
unordered_map<LL, LL> f;

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

signed main() {
    cin >> p;
    p--;
    for (int i = 1; i <= sqrt(p); i++) {
        if (p % i == 0) {
            fac.push_back(i);
            if (p / i != i) fac.push_back(p / i);
        }
    }
    sort(fac.begin(), fac.end());
    for (int i = fac.size() - 1; ~i; i--) {
        (f[fac[i]] += p / fac[i]) %= MOD;
        for (int j = i - 1; ~j; j--)
            if (fac[i] % fac[j] == 0) (f[fac[j]] -= f[fac[i]]) %= MOD;
    }
    LL ans = 0;
    for (auto& v : fac) {
        ans += p % MOD * qpow(v, MOD - 2, MOD) % MOD * f[v] % MOD;
        ans %= MOD;
    }
    cout << (ans + 1 + MOD) % MOD;
    return 0;
}

H Nim Counting

Description

题目链接

Solution

定义异或卷积 X∗Y=Z=(∑i⊕j=0XiYj,∑i⊕j=1XiYj,…,∑i⊕j=K−1XiYj)X*Y=Z=(\sum\limits_{i⊕j=0}X_iY_j,\sum\limits_{i⊕j=1}X_iY_j,\dots,\sum\limits_{i⊕j=K-1}X_iY_j)，其中 X,YX,Y 均为长为 K=2kK=2^k 的序列。

令 Ci=[∃j，Aj=i]C_i = [\exist j，A_j=i]，则对于一个确定的 MM，答案为 C∗C∗…(M times)⋯∗CC*C*\dots(M \ times)\dots*C 中下标不为 00 的项的和，由快速沃尔什变换，即 ∑i=1K−1IFWT(FWT(C)iM)\sum \limits_{i=1}^{K-1}IFWT(FWT(C)_i^M)，因此总的答案为 ∑M=1N∑i=1K−1IFWT(FWT(C)iM)=∑i=1K−1IFWT(∑M=1NFWT(C)iM)\sum\limits_{M=1}^{N}\sum \limits_{i=1}^{K-1}IFWT(FWT(C)_i^M) = \sum \limits_{i=1}^{K-1}IFWT(\sum\limits_{M=1}^{N} FWT(C)_i^M)。

我们先对 CC 做快速沃尔什变换，对每一项利用等比数列公式求和（注意 Ci=0C_i=0 的情况），再反变换对下标不为 00 的项求和即可得到答案。

时间复杂度：O(A(logA+logN))O(A(logA+logN))。

Code

Nim Counting
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 <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

#define int long long
const int MAXN = 2E5 + 5;
const int MOD = 998244353;
int n, k;
int c[MAXN];

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void FWT_XOR(int* A, int N, int tag) {
    for (int sz = 1; sz < N; sz *= 2)
        for (int i = 0; i < N; i += sz * 2)
            for (int k = 0; k < sz; k++) {
                const int x = A[i + k], y = A[i + k + sz];
                A[i + k] = (x + y) % MOD;
                A[i + k + sz] = (x - y) % MOD;
            }
    if (tag == -1)
        for (int i = 0; i < N; i++) (A[i] *= qpow(N, MOD - 2, MOD)) %= MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    int N = (1 << 16);
    for (int i = 1, x; i <= k; i++) cin >> x, c[x] = 1;
    FWT_XOR(c, N, 1);
    for (int i = 0; i < N; i++) {
        if (c[i] == 1)
            c[i] = n;
        else
            c[i] = c[i] * (1 - qpow(c[i], n, MOD)) % MOD *
                   qpow(1 - c[i], MOD - 2, MOD) % MOD;
    }
    FWT_XOR(c, N, -1);
    int ans = 0;
    for (int i = 1; i < N; i++) ans = (ans + c[i]) % MOD;
    cout << (ans + MOD) % MOD;
    return 0;
}