Codeforces Round 942 (Div. 1) Solution

发表于 更新于 分类于 阅读次数： 本文字数： 3.7k 阅读时长 ≈ 14 分钟

菜狗的第二场 Div.1，感觉晚上临时开窍了，能上橙名。

场上做出了 A ~ C，同时 D 的解法已经想出来了，碍于码力没有写完。

后续的题稍微看下，不一定会 / 能补了。

A. Permutation Counting

简要翻译

有一副牌，点数为 \([1, n]\)，有 \(a_i\) 张点数为 \(i\) 的牌。

同时可以购买任意点数的牌，购买的数量之和不超过 \(k\)。

买完之后将牌按某种顺序排列，定义序列的分数为是 \([n]\) 的排列的子区间个数。

求序列分数的最大值。

思路解析

先思考如何在牌的数量固定的情况下排出最多的 \([n]\) 的排列 \(c\)。

对于两个子区间 \([i, i + n - 1]\) 和 \([i + 1, i + n]\)，它们如果都是 \([n]\) 的排列，那么一定有 \(c_i = c_{i + n}\)。

所以一旦确定 \(c\) 的前 \(n\) 个数，\(c_{i + n}\) 总是可以由 \(c_i\) 确定，整个序列的答案就固定了。

考虑一下所有牌数量都一样的时候的答案。

假设 \(a_1 = a_2 = \cdots = a_n = t\)，那么序列总长为 \(t \times n\)。

除去不能作为合法区间右端点的 \(n - 1\) 个值，答案为 \(t \times n - n + 1\)。

对于 \(a_i\) 不相等的情况，容易想到应该让 \(a_i\) 大的 \(i\) 出现在序列的前面，这样向后延伸时先使用大的 \(a_i\)，答案显然会更大。

这启发我们将 \(a_i\) 从大到小排序，然后从后往前分配我们可以购买的牌。

假设目前还能购买 \(k\) 张牌，\(a_i - a_{i + 1} = \delta\)。

如果 \(\delta \times (n - i) \leq k\)，说明第 \(i + 1 \sim n\) 的位置都可以补足 \(a_i\) 张牌，直接在 \(k\) 中减掉即可。

否则，说明最终序列中不能完整地出现 \(a_{i}\) 个 \([n]\) 的排列，这个时候就可以直接计算：

记 \(\delta^\prime = \lfloor \frac{k}{n - i} \rfloor, k^\prime = k - (n - i)\delta^\prime\)。

答案的第一部分，是 \(a_{i + 1} + \delta^\prime\) 个完整 \([n]\) 的排列，这里的答案是 \((a_{i + 1} + \delta^\prime) \times n - n + 1\)。

第二部分，是接下来还能在第一部分的序列后面接上 \(i + k^\prime\) 张牌，每一张都能形成一个新的合法子区间，答案为 \(i + k^\prime\)。

两部分的和就是答案。

如果遍历完后还没有触发直接计算，说明所有的数字都可以补足为 \(a_1\)，这是我们按所有牌数量一样的情况计算，答案为 \(a_{1} \times n - n + 1 + m\)。

代码

Code

 
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
#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char& op){return op >= '0' && op <= '9';}
    inline bool isalpha(const char& op){return op >= 'a' && op <= 'z';}
    inline bool iscapitcal(const char& op){return op >= 'A' && op <= 'Z';}
    inline bool isletter(const char& op){return isalpha(op) || iscapitcal(op);}
    inline bool ischr(const char& op){return isletter(op);}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len; static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc()) s[len++] = op;
        return len;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
ll a[N], n, m;
void solve(){
    n = read(); m = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + n + 1, [](ll x, ll y){return x > y;});
    ll ans = 0;
    ll i = n - 1;
    for(; i; i--){
        if((a[i] - a[i + 1]) * (n - i) <= m){
            m -= (a[i] - a[i + 1]) * (n - i);
            continue;
        }
        else{
            ll delta = m / (n - i);
            m -= delta * (n - i);
            ans = (n * (a[i + 1] + delta) - n + 1ll) + i + m;
            m = 0;
            break;
        }
    }
    if(i == 0){
        ans = n * a[1] - n + 1ll + m;
    }
    printf("%lld\n", ans);
}
signed main(int argc, char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

B1. Reverse Card (Easy Version)

简要翻译

给定两个上界 \(n, m\)，求满足 \(a \in [1, n], b \in [1, m]\)，且 \(b \operatorname{gcd}(a, b) | (a + b)\) 的数对数量。

思路解析

可以设 \(g = \gcd(a, b), a = xg, b = yg\)，应有 \(\gcd(x, y) = 1\)。

上式则变换为 \(yg^2 | (x + y) g\)。进一步有 \((x + y) = kgy, x = (kg - 1)y, k \in \mathrm{N}_{+}\)。

这说明 \(\gcd(x, y) = y\)。想到 \(y = 1\) 可以推出 \(b = g\)，相当于求 \(a = (kg - 1)g\) 的 \((a, g)\) 对数。

\[ a = (kg - 1)g \leq n \Rightarrow k \le \frac{\frac{n}{g} + 1}{g} \]

因为 \(g \leq n, m \leq 2 \cdot 10^6\)，所以枚举 \(g\) 计算即可。

复杂度 \(\Theta(\sum n)\)。

代码

Code

 
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
#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char& op){return op >= '0' && op <= '9';}
    inline bool isalpha(const char& op){return op >= 'a' && op <= 'z';}
    inline bool iscapitcal(const char& op){return op >= 'A' && op <= 'Z';}
    inline bool isletter(const char& op){return isalpha(op) || iscapitcal(op);}
    inline bool ischr(const char& op){return isletter(op);}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len; static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc()) s[len++] = op;
        return len;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
ll n, m;
void solve(){
    ll ans = 0;
    n = read(); m = read();
    for(ll g = 1; g <= min(n, m); ++g){// gcd(a, b) == b
        ans += ((n / g) + 1ll) / g;
        if(g == 1) ans--;// kg - 1 > 0
    }
    printf("%lld\n", ans);
}
signed main(int argc,char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

B2. Reverse Card (Hard Version)

简要翻译

和上题几乎一样，区别在于整除的两侧交换了，即 \((a + b) | b \operatorname{gcd}(a, b)\)

范围也是一样的。

思路解析

这题就没有那么好的性质了。不过仍然可以设 \(g = \gcd(a, b), a = xg, b = yg\)，应有 $ (x, y) = 1$。

化简后的式子变成 \(yg = k (x + y), k \in \mathrm{N}_{+}\)。

因为 \(x, y\) 互质，所以 \((x + y)\) 与 \(x, y\) 均互质。

整除关系必须成立，所以 \(g = k^\prime (x + y)\)。

对于一个数对 \((x, y)\)，\(a = k^\prime (x + y) x \leq n, b = k^\prime (x + y) y \leq m\)。

所以有 \(k^\prime \leq \frac{n}{(x + y) x}, k^\prime \leq \frac{m}{(x+y) y}\)。

乍一看，枚举 \(x, y\) 复杂度会爆炸。

这个时候犯难了，以为正解是莫比乌斯反演或者欧拉函数性质之类的。

手搓一下有贡献的数对，发现有用的部分 \(x^2 \leq (x + y)x \leq n\)，所以枚举上界可以压缩。

复杂度 \(\Theta(\sum \sqrt{nm})\)。

代码

Code

 
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
#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char& op){return op >= '0' && op <= '9';}
    inline bool isalpha(const char& op){return op >= 'a' && op <= 'z';}
    inline bool iscapitcal(const char& op){return op >= 'A' && op <= 'Z';}
    inline bool isletter(const char& op){return isalpha(op) || iscapitcal(op);}
    inline bool ischr(const char& op){return isletter(op);}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len; static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc()) s[len++] = op;
        return len;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010;
ll n, m;
void solve(){
    n = read(); m = read();
    ll ans = 0;
    for(ll p = 1; p * p <= n; ++p)
    for(ll q = 1; q * q <= m; ++q)
    if(__gcd(p, q) == 1)
        ans += min(n / ((p + q) * p), m / ((p + q) * q));
    printf("%lld\n", ans);
}
signed main(int argc,char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}

C. Fenwick Tree

简要翻译

对于一个数列 \(A\)，我们定义一个函数 \(f(A)\)，它得到一个新数列 \(B\)。

\(B\) 满足 \(b_k=\left( \sum\limits_{i = k - \operatorname{lowbit}(k) + 1}^{k} a_i \right) \bmod 998\,244\,353\)，其实就是对 \(A\) 求一次树状数组得到的数组。

现在定义 \(f^k(A) = f(f^{k - 1}(A))\)，并给定 \(B = f^k(A)\) 和 \(k\)，构造一个可能的 \(A\)。

思路解析

手玩一下样例和几组小数据，可以发现两个性质：

  1. 奇数位置的值永远不变。
  2. 整个序列可以按递减的 \(2\) 的整次幂的长度划分，就像树状数组一样。

这启发我们计算每个数 \(a_i\) 对于另一个位置 \(b_j\) 的贡献。

定义 \(\operatorname{step}(x, 1) = x + \operatorname{lowbit}(x), \operatorname{step}(x, s) = \operatorname{step}(\operatorname{step}(x, s - 1), 1)\)。

抽象到树状数组中，\(\operatorname{step}(x, s)\) 就是 \(x\) 向上跳 \(s\) 步到达的节点。

那么 \(a_x\) 有贡献的点只能是 \(\operatorname{step}(x, s), s \in N_{+}\)。

只考虑 \(x\) 对 \(y\) 的贡献的话，不妨设一个新数组 \(s_{k, s}\) 表示求 \(k\) 次树状数组后 \(x\) 对 \(\operatorname{step}(x, s)\) 的贡献。

边界条件有 \(s_0 = \left\{1, 0, 0, \ldots \right\}\)，下标从 0 开始。

因为再做一次树状数组，\(\operatorname{step}(x, s)\) 的位置上一定包含 \(\operatorname{step}(x, 0), \operatorname{step}(x, 1), \operatorname{step}(x, 2) \ldots\) 中 \(a_x\) 的贡献，所以 \(s_{k,i} = \sum\limits_{j = 1}^{i} s_{k - 1, j}\)。

这时可以发现，\(s_k\) 与 \(x\) 无关，实际上就是数列 \(s_0\) 的 \(k\) 次前缀和。

经过计算推理可以得出 \(s_{k,s} = \binom{k + s - 1}{s}\)。

这里 \(k\) 很大但 \(s\) 很小，Round 926 Div.2 F# 的暴力思路又涌上心头。

同时 \(0 \le s \le \log(N)\)，所以对于每个 \(x\) 直接枚举 \(\operatorname{step}(x, s)\) 去除 \(x\) 的贡献即可。

复杂度 \(\Theta(N \log^2 N)\)，单次计算组合数的时间为 \(\Theta(\log N)\)。

代码

Code

 
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
#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char& op){return op >= '0' && op <= '9';}
    inline bool isalpha(const char& op){return op >= 'a' && op <= 'z';}
    inline bool iscapitcal(const char& op){return op >= 'A' && op <= 'Z';}
    inline bool isletter(const char& op){return isalpha(op) || iscapitcal(op);}
    inline bool ischr(const char& op){return isletter(op);}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len; static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc()) s[len++] = op;
        return len;
    }
}
using namespace std;
using Input::read;
typedef long long ll;
const int N = 300010, lgN = 40;
const ll mod = 998244353;

ll invfac[N];
void prework(){
    invfac[0] = invfac[1] = 1;
    for(int i = 2; i < lgN; ++i)
        invfac[i] = (mod - mod / i) * invfac[mod % i] % mod;
    for(int i = 2; i < lgN; ++i)
        invfac[i] = invfac[i] * invfac[i - 1] % mod;
}
ll binom(ll n, ll m){// small m
    ll ans = 1;
    for(ll i = n; i >= n - m + 1ll; i--)
        ans = ans * i % mod;
    return ans * invfac[m] % mod;
}
// suppose there's a sequence s = [1, 0, 0, ...] (indexed from 0)
// C(k + j - 1, j) is the j-th item of k time's suffix sequence of s
ll b[N], a[N];
int n, k;
void solve(){
    n = read(); k = read();
    for(int i = 1; i <= n; ++i)
        b[i] = (read() % mod + mod) % mod;
    for(int i = 1; i <= n; ++i){
        a[i] = b[i];
        for(int x = i, s = 0; x <= n; x += x & -x, s++)
            b[x] = (b[x] + mod - a[i] * binom(k + s - 1, s) % mod) % mod;
    }
    for(int i = 1; i <= n; ++i)
        printf("%lld ", a[i]);
    putchar('\n');
}
signed main(int argc, char **argv){
    prework();
    int T = read();
    while(T--)
        solve();
    return 0;
}

D. Long Way to be Non-decreasing

简要翻译

有一个序列 \(a_1, a_2, \ldots, a_n\)，值域为 \([1, m]\)。

同时规定一组变换 \(b_1, b_2, \ldots, b_m\)，值域同样为 \([1, m]\)。

你可以执行若干次操作，每次选中一个 \([n]\) 的子集 \(S\)， 对于所有的 \(x \in S\)，将第 \(x\) 个位置上的数从 \(a_x\) 修改为 \(b_{a_x}\)。

求出最少的操作次数，可以使 \(a\) 成为不下降的序列。不可能则输出 -1。

思路解析

看到了将 \(v\) 修改为 \(b_v\)，其实可以联想到建图。

对每个 \(i\) 连一条 \(i \rightarrow b_i\) 的边，对于一个点 \(a_x\) 的操作就转化成在图上走一步。

\(m\) 个点 \(m\) 条边，这张图是一个基环树森林（内向树森林）。

那么 \(a_i\) 就能抽象为一个人 \(P_i\) 初始在编号为 \(a_i\) 的点上。

然后也可以发现 \(a_i\) 之间在操作上是相互独立的，而最后需要满足一个不下降的性质。

求这个步数可以考虑二分答案，转化为 \(lim\) 步之内能不能让所有的 \(a_i\) 走到一个编号不降的状态。

先考虑 \(P_n\)。我们应该让他走到编号最大的点。

那么最大的点编号为 \(m\)，判断 \(a_n\) 到 \(m\) 的距离 \(d\) 有没有 \(d \leq lim\) 即可。

如果没有，说明 \(P_n\) 不能走到 \(m\)，又因为我们要保持序列的单调性，其他 \(P_i\) 也不需要考虑 \(m\) 了。

这时转而考虑 \(m - 1\) 即可。一旦有一个 \(P_i\) 不能安排到任何位置，说明 \(lim\) 步不能形成单调不降的序列 \(a\)。

这里用一个双指针实现比较简单。

至于判断可能性，可以适当提高二分的上界，如果最后落在上界则说明多少步都不可能形成单调的序列。

实现难点在于计算基环树上两点距离。时间复杂度 \(\Theta((N + M)\log M)\)。

代码

Code

 
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
#include <algorithm>
#include <cstdio>
#include <vector>
namespace Input{
    const int BUFFLEN = 1 << 20;
    char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
    inline char getc(){
        if(p1 == p2)
            p1 = buf,
            p2 = buf + fread(buf, 1, BUFFLEN, stdin);
        return p1 == p2? EOF: *p1++;
    }
    inline bool isdgt(const char& op){return op >= '0' && op <= '9';}
    inline bool isalpha(const char& op){return op >= 'a' && op <= 'z';}
    inline bool iscapitcal(const char& op){return op >= 'A' && op <= 'Z';}
    inline bool isletter(const char& op){return isalpha(op) || iscapitcal(op);}
    inline bool ischr(const char& op){return isletter(op);}
    long long read(){
        static long long res; static char op, f;
        for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
        for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
        return f? -res: res;
    }
    int readstr(char *s){
        static int len; static char op;
        do op = getc(); while(!ischr(op));
        for(len = 0; ischr(op); op = getc()) s[len++] = op;
        return len;
    }
}
using Input::read;
typedef long long ll;
const int N = 1000010;
const int inf = 0x3f3f3f3f;

std::vector<int> ver[N];
int fa[N], deg[N];
int q[N], pos[N], bel[N], siz[N], belcnt;
int dep[N], anc[N], dfnl[N], dfnr[N], dfncnt;
bool incir[N];
int a[N], n, m;

void dfs(const int& x){
    dfnl[x] = ++dfncnt;
    for(int y : ver[x])
    if(!incir[y]){
        dep[y] = dep[x] + 1;
        anc[y] = anc[x]; bel[y] = bel[x];
        dfs(y);
    }
    dfnr[x] = dfncnt;
}
inline bool ischd(const int& x, const int& y){// x is child of y
    return dfnl[y] <= dfnl[x] && dfnl[x] <= dfnr[y];
}
ll dist(const int& x, const int& y){
    if(bel[x] != bel[y]) return inf;
    if(ischd(x, y)) return dep[x] - dep[y];
    if(ischd(y, x)) return inf;
    if(!incir[y]) return inf;
    return dep[x] + (pos[y] + siz[bel[x]] - pos[anc[x]]) % siz[bel[x]];
}
bool chk(const int& lim){
    int i = m, j = n;
    while(j){
        while(i && dist(a[j], i) > lim) i--;
        if(!i) return false;
        j--;
    }
    return true;
}
inline void clear(){
    for(int i = 1; i <= m; ++i)
        deg[i] = 0, incir[i] = 0,
        bel[i] = 0, siz[i] = 0,
        ver[i].clear();
    dfncnt = 0;
}
inline void findcir(){
    int ql = 0, qr = 0;
    for(int i = 1; i <= m; ++i)
    if(!deg[i]) q[++qr] = i;
    while(ql < qr){
        int x = q[++ql];
        if(!--deg[fa[x]]) q[++qr] = fa[x];
    }
    for(int i = 1; i <= m; ++i)
        incir[i] = deg[i];
}
void solve(){
    n = read(); m = read();
    clear();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= m; ++i){
        fa[i] = read();
        ver[fa[i]].emplace_back(i);
        deg[fa[i]]++;
    }
    findcir();
    for(int i = 1, cnt = 0; i <= m; ++i)
    if(deg[i]){
        belcnt++;
        cnt = 0;
        for(int x = i; deg[x]; x = fa[x]){
            deg[x] = 0; dep[x] = 0; anc[x] = x;
            bel[x] = belcnt; ++siz[belcnt];
            pos[x] = ++cnt;
            dfs(x);
        }
    }
    if(!chk(m + 1)){
        puts("-1");
        return;
    }
    int l = 0, r = m, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(chk(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
}
signed main(int argc, char **argv){
    int T = read();
    while(T--) solve();
    return 0;
}