2025年夏季个人训练赛第十场

A. 分割数组#

又是我最喜欢的 dp， $f_{i, j}$ 表示前 i 个数分成 j 段的方案数

f_{i, j} = \sum_{\sum_{l=k}^{j - 1}a_l\ mod\ j = 0 \land k < j}f_{k, j - 1}

把 $f_{i, j}$ 和按照对 j + 1 的模数分类前缀和可以优化一层循环，之后时间复杂度是 $\Theta(n^2)$ 恰好就能过了。

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 3010;
6
const int MOD = 1000000007;
7
long long s[N], f[N][N], g[N][N];
8

9
int main() {
10
    int n;
11
    scanf("%d", &n);
12
    g[0][0] = 1;
13
    f[0][0] = 1;
14
    for (int i = 1; i <= n; ++i) {
15
        scanf("%lld", &s[i]);
16
        s[i] += s[i - 1];
17
    }
18
    for (int i = 1; i <= n; ++i) {
19
        for (int j = 1; j <= n; ++j) {
20
            f[i][j] = g[s[i] % j][j - 1];
21
        }
22
        for (int j = 1; j < n; ++j) {
23
            g[s[i] % (j + 1)][j] += f[i][j];
24
            g[s[i] % (j + 1)][j] %= MOD;
25
        }
26
    }
27
    long long res = 0;
28
    for (int i = 1; i <= n; ++i) {
29
        res = (res + f[n][i]) % MOD;
30
    }
31
    printf("%lld\n", res);
32
    return 0;
33
}

B. 超电磁炮#

按说答案就是 $\lceil\log_2{n}\rceil$ 但是好像精度出了点问题，那就二分答案。

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
int main() {
7
    long long n;
8
    cin >> n;
9
    long long l = 0, r = 64;
10
    while (l < r) {
11
        long long mid = l + r >> 1;
12
        if ((1ll << mid) >= n) r = mid;
13
        else l = mid + 1;
14
    }
15
    cout << l << endl;
16
    return 0;
17
}

C. 为美好的世界献上爆炎#

先从小到大一点一点试

l + r 一循环，一个循环内，小于 l 的必败，其余必胜。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        int n, l, r;
10
        scanf("%d%d%d", &n, &l, &r);
11
        if (l <= (n % (l + r))) printf("yes\n");
12
        else printf("no\n");
13
    }
14
    return 0;
15
}

D. 八进制小数#

高精硬算，之前做过所以直接复制过来了。

1
#include <iostream>
2
#include <vector>
3
#include <cmath>
4

5
using namespace std;
6

7
struct Hipre {
8
    vector<int> a;
9

10
    void mv(int t) {
11
        vector<int> b(t, 0);
12
        b.insert(b.end(), a.begin(), a.end());
13
        a = b;
14
    }
15
    Hipre() {
16
        a = vector<int>(1, 0);
17
    }
18

19
    Hipre(int n) {
20
        if (!n) {
21
            a = vector<int>(1, 0);
22
        }
23
        else
24
            while (n) {
25
                a.push_back(n % 10);
26
                n /= 10;
27
            }
28
    }
29

30
    int length() const {
31
        return a.size();
32
    }
33

34
    int to_int() {
35
        int res = 0, mul = 1;
36
        for (int i = 0; i < a.size(); ++i) {
37
            res += a[i] * mul;
38
            mul *= 10;
39
        }
40
        return res;
41
    }
42

43
    int &operator [](const int &p) {
44
        return a[p];
45
    }
46

47
    friend istream &operator >>(istream &cin, Hipre &a) {
48
        static string s;
49
        cin >> s;
50
        a.a = vector<int>(s.length());
51
        for (int i = 0; i < s.length(); ++i) {
52
            a.a[i] = s[s.length() - i - 1] - 48;
53
        }
54
        while (a.length() > 1 && a.a.back() == 0) a.a.pop_back();
55
        return cin;
56
    }
57

58
    friend ostream &operator <<(ostream &cout, const Hipre &a) {
59
        for (int i = a.length() - 1; i >= 0; --i)
60
            cout << a.a[i];
61
        return cout;
62
    }
63

64
    bool operator <(const Hipre &c) const {
65
        if (length() != c.length()) return length() < c.length();
66
        else {
67
            for (int i = length() - 1; i >= 0; --i) {
68
                if (a[i] != c.a[i]) return a[i] < c.a[i];
69
            }
70
            return false;
71
        }
72
    }
73

74
    bool operator ==(const Hipre &c) const {
75
        if (length() != c.length()) return false;
76
        else {
77
            for (int i = length() - 1; i >= 0; --i) {
78
                if (a[i] != c.a[i]) return false;
79
            }
80
            return true;
81
        }
82
    }
83

84
    Hipre operator +(const Hipre &c) {
85
        auto &b = c.a;
86
        Hipre res;
87
        res.a = vector<int>(max(a.size(), b.size()) + 1, 0);
88
        for (int i = 0; i < res.length(); ++i) {
89
            if (i < a.size() && i < b.size()) res[i] += a[i] + b[i];
90
            else if (i < a.size()) res[i] += a[i];
91
            else if (i < b.size()) res[i] += b[i];
92
            if (res[i] > 9) res.a[i + 1] += 1, res[i] -= 10;
93
        }
94
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
95
        return res;
96
    }
97

98
    Hipre operator -(const Hipre &c) {
99
        Hipre res = *this;
100
        for (int i = 0; i < res.length(); ++i) {
101
            if (i < c.length()) res[i] -= c.a[i];
102
            if (res[i] < 0) res[i] += 10, res.a[i + 1] -= 1;
103
        }
104
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
105
        return res;
106
    }
107

108
    Hipre operator *(const Hipre &c) {
109
        auto &b = c.a;
110
        Hipre res;
111
        res.a = vector<int>(a.size() + b.size(), 0);
112
        for (int i = 0; i < a.size(); ++i) {
113
            for (int j = 0; j < b.size(); ++j) {
114
                res.a[i + j] += a[i] * b[j];
115
            }
116
        }
117
        for (int i = 0; i < res.length() - 1; ++i) {
118
            res.a[i + 1] += res[i] / 10;
119
            res[i] %= 10;
120
        }
121
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
122
        return res;
123
    }
124

125
    Hipre operator *=(const int &c) {
126
        if (c)
127
            a.resize(a.size() + (int)floor(log10(c)) + 1);
128
        for (int i = 0; i < a.size(); ++i) {
129
            a[i] *= c;
130
        }
131
        for (int i = 0; i < a.size() - 1; ++i) {
132
            if (a[i] > 9) a[i + 1] += a[i] / 10, a[i] %= 10;
133
        }
134
        while (a.size() > 1 && a.back() == 0) a.pop_back();
135
        return *this;
136
    }
137

138
    Hipre operator *(const int &c) {
139
        Hipre t = *this;
140
        return t *= c;
141
    }
142

143
    Hipre operator /(const int &c) {
144
        Hipre res;
145
        res.a = vector<int>(a.size());
146
        int t = 0;
147
        for (int i = a.size() - 1; i >= 0; --i) {
148
            t = t * 10 + a[i];
149
            if (t >= c) res[i] = t / c;
150
            t %= c;
151
        }
152
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
153
        return res;
154
    }
155

156
    Hipre operator /(Hipre c) {
157
        Hipre res, b = *this;
158
        int l = b.length() - c.length();
159
        res.a = vector<int>(l + 1, 0);
160
        c.mv(b.length() - c.length());
161
        for (int i = l; i >= 0; --i) {
162
            while (!(b < c)) {
163
                b = b - c;
164
                res[i]++;
165
            }
166
            c.a.erase(c.a.begin());
167
        }
168
        while (res.length() > 1 && res.a.back() == 0) res.a.pop_back();
169
        return res;
170
    }
171

172
    Hipre operator %(Hipre c) {
173
        Hipre b = *this;
174
        int l = b.length() - c.length();
175
        c.mv(b.length() - c.length());
176
        for (int i = l; i >= 0; --i) {
177
            while (!(b < c)) {
178
                b = b - c;
179
            }
180
            c.a.erase(c.a.begin());
181
        }
182
        while (b.length() > 1 && b.a.back() == 0) b.a.pop_back();
183
        return b;
184
    }
185
};
186

187

188
int main() {
189
    ios::sync_with_stdio(0);
190
    cin.tie(0), cout.tie(0);
191
    string s;
192
    Hipre ans(0), base(125);
193
    cin >> s;
194
    for (auto i : s) {
195
        ans = ans * 1000 + base * (i - 48);
196
        base *= 125;
197
    }
198
    vector<int> t = ans.a;
199
    int i = 3 * s.length() - t.size();
200
    while (i--) cout << 0;
201
    i = 0;
202
    while (t[i] == 0 && i < t.size()) i++;
203
    for (int j = t.size() - 1; j >= i; --j) cout << t[j];
204
    cout << endl;
205
    return 0;
206
}

E. 愿此行终抵群星#

按照字典序排序，记 $f_i$ 为不经过反物质军团到达第 i 个的点的方案数，统计方案数的一大问题就是怎么不重不漏，可以先求从起点到 i 的总方案数，然后减掉不合法的。统计不合法的方案时，可以枚举第一个经过的反物质军团坐标，只要第一个不一样，那么一定不会重复，后面直接用组合数算就可以正好覆盖所有方案。

f_i = \text{way}\left(p_0, p_i\right) - \sum_{1 \le j < i} f_j * way(p_j, p_i)

其中 p_i 表示排序后第 i 个点的坐标，way(a, b) 表示坐标 a 和坐标 b 之间没有限制情况下的路径数。

预处理的数组别开小了，最坏的情况 10 个维度每个维度 10⁵ 要开 1e6！

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
const int MOD = 998244353;
8
const int N = 5010, M = 1000010;
9

10
int power(int n, int p) {
11
    long long res = 1, base = n;
12
    while (p) {
13
        if (p & 1) res = res * base % MOD;
14
        base = base * base % MOD;
15
        p >>= 1;
16
    }
17
    return res;
18
}
19

20
int jc[M], inv[M];
21
int f[N];
22
vector<int> p[N];
23

24
int c(int n, int m) {
25
    return 1LL * jc[n] * inv[m] % MOD * inv[n - m] % MOD;
26
}
27

28
int way(vector<int> a, vector<int> b) {
29
    long long res = 1;
30
    int k = a.size(), n = 0;
31
    for (int i = 0; i < k; ++i) {
32
        res = (res * c(n + (b[i] - a[i]), n)) % MOD;
33
        n += b[i] - a[i];
34
    }
35
    return res;
36
}
37

38
bool le(vector<int> a, vector<int> b) {
39
    int n = a.size();
40
    for (int i = 0; i < n; ++i) {
41
        if (a[i] > b[i]) return false;
42
    }
43
    return true;
44
}
45

46
int main() {
47
    jc[0] = inv[0] = 1;
48
    for (int i = 1; i <= 1000000; ++i) {
49
        jc[i] = 1LL * jc[i - 1] * i % MOD;
50
        inv[i] = power(jc[i], MOD - 2);
51
    }
52
    int k, n;
53
    scanf("%d%d", &k, &n);
54
    for (int i = 0; i <= n + 1; ++i) {
55
        p[i] = vector<int>(k, 0);
56
    }
57
    for (int i = 0; i < k; ++i) {
58
        scanf("%d", &p[n + 1][i]);
59
    }
60
    for (int i = 1; i <= n; ++i) {
61
        for (int j = 0; j < k; ++j) {
62
            scanf("%d", &p[i][j]);
63
        }
64
    }
65
    sort(p + 1, p + n + 1);
66
    f[0] = 1;
67
    for (int i = 1; i <= n + 1; ++i) {
68
        f[i] = way(p[0], p[i]);
69
        for (int j = 1; j < i; ++j) {
70
            if (le(p[j], p[i])) {
71
                f[i] = (f[i] - (1LL * f[j] * way(p[j], p[i]) % MOD) + MOD) % MOD;
72
            }
73
        }
74
    }
75
    printf("%d\n", f[n + 1]);
76
    return 0;
77
}

Star's Blog

A. 分割数组#

B. 超电磁炮#

C. 为美好的世界献上爆炎#

D. 八进制小数#

E. 愿此行终抵群星#