壁纸链接
题目链接：https://atcoder.jp/contests/abc470/tasks

A - Fizz#

直接遍历 $1$ 到 $N$ 。如果 $i\bmod 3=0$ ，说明 $i$ 是 $3$ 的倍数，输出 $Fizz$ ；否则输出 $i$ 本身。

1
void solved(){
2
    int n; cin >> n;
3
    for(int i = 1; i <= n;i++){
4
        if(i % 3 == 0) cout << "Fizz" << endl;
5
        else cout << i << endl;
6
    }
7
}

B - Monocolor#

假设最终统一为颜色 $c$ ，那么原本颜色为 $c$ 的球不需要修改，其余 $N-cnt_c$ 个球都需要修改。为了让操作次数最少，应当保留出现次数最多的颜色。
我们用 $cnt[c]$ 统计每种颜色的出现次数，设最大频次为 $ma$ ，最终答案就是 $N-ma$ 。

1
void solve(){
2
    int n; cin >> n;
3
    vector<int> cnt(n + 1, 0);
4
    for(int i = 1; i <= n;i++){
5
        int x; cin >> x;
6
        cnt[x]++;
7
    }
8
    int ma = 0;
9
    for(int i = 1; i <= n;i++){
10
        ma = max(ma, cnt[i]);
11
    }
12
    cout << n - ma << endl;
13
}

C - Inc, Dec, Xor#

我们用 $ans=A_1\oplus A_2\oplus\cdots\oplus A_N$ 维护当前异或和。异或具有自反性，即 $x\oplus x=0$ ，所以当某个元素从 $old$ 变为 $new$ 时，可以通过 $ans\leftarrow ans\oplus old\oplus new$ 先消去旧贡献，再加入新贡献，不需要重新计算整个数组。
对于第一类操作，只有 $A_x$ 发生变化，直接用上述公式将它从 $A_x$ 更新为 $A_x+1$ 。对于第二类操作，只需要处理当前大于 $0$ 的元素。代码用 $active$ 保存这些下标，每次将其中的元素减一，并把减完后仍大于 $0$ 的下标压缩到数组前部；元素第一次从 $0$ 变成 $1$ 时才加入 $active$ 。
虽然一次第二类操作可能遍历多个下标，但每次遍历都会让某个正数减少 $1$ ，这个减少量一定来自此前的一次加一操作。因此所有第二类操作的总遍历次数不超过第一类操作的数量，整体复杂度为 $O(N+Q)$ 。

1
void solve(){
2
    int n, q;
3
    cin >> n >> q;
4

5
    int ans = 0;
6
    vector<int> a(n + 1, 0), active;
7
    while(q--){
8
        int op; cin >> op;
9
        if(op == 1){
10
            int x; cin >> x;
11
            if(a[x] == 0) active.push_back(x);
12
            ans = ans ^ a[x] ^ (a[x] + 1);
13
            a[x]++;
14
        }
15
        else{
16
            int remain = 0;
17
            for(auto x : active){
18
                ans = ans ^ a[x] ^ (a[x] - 1);
19
                a[x]--;
20
                if(a[x] > 0) active[remain++] = x;
21
            }
22
            active.resize(remain);
23
        }
24
        cout << ans << endl;
25
    }
26
}

D - Inverse and Swap#

第二类操作的条件 $P_{P'_i}=i$ 说明 $P'=P^{-1}$ ，也就是把当前排列替换为它的逆排列。由于 $(P^{-1})^{-1}=P$ ，连续执行两次求逆会回到原排列，所以只需要用布尔变量 $re$ 记录当前应当把哪一个数组视为答案。
代码同时维护 $a[i]=P_i$ 和 $pos[v]=P^{-1}_v$ 。当 $re=false$ 时，第一类操作交换当前排列中的两个位置 $a[x],a[y]$ ，并同步更新这两个值在 $pos$ 中的位置；当 $re=true$ 时，当前排列是 $pos$ ，于是交换 $pos[x],pos[y]$ ，再对其逆排列 $a$ 做对应更新。第二类操作不需要实际重建数组，只需要翻转 $re$ 。
这样每次查询都能在 $O(1)$ 时间内完成，最后根据 $re$ 输出 $a$ 或 $pos$ 即可。总时间复杂度为 $O(N+Q)$ 。

1
void solve(){
2
    int n, q; cin >> n >> q;
3

4
    vector<int> a(n + 1, 0);
5
    vector<int> pos(n + 1, 0);
6
    for(int i = 1; i <= n;i++){
7
        cin >> a[i];
8
        pos[a[i]] = i;
9
    }
10
    bool re = false;
11
    while(q--){
12
        int op; cin >> op;
13
        if(op == 1){
14
            int x, y; cin >> x >> y;
15
            if(!re){
16
                int temp = a[x]; a[x] = a[y]; a[y] = temp;
17
                temp = pos[a[x]]; pos[a[x]] = pos[a[y]];
18
                pos[a[y]] = temp;
19
            }
20
            else{
21
                int temp = pos[x]; pos[x] = pos[y]; pos[y] = temp;
22
                temp = a[pos[x]]; a[pos[x]] = a[pos[y]];
23
                a[pos[y]] = temp;
24
            }
25
        }
26
        else re = !re;
27
    }
28
    if(!re) for(int i = 1; i <= n;i++)
29
        cout << a[i] << " ";
30
    else for(int i = 1; i <= n;i++)
31
        cout << pos[i] << " ";
32
    cout << endl;
33
}

E - Concentration#

这题需要使用概率 $dp$ 。在最优策略下，已经知道位置的一对相同卡片一定会被直接消除，因此状态只需要记录尚未完全确定的卡片。定义 $F_i(j,k)$ 表示还剩 $i$ 点生命、存在 $j$ 种两张位置都未知的卡片、 $k$ 种已经知道一张位置但另一张仍未知的卡片时，最终能够消除的卡片对数的期望。此时未知位置的卡片总数为 $U=2j+k$ 。
每轮先翻开一张未知卡片。如果它属于已有的 $k$ 个单张信息之一，概率为 $\frac{k}{U}$ ，可以立即选择已知的另一张完成配对，转移到 $1+F_i(j,k-1)$ 。否则它来自 $j$ 个完全未知的卡片对，概率为 $\frac{2j}{U}$ ，再翻开一张未知卡片时有三种情况：
第一种是恰好翻到同一对中的另一张，概率为 $\frac{1}{U-1}$ ，成功配对后转移到 $1+F_i(j-1,k)$ 。
第二种是翻到已有 $k$ 个单张信息之一的对应卡片，概率为 $\frac{k}{U-1}$ 。本轮失配并损失一点生命，但在生命仍大于 $0$ 时，原来已经记住的那张卡可以保证形成一对；同时本轮第一张卡成为新的单张信息，所以转移到 $1+F_{i-1}(j-1,k)$ 。
第三种是翻到其他完全未知卡片对中的一张，概率为 $\frac{2(j-1)}{U-1}$ 。本轮失配后新增两个单张信息，转移到 $F_{i-1}(j-2,k+2)$ 。当 $i=1$ 时，后两种失配会使游戏立即结束，因此后续贡献为 $0$ 。
成功转移依赖同一生命值下规模更小的状态，失配转移依赖上一层生命值，所以代码按生命值从小到大计算，并用两个二维数组滚动。由于所有卡片对在随机排列中完全对称，每一对最终被消除的概率都等于 $F_L(N,0)/N$ 。因此最终得分期望为 $\frac{F_L(N,0)}{N}\sum_{i=1}^{N}A_i$ 。时间复杂度为 $O(LN^2)$ 。

1
void solve(){
2
    int n, l; cin >> n >> l;
3
    ll sum = 0;
4
    for(int i = 1; i <= n;i++){
5
        int x; cin >> x;
6
        sum += x;
7
    }
8
    /*
9
        dp[j][k]表示当前状态下已完成配对的个数。
10
        j表示还未知的单个卡片个数，k表示目前已知一个卡片，还差另一个的个数。
11
        ndp记录的是上一次dp的状态，因为dp在计算时会用到上一次dp的状态
12
    */
13
    vector<vector<double>> ndp(n + 1, vector<double>(n + 1, 0.0));
14

15
    for(int i = 1; i <= l;i++){
16

17
        //当前状态下的dp。
18
        vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0.0));
19

20
        for(int j = 0; j <= n;j++){
21
            for(int k = 0; j + k <= n; k++){
22
                if(j == 0 && k == 0) continue;
23

24
                int unknown = 2 * j + k;
25
                double ans = 0.0;
26

27
                //第一张未知的卡和已知卡成对
28
                if(k > 0)
29
                    ans += (double)k / unknown * (1.0 + dp[j][k - 1]);
30

31
                //第一张未知的卡不和任何已知卡成对
32
                if(j > 0){
33
                    double newone = 0.0;
34

35
                    //第二张卡是这张未知卡的配对
36
                    newone += (1.0 + dp[j - 1][k]) / (unknown - 1);
37

38
                    //剩下的两种情况都会损失生命值，需要判断是否大于1才能继续
39
                    if(i > 1){
40

41
                        //第二张卡与原来的k张卡可以配对
42
                        if(k > 0)
43
                            newone += (double)k / (unknown - 1) * (1.0 + ndp[j - 1][k]);
44

45
                        //第二张卡是其他的未知卡
46
                        if(j > 1)
47
                            newone += (double)(2 * (j - 1)) / (unknown - 1) * ndp[j - 2][k + 2];
48
                    }
49

50
                    ans += (double)(2 * j) / unknown * newone;
51
                }
52
                dp[j][k] = ans;
53
            }
54
        }
55
        ndp.swap(dp);
56
    }
57

58
    //每一对牌获得的概率都为p = ndp[n][0] / n, 因此期望就是累加每个A元素乘p。
59
    double res = ndp[n][0] / n * double(sum);
60
    printf("%.15lf\n", res);
61
}

F - Googol Swaps#

把字符串位置看作图上的点，每个允许交换的位置对 $(A_i,B_i)$ 看作一条边。沿连通块内的边进行交换可以生成该连通块中任意位置置换，因此不同连通块相互独立。使用并查集求出所有连通块，并统计每个连通块内 $26$ 种字符的出现次数。
对于大小为 $s$ 的连通块，如果字符 $c$ 出现 $cnt_c$ 次，那么忽略交换次数奇偶性时，该连通块可以形成的不同字符串数量为多重集合排列数 $\frac{s!}{\prod_c cnt_c!}$ 。将所有连通块的方案数相乘即可得到总排列数，阶乘与逆阶乘可以预处理。
本题要求恰好执行 $10^{100}$ 次交换，这是一个偶数，所以最终的位置置换必须是偶置换。连通块内的任意偶置换都可以通过边上的交换实现，并且可以把同一条边连续交换两次来增加 $2$ 次操作，因此这个足够大的操作次数只会限制置换的奇偶性。如果某个连通块内存在重复字符，那么交换两个相同字符不会改变最终字符串，却可以改变置换的奇偶性。因此每个可形成的字符串都同时存在奇、偶两种生成方式，所有多重集合排列都合法。
如果所有连通块内部都没有重复字符，那么最终字符串能够唯一确定各连通块中的位置置换，所有方案中恰好一半对应偶置换，所以答案需要乘以 $2$ 的模逆元。并查集部分的时间复杂度为 $O((N+M)\alpha(N))$ ，频次统计与组合数计算为 $O(26N)$ ，空间复杂度为 $O(26N)$ 。

1
void solve(){
2
    int n, m; cin >> n >> m;
3
    string s; cin >> s;
4

5
    // 阶乘和逆阶乘预处理
6
    vector<ll> f(n + 1, 1);
7
    vector<ll> inverse_f(n + 1, 1);
8
    for(int i = 1; i <= n;i++) f[i] = f[i - 1] * i % mod;
9
    inverse_f[n] = fast_pow(f[n], mod - 2, mod);
10
    for(int i = n;i >= 1;i--)
11
        inverse_f[i - 1] = inverse_f[i] * i % mod;
12

13
    // 连通块处理
14
    vector<int> fa(n), sz(n, 1);
15
    iota(fa.begin(), fa.end(), 0);
16

17
    auto Find = [&](auto &&self, int x) -> int {
18
        if(fa[x] == x) return x;
19
        return fa[x] = self(self, fa[x]);
20
    };
21

22
    auto unite = [&](int x, int y){
23
        int fx = Find(Find, x);
24
        int fy = Find(Find, y);
25
        if(fx == fy) return;
26
        if(sz[fx] < sz[fy]) swap(fx, fy);
27
        fa[fy] = fx;
28
        sz[fx] += sz[fy];
29
    };
30

31
    // 构造连通块
32
    for(int i = 0; i < m;i++){
33
        int a, b; cin >> a >> b;
34
        unite(a - 1, b - 1);
35
    }
36

37
    // 记录每个连通块内各字符出现的频率
38
    vector<array<int, 26>> freq(n);
39
    for(int i = 0; i < n;i++){
40
        int u = Find(Find, i);
41
        freq[u][s[i] - 'a']++;
42
    }
43

44
    ll ans = 1;
45
    bool repeat = false;
46
    for(int i = 0; i < n;i++){
47
        // 跳过非根节点
48
        if(Find(Find, i) != i) continue;
49

50
        // 计算该连通块内不同字符串排列的数量
51
        ans = ans * f[sz[i]] % mod;
52
        for(int c = 0; c < 26;c++){
53
            ans = ans * inverse_f[freq[i][c]] % mod;
54
            // 重复字符可以在不改变字符串的情况下改变置换奇偶性
55
            if(freq[i][c] >= 2) repeat = true;
56
        }
57
    }
58

59
    // 没有重复字符时，只有一半的排列是偶置换
60
    if(!repeat) cout << ans * ((mod + 1) / 2) % mod << endl;
61
    else cout << ans << endl;
62
}

G - ΣШX#

利用恒等式 $mex(B)=\sum_{x\geq 0}[0,1,\ldots,x\text{均在}B\text{中出现}]$ ，可以把答案转化为：依次枚举 $x=0,1,\ldots$ ，统计同时包含 $0$ 到 $x$ 的子数组数量并累加。如果某个 $x$ 在原数组中没有出现，那么更大的 $x$ 也不会产生贡献，可以直接结束枚举。
使用从 $0$ 开始的下标。对于一个左端点 $l$ ，记 $next_x(l)$ 为位置 $l$ 及其右侧第一个值为 $x$ 的位置，不存在时记为 $N$ 。处理完 $0$ 到 $x$ 后，令 $f(l)=\max(l,next_0(l),next_1(l),\ldots,next_x(l))$ 。那么以 $l$ 为左端点的子数组要包含 $0$ 到 $x$ ，右端点至少需要到达 $f(l)$ ，合法右端点数量为 $N-f(l)$ 。
对于固定的 $x$ ，相邻两次出现位置之间的所有左端点拥有相同的 $next_x(l)$ 。因此预处理每个值的出现位置后，可以对每一段左端点区间执行 $f(l)\leftarrow\max(f(l),next_x(l))$ ，问题就转化为了若干次区间 $chmax$ 以及维护全局 $\sum f(l)$ 。
代码使用 $map$ 保存 $f$ 的极长连续段，每个键 $[l,r)$ 表示这一段上的函数值相同。更新 $[l,r)$ 前先用 $split$ 切出左右边界，再删除其中所有小于新值的连续段并合并，同时维护各段长度乘函数值的总和 $sum$ 。由于 $f(l)$ 单调不降，需要修改的部分一定是更新区间的一个前缀。
额外加入 $l=N$ 的哨兵并令 $f(N)=N$ 后，当前同时包含 $0$ 到 $x$ 的子数组数量可以写成 $N(N+1)-sum$ 。每个出现位置只会产生常数次区间切分，旧区间被删除后不会再次出现，因此总时间复杂度为 $O(NlogN)$ ，空间复杂度为 $O(N)$ 。

1
void solve(){
2
    int n; cin >> n;
3
    vector<vector<int>> pos(n + 1);
4
    for(int i = 0, x; i < n; i++) cin >> x, pos[x].push_back(i);
5

6
    map<pii, int> mp;
7
    ll sum = 0, ans = 0;
8
    for(int i = 0; i <= n; i++) mp[{i, i + 1}] = i, sum += i;
9

10
    auto split = [&](int x){
11
        auto it = prev(mp.upper_bound({x, INT_MAX}));
12
        auto [l, r] = it->first;
13
        int val = it->second;
14
        if(x == l || x == r) return;
15
        mp.erase(it);
16
        mp[{l, x}] = mp[{x, r}] = val;
17
    };
18

19
    for(int x = 0; x < n && !pos[x].empty(); x++){
20
        pos[x].push_back(n);
21
        for(int i = 0; i < (int)pos[x].size(); i++){
22
            int l = (i ? pos[x][i - 1] + 1 : 0);
23
            int r = pos[x][i] + 1, val = pos[x][i], end = l;
24
            split(l), split(r);
25

26
            auto it = mp.lower_bound({l, -1});
27
            while(it != mp.end() && it->first.first < r && it->second < val){
28
                sum -= 1LL * (it->first.second - it->first.first) * it->second;
29
                end = it->first.second;
30
                it = mp.erase(it);
31
            }
32
            if(l < end){
33
                mp[{l, end}] = val;
34
                sum += 1LL * (end - l) * val;
35
            }
36
        }
37
        ans += 1LL * n * (n + 1) - sum;
38
    }
39
    cout << ans << '\n';
40
}

模板：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
using ull = unsigned long long;
6
#define mod 998244353
7
typedef pair<int, int> pii;
8
typedef pair<ll, ll> pll;
9

10
ll fast_pow(ll a, ll b, ll MOD){
11
    ll ans = 1;
12
    while(b){
13
        if(b & 1) ans = (ans * a) % MOD;
14
        b >>= 1;
15
        a = (a * a) % MOD;
16
    }
17
    return ans;
18
}
19

20
vector<ll> get_inverse(ll n, ll MOD){
21
    vector<ll> inverse(n + 1, 0);
22
    inverse[1] = 1;
23
    for(int i = 2; i <= n;i++){
24
        inverse[i] = MOD - (MOD / i) * inverse[MOD % i] % MOD;
25
    }
26
    return inverse;
27
}
28

29
void solve(){
30
}
31

32
int main(){
33
    ios::sync_with_stdio(false),
34
    cin.tie(nullptr), cout.tie(nullptr);
35
    int _ = 1;
36
    //cin >> _;
37
    while(_--){
38
        solve();
39
    }
40
    return 0;
41
}

Mkrari的个人博客