小花生

study & life record.

牛客寒假训练营2025

发表于 分类于 ，

6 场比赛的补题都放在这里吧。

训练一

解题数 8 -> 11 / 13。

C. 兢兢业业之移

对每一个待填充 1 的位置做一次 bfs 求最近的 1 并移入。

可以证明，每次移动步数不超过 $n$，而待移入的个数为 $n^2/4$，可以看出总步数不超过 $n^3/4$。

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>
#define int long long
using namespace std;
typedef pair<int, int> PII;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void solve(){
    int n; cin >> n;
    vector<string>v(n);
    vector<vector<int>>ok(n, vector<int>(n, 0));
    vector<vector<int>>res;
    for(int i = 0; i < n; i++) cin >> v[i];

    auto bfs = [&](PII s){
        auto vis = ok;
        queue<PII>Q;

        Q.emplace(s);
        vis[s.first][s.second] = 1;

        PII d;
        while(!Q.empty()){
        	auto [x, y] = Q.front();
        	Q.pop();

        	if(v[x][y] == '1'){
        		d = {x, y};
        		break;
        	}

        	for(int i = 0; i < 4; i++){
        		int xx = x + dx[i];
        		int yy = y + dy[i];


        		if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
        		if(vis[xx][yy]) continue;

        		Q.emplace(xx, yy);
        		vis[xx][yy] = vis[x][y] + 1;
        	}
        }

        v[s.first][s.second] = '1';
        v[d.first][d.second] = '0';

        while(d != s){
        	for(int i = 0; i < 4; i++){
        		int xx = d.first + dx[i];
        		int yy = d.second + dy[i];
        		if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
        		if(vis[xx][yy] == vis[d.first][d.second] - 1){
        			res.emplace_back(vector<int>{d.first, d.second, xx, yy});
                	d = {xx, yy};
        			break;
        		}
        	}
        }
    };

    for(int i = 0; i < n / 2; i++){
        for(int j = 0; j < n / 2; j++){
            if(v[i][j] == '0'){
                PII s = {i, j};
                bfs(s);
            }
            ok[i][j] = 500;
        }
    }

    cout << res.size() << '\n';
    for(auto &ex : res){
        for(auto &i : ex){
            cout << i + 1 << ' ';
        }
        cout << '\n';
    }
    
}

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

F. 双生双宿之探

双指针，每次找出“极长的双元素数组”。

再在每个“极长的双元素数组”内部找寻双生数组，即求两元素个数相同的子数组数。

将其中一种元素置 1，另一种元素置 -1，则和为 0 时满足两元素个数相同。

利用前缀和维护，前缀和相同则对应某段上和为 0，vis 记录出现过的前缀和即可。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    
    int res = 0, cnt = 0;

    auto deal = [&](int l, int r){
        vector<int>a(r - l + 2);
        unordered_map<int, int>vis;
        vis[0]++;
        for(int i = l; i <= r; i++){
            if(v[i] == v[l]){
                a[i - l + 1] = a[i - l] + 1;
            }
            else{
                a[i - l + 1] = a[i - l] - 1;
            }
            res += vis[a[i - l + 1]];
            vis[a[i - l + 1]]++;
        }
    };

    unordered_map<int, int>mp;
    for(int i = 0, j = 0; ; j++){
        while(cnt <= 2){
            if(!mp[v[j]]){
                if(cnt == 2){
                    j--;
                    break;
                }
                else{
                    cnt++;
                    mp[v[j]]++;
                }
            }
            else{
                mp[v[j]]++;
            }
            if(j == n - 1) break;
            j++;
        }

        deal(i, j);
        if(j == n - 1) break;

        while(cnt == 2){
            mp[v[i]]--;
            if(!mp[v[i]]){
                cnt--;
                i++;
                break;
            }
            i++;
        }
    }
    cout << res << '\n';
}

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

K. 硝基甲苯之魇

遍历左端点 l，对每个 l：不难发现，以 l 为左端点的区间，其 gcd 种数不超过log (a[l])。

这样，以 [l, r] 上整体 gcd 为区分 ，将 r 分块，保证同一分块中，[l, r] 的整体 gcd 相同。

在此分块上，记区间 gcd 为 G，前缀异或和序列为 b ，则需要计数满足 G = b[r] ^ b[l - 1] 的个数。

这等价于 b[r] = G ^ b[l - 1]，这样，只需要维护一个 map ，用前缀异或和映射至所有下标，每次查询计数时，直接用左右下标在序列内二分即可。

总体复杂度 $O(nlog^2n)$。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

struct ST{
    vector<vector<int>>st;
    vector<int>log;

    ST(vector<int>v){
        int n = v.size();
        int max_log = log2(n) + 1;
        
        log.resize(n + 1);
        for(int i = 2; i <= n; i++){
            log[i] = log[i >> 1] + 1;
        }

        st.resize(n, vector<int>(max_log));
        for(int i = 0; i < n; i++){
            st[i][0] = v[i];
        }
        for(int j = 1; (1 << j) <= n; j++){
            for(int i = 0; i + (1 << j) - 1 < n; i++){
                st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query(int l, int r){
        int k = log[r - l + 1];
        return gcd(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

void solve(){
    int n; cin >> n;
    vector<int>a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    ST st(a);
    unordered_map<int, vector<int>> mp;
    mp[0].emplace_back(0);
    vector<int> b = a;
    for(int i = 1; i <= n; i++){
        b[i] ^= b[i - 1];
        mp[b[i]].emplace_back(i);
    }

    int res = 0;
    for(int i = 1; i <= n; i++){
        int j = i - 1, G;
        do{
            G = st.query(i, j + 1);
            int l = j, r = n + 1;
            while(l + 1 != r){
                int mid = l + r >> 1;
                if(st.query(i, mid) == G) l = mid;
                else r = mid;
            }

            auto &v = mp[G ^ b[i - 1]];
            res += upper_bound(v.begin(), v.end(), l) 
                 - lower_bound(v.begin(), v.end(), max(i + 1, j + 1));
            j = l;
        }while(j != n);
    }

    cout << res << '\n';
}

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

训练二

解题数 9 -> 11 / 13。

C. 字符串外串

是难想的构造题。

构造方法直接看代码，容易发现，这样构造恰有 m 个可爱度。

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>
#define int long long
using namespace std;

void solve(){
    int n, m; cin >> n >> m;
    if(m < n - 26 || m > n - 1){
        cout << "NO" << '\n';
        return;
    }
    cout << "YES" << '\n';

    int run = 0;
    for(int i = 0; i < n; i++){
        if(i == n - m){
            run = 0;
        }
        cout << char('a' + run++ % 26);
    }
    cout << '\n';
}

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

M. 那是我们的影子

感觉很简单，但是赛时榜歪了压根没看这题。

三种不合法情况：

  • %3 的列中出现超过三种数字
  • 同一列有相同数字
  • 一个数在不同的 %3 列中

排除后肯定有解，计算答案：

假设 %3 列中空缺数分别为 x，y，z，则将未出现数字分配给 %3 列的方式有$\dfrac{(x+y+z)!}{x!\ y!\ z!}$种。

然后各列内部分配，总分配方式有 $\sum\limits_{j=1}^{n}A_{q_j}^{q_j}$，其中 $q_j$ 表示第 $j$ 列的问号数。

因此 $res = \dfrac{(x+y+z)!}{x!\ y!\ z!} \times \sum\limits_{j=1}^{n}A_{q_j}^{q_j}$ 即可。

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>
#define int long long
using namespace std;

constexpr int mod = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector<string>a(3);
    for(int i = 0; i < 3; i++) cin >> a[i];

    vector<set<int>>st(3);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < n; j++){
            if(a[i][j] == '?') continue;
            st[j % 3].emplace(a[i][j] - '0');
        }
    }
    for(int i = 0; i < 3; i++){
        if(st[i].size() > 3){
            cout << 0 << '\n';
            return;
        }
    }
    for(int j = 0; j < n; j++){
        for(int i = 0; i < 3; i++){
            if(a[i][j] == '?') continue;
            for(int k = i + 1; k < 3; k++){
                if(a[i][j] == a[k][j]){
                    cout << 0 << '\n';
                    return;
                }
            }
        }
    }
    set<int>all;
    for(int i = 0; i < 3; i++){
        for(auto &j : st[i]){
            all.emplace(j);
        }
    }
    if(all.size() != st[0].size() + st[1].size() + st[2].size()){
        cout << 0 << '\n';
        return;
    }

    vector<int>fact(10, 1);
    for(int i = 2; i < 10; i++) fact[i] = fact[i - 1] * i;

    int x = 3 - st[0].size(), y = 3 - st[1].size(), z = 3 - st[2].size();
    int res = fact[x + y + z] / fact[x] / fact[y] / fact[z];

    for(int j = 0; j < n; j++){
        int cnt = 0;
        for(int i = 0; i < 3; i++){
            if(a[i][j] == '?') cnt++;
        }
        if(cnt == 2) res *= 2;
        if(cnt == 3) res *= 6;
        res %= mod;
    }

    cout << res << '\n';
    
}

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

训练三

解题数 6 -> 11 / 13。

G. 智乃与模数

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, k; cin >> n >> k;
    
    auto check = [&](int mid) -> bool{
        int cnt = 0;
        for(int l = 1, r; l <= n; l = r + 1){
            r = n / (n / l);
            int a = n % r;
            int d = n / l;
            cnt += max(0ll, r - l - (mid - a + d - 1) / d + 1);
        }
        return cnt > k;
    };

    int L = -1, R = n + 1;
    while(L + 1 != R){
        int mid = L + R >> 1;
        if(check(mid)) L = mid;
        else R = mid;
    }
    
    int res = 0, cnt = 0;
    for(int l = 1, r; l <= n; l = r + 1){
        r = n / (n / l);
        int a = n % r;
        int d = n / l;
        int nmin = (L - a + d - 1) / d;
        int al = a + nmin * d;
        int ar = a + (r - l) * d;
        int t = r - l - nmin + 1;
        if(t <= 0) continue;
        res += (al + ar) * t / 2;
        cnt += t;
    }
    res -= (cnt - k) * L;
    cout << res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

K. 智乃的逆序数

先使其整体上完全逆序，这样得到的一定是最大的逆序数，记为 Km。

若 Km < k 则一定无解。

接下来进行冒泡排序，每交换一次，会导致逆序数 Km--，注意要跳过交换元素来自同一子序列的所有交换。

直到 Km == k 时，结束冒泡排序，输出序列。

如果直到冒泡排序结束，都没能达到 Km == k，无解。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, k; cin >> n >> k;
    vector<vector<int>>all(n);
    unordered_map<int, int>mp;
    for(int i = 0; i < n; i++){
        int l; cin >> l;
        for(int j = 0; j < l; j++){    	
            int x; cin >> x;	
               mp[x] = i;
        	all[i].emplace_back(x);
        }
    }
    sort(all.begin(), all.end());
    vector<int>a;
    for(int i = n - 1; i >= 0; i--){
        for(auto &u : all[i]){
            a.emplace_back(u);
        }
    }

    int len = a.size();
    
    int Km = 0;
    for(int i = 0; i < len; i++){
        for(int j = i; j < len; j++){
            if(a[i] > a[j]) Km ++;
        }
    }

    if(k > Km){
        cout << "No" << '\n';
        return;
    }
    
    if(Km == k){    
        cout << "Yes" << '\n';
        for(auto &u : a){ 
            cout << u << ' ';
        }
        return;
    }

    for(int i = 0; i < len - 1; i++){
        for(int j = 0; j < len - i - 1; j++){
            if(mp[a[j]] == mp[a[j + 1]]) continue;
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]);
                Km--;
            }
            if(Km == k){    
                cout << "Yes" << '\n';
                for(auto &u : a){ 
                    cout << u << ' ';
                }
                return;
            }
        }
    }
    cout << "No" << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

D. 智乃的Notepad(Hard version)

不难发现，敲键盘的总次数为：由 [l, r] 上的字符串构建的 Trie 树上节点数 * 2 减去 [l, r] 上最长串的长度。

对这个问题，考虑离线查询，然后从左往右建立 Trie 树，在加入第 r 个串时，处理所有的 [l, r] 的查询。

考虑每个串此时对节点数的贡献，为 Trie 树上每一个节点确定一个“父串”，则每个串的贡献为其拥有的“子节点”，总节点数为所有串的贡献之和。

在加入新串时，将其所有字符的“父串”更新为该新串。这样做的可行性在于，查询总贡献时，如果前串被查询到，那么后串一定也在查询区间之内。

用 树状数组/线段树 维护每个串的当前贡献，用 ST表/线段树 维护区间最长串长度即可。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
constexpr int N = 1e6 + 5;

struct FenwickTree{
    int n;
    vector<int>bit;
    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void update(int p, int v){
        while(p <= n){
            bit[p] += v;
            p += p & (-p);
        }
    }

    int query(int p){
        int sum = 0;
        while(p > 0){
            sum += bit[p];
            p -= p & (-p);
        }
        return sum;
    }
};

struct ST{
    vector<vector<int>>st;
    vector<int>log;

    ST(vector<int>v){
        int n = v.size();
        int max_log = log2(n) + 1;

        log.resize(n + 1);
        for(int i = 2; i <= n; i++){
            log[i] = log[i >> 1] + 1;
        }

        st.resize(n, vector<int>(max_log));
        for(int i = 0; i < n; i++){
            st[i][0] = v[i];
        }
        for(int j = 1; (1 << j) <= n; j++){
            for(int i = 0; i + (1 << j) - 1 < n; i++){
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query(int l, int r){
        int len = r - l + 1;
        int k = log[len];
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

void solve(){
    int n, m; cin >> n >> m;
    vector<string>s(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }
    vector<vector<PII>>q(N);
    for(int i = 0; i < m; i++){
        int l, r; cin >> l >> r;
        q[r].emplace_back(l, i);
    }
    
    vector<int>siz(n + 1);
    for(int i = 1; i <= n; i++){
        siz[i] = s[i].size();
    }
    ST st(siz);

    int idx = 0;
    vector<array<int, 26>>adj(N);
    vector<int>fa(N);
    FenwickTree bit(N);
    vector<int>res(m);
    
    for(int i = 1; i <= n; i++){
        int p = 0;
        bit.update(i, s[i].size());
        for(auto &u : s[i]){
            int x = u - 'a';
        	if(!adj[p][x]){
                p = adj[p][x] = ++idx;
                fa[idx] = i;
            }
            else{
                p = adj[p][x];
                bit.update(fa[p], -1);
                fa[p] = i;
            }
        }
        for(auto &[l, id] : q[i]){
            res[id] = 2 * (idx - bit.query(l - 1)) - st.query(l, i);
        }
    }
    for(auto &u : res){
        cout << u << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

B. 智乃的质数手串

首先简化：考虑在一段链上处理这个问题。

不难发现，采用从前往后删的策略是最优的，因此维护一个单调栈，每次元素入栈时弹出与其结合为质数的栈顶。如此，如果能删完，最后应剩下唯一一个元素，也就是最后一个元素。

回到本题，我们要在一个环上处理该问题，其实只需要在长为 n 的环上找到一串长为 n 的链即可。采用如下策略：遍历该环两遍（这样就遍历完链的所有可能情况了），若在某段长为 n 的链上，栈中元素仅剩 1 个，那么就可以取出以该元素为链尾的链进行计算。

这样看，已经足够完成问题了，需要维护一个滑动窗口（双端队列）。出题人题解就是这么处理的。

但实际上有如下性质：如果在重复两次的链 [0, 2 * n - 1] 上存在这么一段链 [i - n + 1, i] 满足要求，那么 [0, i] 一定也满足要求。因为第 r 项元素如果能处理掉前面留下的所有元素，那么 r - 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
#include<bits/stdc++.h>
#define int long long
using namespace std;

struct Euler{
    vector<int>primes;
    vector<bool>comp;

    Euler(int n){
        comp.resize(n + 1);
        for(int i = 2; i <= n; i++){
            if(!comp[i]) primes.emplace_back(i);
            for(int j = 0; i * primes[j] <= n; j++){
                comp[i * primes[j]] = true;
                if(!(i % primes[j])) break;
            }
        }
    }
};

void solve(){
    int n; cin >> n;
    vector<int>v(n + n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        v[i + n] = v[i];
    }
    Euler sieve(2e5);

    auto print = [&](int l, int r){
        cout << "Yes" << '\n';
        vector<int>stk;
        for(int i = l; i <= r; i++){
            while(!stk.empty() && !sieve.comp[v[stk.back()] + v[i]]){
                cout << stk.back() % n << ' ';
                stk.pop_back();
            }
            stk.emplace_back(i);
        }
        cout << stk[0] % n << '\n';
    };

    vector<int>stk;
    for(int i = 0; i < n + n; i++){
        while(!stk.empty() && !sieve.comp[v[stk.back()] + v[i]]){
            stk.pop_back();
        }
        stk.emplace_back(i);
        if(i >= n - 1 && stk.size() == 1){
            print(i - n + 1, i);
            return;
        }
    }
    cout << "No" << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

I. 智乃的兔子跳

首先取 $k = 2$，发现能选中的数一定 $\geq\dfrac{n}{2}$ 个。

因此考虑一个随机数做法：数列中任取两个数，他们都在最优集合的概率 $p \geq 1/4$。

这样，随机 $T$ 次，成功率就达到了 $1-(1-p)^T$ 。

对选出的两个数，选择步长为两者之差的所有质因数（非质因数的因数不优）。

分析时间复杂度为 $O(T\cdot\sqrt X\cdot n)$ ，取 $T=100$，时间合适，且成功率达 99.99999999999..%

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
 
    int res = 0;
    int pp = 0, kk = 2;

    if(n == 1){
        cout << v[0] << ' ' << 2 << '\n';
        return;
    }

    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, n - 1);

    for(int t = 0; t < 100; t++){
        int i = dis(gen), j = dis(gen);
        if(i == j) continue;
        int d = abs(v[i] - v[j]);
        if(d == 1) continue;

        for(int k = 2; k * k <= d; k++){
            if(d % k == 0){
                while(d % k == 0) d /= k;
                int p = v[i] % k;
                int cnt = 0;
                for(auto &u : v){
                    if((u - p) % k == 0){
                        cnt++;
                    }
                }
                if(cnt > res){
                    res = cnt; 
                    pp = p, kk = k;
                }
            }
        }
        if(d != 1){
            int k = d;
            int p = v[i] % k;
            int cnt = 0;
            for(auto &u : v){
                if((u - p) % k == 0){
                    cnt++;
                }
            }
            if(cnt > res){
                res = cnt; 
                pp = p, kk = k;
            }
        }
    }
    cout << pp << ' ' << kk << '\n'; 
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

训练四

A. Tokitsukaze and Absolute Expectation

总期望可以拆分为每两个相邻差的绝对值的期望之和。(均在 mod m 意义下运算，除法以逆元实现)

相邻两数，记分为分别在 [l, r] 和 [x, y] 区间内，则差的绝对值的期望为：
$$
\frac{\sum\limits_{i=l}^r\sum\limits_{j=x}^y|i-j|}{(r-l+1)(y-x+1)}
$$
计算出该式子即可，以下先分为两种情况讨论：

  • $l\leq r<x\leq y$

$$
\sum\limits_{i=l}^r\sum\limits_{j=x}^y|i-j|=\sum\limits_{i=l}^r\sum\limits_{j=x}^y(j-i)
$$

两次求和直接得到表达式。

  • $x\leq l\leq r\leq y$

$$
\sum\limits_{i=l}^r\sum\limits_{j=x}^y|i-j|=\sum\limits_{i=l}^r(\frac{(i-x)(i-x+1)}{2}+\frac{(y-i)(y-i+1)}{2})\
=\sum\limits_{i=l}^r(i^2-(x+y)i+\frac{x(x-1)+y(y+1)}{2})
$$

求和得到表达式即可。（第一项利用$1^2+2^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}{6}$ 求和）

这样就讨论完了在外和在内的情况，其他情况均可转换为这两种情况。（见代码 dis 函数）

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
constexpr int mod = 1e9 + 7;

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

int inv(int x){
    return qmi(x, mod - 2, mod);
}

struct modint{
    int v;
    modint(int x) : v(((x % mod) + mod) % mod) {}

    modint operator + (const int &o){
        return modint(v + o);
    }
    modint operator - (const int &o){
        return modint(v - o);
    }
    modint operator * (const int &o){
        return modint(v * o);
    }
    modint operator / (const int &o){
        return modint(v * inv(o));
    }

    modint operator + (const modint &o){
        return modint(v + o.v);
    }
    modint operator - (const modint &o){
        return modint(v - o.v);
    }
    modint operator * (const modint &o){
        return modint(v * o.v);
    }
    modint operator / (const modint &o){
        return modint(v * inv(o.v));
    }
};
using Z = modint;

// 等差数列求和：S = na + n(n - 1)d / 2
Z arith(Z n, Z a, Z d) {
    return n * a + n * (n - 1) / 2 * d;
}

// 平方数列求和：S = n(n + 1)(2n + 1) / 6
Z square(Z n){
    return n * (n + 1) * (n * 2 + 1) / 6;
}

// 计算距离和
Z dis(Z l, Z r, Z x, Z y) {
    if (r.v < x.v) { // Case 1: [l, r] completely left of [x, y]
        return arith(r - l + 1, arith(y - x + 1, x - r, 1), y - x + 1);
    }
    if (l.v > y.v) { // Case 2: [l, r] completely right of [x, y]
        return dis(x, y, l, r);
    }
    if (x.v <= l.v && r.v <= y.v) { // Case 3: [l, r] completely inside [x, y]
        return square(r) - square(l - 1) - (x + y) * arith(r - l + 1, l, 1) + (y * (y + 1) + x * (x - 1)) / 2 * (r - l + 1);
    }
    if (l.v <= x.v && r.v >= y.v) { // Case 4: [l, r] fully covering [x, y]
        return dis(x, y, l, r);
    }
    if (l.v < x.v && r.v <= y.v) { // Case 5: [l, r] partially overlaps on the left
        return dis(l, x - 1, x, y) + dis(x, r, x, y);
    }
    if (x.v <= l.v && y.v < r.v) { // Case 6: [l, r] partially overlaps on the right
        return dis(x, y, l, r);
    }
    return 0; // Should never reach here
}

void solve(){
    int n; cin >> n;
    vector<PII>p(n);

    for(int i = 0; i < n; i++){
        int l, r; cin >> l >> r;
        p[i] = {l, r};
    }
    
    Z res = 0;
    for(int i = 1; i < n; i++){
        Z l = p[i - 1].first;
        Z r = p[i - 1].second;
        Z x = p[i].first;
        Z y = p[i].second;


        Z div = (r - l + 1) * (y - x + 1);

        res = res + dis(l, r, x, y) / div;
    }

       cout << res.v << '\n';
}

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