2023-11-01 NOIP 模拟赛题解

发表于 分类于

2023-11-01 的模拟赛，应该是 jzyz 出的题，被爆杀了

预估得分 100+20+20+10=150100 + 20 + 20 + 10 = 150

实际得分 40+10+16+0=6640 + 10 + 16 + 0 = 66

A 的复杂度假了，没卡过去，C 题题面没说捆 Subtask 结果数据捆了，D 题文件名写错了

赛后还发现 D 题的数据巨水，n2n ^ 2 加上优化可以过掉 10510 ^ 5 的数据，得到整整 70pts

哪个天才造的数据

A. 再

题意

给定 nn，在一个 n×nn \times n 的矩阵中从外到内按逆时针顺序依次填入数字，得到一个类似与下面的矩阵：

[11615141321724231231825221141920211056789]\begin{bmatrix} 1 & 16 & 15 & 14 & 13 \\ 2 & 17 & 24 & 23 & 12 \\ 3 & 18 & 25 & 22 & 11 \\ 4 & 19 & 20 & 21 & 10 \\ 5 & 6 & 7 & 8 & 9 \end{bmatrix}

现在定义如下两种查询：

  1. ∑i=knai,i−k+1\sum \limits_{i = k}^{n} a_{i, i - k + 1}
  2. ∑i=knai−k+1,i\sum \limits_{i = k}^{n} {a_{i - k + 1, i}}

现在给定 TT 组查询（1≤T≤1061 \le T \le 10 ^ 6），每组查询给定一个 n,op,kn, op, k 分别代表矩阵的大小，操作类型，和操作的参数（1≤n,k≤1091 \le n, k \le 10 ^ 9）

输出每组查询的结果对 998244353998244353 取模之后的异或和

思路

首先观察操作，发现规律：操作一求的是 (k,1)(k, 1) 到 (n,n−k+1)(n, n - k + 1) 这两点之间的和，操作二求的是 (1,k)(1, k) 到 (n−k+1,n)(n - k + 1, n) 这两点之间的和

发现这条线上的对称的两个数之和等于对应的对角线上的数之和乘 22，例如 (3,1)+(1,3)=(5,1)×2(3, 1) + (1, 3) = (5, 1) \times 2

那么原来要求的数之和即可转化为如干个主对角线上的数之和乘 22（注意特判最后一个位置）

我们定义一个 p=n−k+1p = n - k + 1，pp 代表的就是主对角线上的数的个数

下面首先考虑操作 11

经过推导可以得到如下式子：

ans={∑i=1pan−i+1,i,p≡0(mod2)∑i=1pan−i+1,i−an−p+1,p,p≡1(mod2)ans = \begin{cases} \sum \limits_{i = 1}^{p} {a_{n - i + 1, i}}, & p \equiv 0 \pmod 2 \\ \sum \limits_{i = 1}^{p} {a_{n - i + 1, i}} - a_{n - p + 1, p}, & p \equiv 1 \pmod 2 \end{cases}

现在我们需要在近似 O(1)O(1) 的时间复杂度内求出对角线上的数字之和

将主对角线提取出来，可以发现对角线的第一项为 nn，后边几项之差依次为 4n−6,4(n−2)−6,4(n−4)−64n - 6, 4(n - 2) - 6, 4(n - 4) - 6

换句话说，对角线上的相邻两个元素之差为一个等差数列，即对角线上的数构成了一个二阶等差数列

下面考虑如何快速求和

首先可以想到矩阵快速幂

显然我们可以构造一个如下矩阵：

[1lennowans]\begin{bmatrix} 1 & len & now & ans \end{bmatrix}

其中，lenlen 表示的是当前项与下边一项之差加上 66 再除以 44 的结果，也就是 4n−64n - 6 中的当前的 nn

nownow 表示的是对角线上当前项的值，ansans 就是对角线上的值的和

那么可以构造出初始矩阵为：

[1nnn]\begin{bmatrix} 1 & n & n & n \end{bmatrix}

转移矩阵为

[1−2−6−6014400110001]\begin{bmatrix} 1 & -2 & -6 & -6 \\ 0 & 1 & 4 & 4 \\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}

类似地，可以构造出操作二的初始矩阵为

[1n3n−23n−2]\begin{bmatrix} 1 & n & 3n - 2 & 3n - 2 \end{bmatrix}

转移矩阵为

[1−2−10−10014400110001]\begin{bmatrix} 1 & -2 & -10 & -10 \\ 0 & 1 & 4 & 4 \\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}

使用矩阵快速幂即可在 O(log⁡n)O(\log n) 时间内求出

你以为这就完了，然而并没有

我在赛场上认为这样的复杂度足以通过本题，然而我还是太年轻了，忘记了矩阵乘法的常数问题

每次矩阵乘法都有 4×4=164 \times 4 = 16 的常数，总的时间复杂度量级约在 16×T×log⁡n=16×106×30=4.8×10816 \times T \times \log n = 16 \times 10 ^ 6 \times 30 = 4.8 \times 10 ^ 8 ，由于学校 OJ 慢，所以需要用更加快速的算法

注意到我们现在正在解决的问题其实就是二阶等差数列的前缀和问题，考虑能否使用通项公式直接 O(1)O(1) 求解

经过一番 Google，我们知道了二阶等差数列的通项公式为：

Sn=a1×C(n,1)+b1×C(n,2)+d×C(n,3)S_n = a_1 \times C(n, 1) + b_1 \times C(n, 2) + d \times C(n, 3)

其中，a1a_1 为二阶等差数列的首项，bi=ai+1−ai,d=bi+1−bib_i = a_{i + 1} - a_i, d = b_{i + 1} - b_i

将原数列的代入，化简，可以得到如下结果：

ans1=C(k,1)×n+C(k,2)×(4n−6)−C(k,3)×8=k×n+(k2−k)(4n−6)2−k3−3k2+2k6×8=nk+4nk2−6k2−4nk+6k2+4k3+12k2−8k3=nk+2nk2−3k2−2nk+3k−4k33+4k2−8k3=k3+k2−4k33−nk+2nk2ans2=C(k,1)×(3n−2)+C(k,2)×(4n−10)−C(k,3)×8=k×(3n−2)+(k2−k)(4n−10)2−k3−3k2+2k6×8=3nk−2k+4nk2−10k2−4nk+10k2+4k3+12k2−8k3=3nk−2k+2nk2−5k2−2nk+5k−4k33+4k2−8k3=k3−k2−4k33+nk+2nk2\begin{aligned} ans_1 & = C(k, 1) \times n + C(k, 2) \times (4n - 6) - C(k, 3) \times 8 \\ & = k \times n + \frac{(k ^ 2 - k)(4n - 6)}{2} - \frac{k ^ 3 - 3k ^ 2 + 2k}{6} \times 8 \\ & = nk + \frac{4nk ^ 2 - 6k ^ 2 - 4 nk + 6k}{2} + \frac{4k ^ 3 + 12k ^ 2 - 8k}{3} \\ & = nk + 2nk ^ 2 - 3k ^ 2 - 2nk + 3k - \frac{4k ^ 3}{3} + 4k ^ 2 - \frac{8k}{3} \\ & = \frac{k}{3} + k ^ 2 - \frac{4k ^ 3}{3} - nk + 2nk ^ 2 \\ ans_2 & = C(k, 1) \times (3n - 2) + C(k, 2) \times (4n - 10) - C(k, 3) \times 8 \\ & = k \times (3n - 2) + \frac{(k ^ 2 - k)(4n - 10)}{2} - \frac{k ^ 3 - 3k ^ 2 + 2k}{6} \times 8 \\ & = 3nk - 2k + \frac{4nk ^ 2 - 10k ^ 2 - 4nk + 10k}{2} + \frac{4k ^ 3 + 12k ^ 2 - 8k}{3} \\ & = 3nk - 2k + 2nk ^ 2 - 5k ^ 2 - 2nk + 5k - \frac{4k ^ 3}{3} + 4k ^ 2 - \frac{8k}{3} \\ & = \frac{k}{3} - k ^ 2 - \frac{4k ^ 3}{3} + nk + 2nk ^ 2 \end{aligned}

直接代入求值即可，总的时间复杂度为 O(T)O(T)

由于答案是关于 n,kn, k 的一个三次多项式，那么我们如果将 nn 看成系数，答案就是一个关于 kk 的三次函数，也可以使用拉格朗日插值 / 高斯消元的方法解决，这样就可以避免化简式子的烦恼

代码

矩阵快速幂版本

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
namespace matrix
{
    typedef long long LL;
    struct Matrix
    {
        static const int MAXSIZE = 10;
        int colume, line;
        LL m[MAXSIZE][MAXSIZE];
        Matrix(int col = 0, int ln = 0) : colume(col), line(ln)
        {
            memset(m, 0, sizeof(m));
        }
        Matrix &operator=(Matrix a)
        {
            this->colume = a.colume, this->line = a.line;
            for (int i = 1; i <= a.line; i++)
            {
                for (int j = 1; j <= a.colume; j++)
                {
                    this->m[i][j] = a.m[i][j];
                }
            }
            return *this;
        }
    };
    Matrix operator+(const Matrix a, const Matrix b)
    {
        if (a.colume != b.colume)
        {
            throw "Matrix Colume Not equal";
        }
        if (a.line != b.line)
        {
            throw "Matrix line Not equal";
        }
        Matrix res(a.colume, a.line);
        for (int i = 1; i <= a.line; i++)
        {
            for (int j = 1; j <= a.colume; i++)
            {
                res.m[i][j] = a.m[i][j] + b.m[i][j];
            }
        }
        return res;
    }
    Matrix operator-(const Matrix a, const Matrix b)
    {
        if (a.colume != b.colume)
        {
            throw "Matrix colume not equal";
        }
        if (a.line != b.line)
        {
            throw "Matrix line not equal";
        }
        Matrix res(a.colume, a.line);
        for (int i = 1; i <= a.line; i++)
        {
            for (int j = 1; j <= a.colume; i++)
            {
                res.m[i][j] = a.m[i][j] - b.m[i][j];
            }
        }
        return res;
    }
    Matrix operator*(const Matrix a, const Matrix b)
    {
        if (a.colume != b.line)
        {
            printf("Matrix a: %d line %d col.\n", a.line, a.colume);
            printf("Matrix b: %d line %d col.\n", b.line, b.colume);
            throw "Matrix cannot multiple";
        }
        Matrix res(a.colume, b.line);
        for (int i = 1; i <= a.line; i++)
        {
            for (int j = 1; j <= b.colume; j++)
            {
                for (int k = 1; k <= a.colume; k++)
                {
                    res.m[i][j] += a.m[i][k] * b.m[k][j];
                }
            }
        }
        return res;
    }
    Matrix operator%(const Matrix a, const int b)
    {
        Matrix res(a.colume, a.line);
        for (int i = 1; i <= a.line; i++)
        {
            for (int j = 1; j <= a.colume; j++)
            {
                res.m[i][j] = a.m[i][j] % b;
            }
        }
        return res;
    }
    Matrix getUnitMatrix(int x)
    {
        Matrix res(x, x);
        for (int i = 1; i <= x; i++)
        {
            res.m[i][i] = 1;
        }
        return res;
    }
    Matrix qpow(Matrix a, int b, int mod)
    {
        bool flag = true;
        Matrix res;
        while (b)
        {
            if (b & 1)
            {
                if (flag)
                {
                    res = a;
                    flag = false;
                }
                else
                {
                    res = res * a;
                    res = res % mod;
                }
            }
            a = a * a;
            a = a % mod;
            b >>= 1;
        }
        if (flag == true)
        {
            return getUnitMatrix(a.line);
        }
        return res;
    }
}
namespace solution
{
    using matrix::Matrix;
    typedef long long LL;
    const int MOD = 998244353;
    const int MUL_MATRIX_OP1[4][4] = {{1, -2, -6, -6},
                                      {0, 1, 4, 4},
                                      {0, 0, 1, 1},
                                      {0, 0, 0, 1}};
    const int MUL_MATRIX_OP2[4][4] = {{1, -2, -10, -10},
                                      {0, 1, 4, 4},
                                      {0, 0, 1, 1},
                                      {0, 0, 0, 1}};
    int t;
    int n, k, op;
    LL ans = 0;
    LL res = 0;
    matrix::Matrix m, m1, m2;
    void init()
    {
        m1 = m2 = Matrix(4, 4);
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 4; j++)
            {
                m1.m[i + 1][j + 1] = MUL_MATRIX_OP1[i][j];
                m2.m[i + 1][j + 1] = MUL_MATRIX_OP2[i][j];
            }
        }
    }
    int main()
    {
        freopen("again.in", "r", stdin);
        freopen("again.out", "w", stdout);
        init();
        scanf("%d", &t);
        while (t--)
        {
            scanf("%d%d%d", &n, &op, &k);
            k = n - k + 1;
            m = Matrix(4, 1);
            if (k == n)
            {
                op = 1;
            }
            if (op == 1)
            {
                m.m[1][1] = 1, m.m[1][2] = n, m.m[1][3] = n, m.m[1][4] = n;
                m = m * matrix::qpow(m1, std::ceil((double)k / 2) - 1, MOD) % MOD;
            }
            if (op == 2)
            {
                m.m[1][1] = 1, m.m[1][2] = n, m.m[1][3] = 3 * n - 2, m.m[1][4] = 3 * n - 2;
                m = m * matrix::qpow(m2, std::ceil((double)k / 2) - 1, MOD) % MOD;
            }
            res = m.m[1][4] * 2 % MOD;
            if (k % 2 == 1)
            {
                res -= m.m[1][3];
            }
            res = ((res % MOD) + MOD) % MOD;
            ans = ans ^ res;
            // printf("%lld\n", res);
        }
        printf("%lld\n", ans);
        return 0;
    }
}
int main()
{
    try
    {
        solution::main();
    }
    catch (const char *e)
    {
        puts(e);
    }
    return 0;
}

直接计算版本

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
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    typedef __int128 SLL;
    const int MOD = 998244353;
    int t;
    int n, k, op;
    LL ans = 0;
    LL res = 0;
    SLL solve(int op, SLL n, SLL k)
    {
        if (op == 1)
        {
            return k * k - n * k + 2 * n * k * k + (1 * k - 4 * k * k * k) / 3;
        }
        else
        {
            return -k * k + n * k + 2 * n * k * k + (1 * k - 4 * k * k * k) / 3;
        }
    }
    SLL getN(int op, SLL n, SLL k)
    {
        SLL a, d;
        if (op == 1)
        {
            a = 4 * n - 6, d = -8;
            return n + (a + a + (k - 2) * d) * (k - 1) / 2;
        }
        else
        {
            a = 4 * n - 10, d = -8;
            return 3 * n - 2 + (a + a + (k - 2) * d) * (k - 1) / 2;
        }
    }
    int main()
    {
        freopen("again.in", "r", stdin);
        freopen("again.out", "w", stdout);
        scanf("%d", &t);
        while (t--)
        {
            scanf("%d%d%d", &n, &op, &k);
            k = n - k + 1;
            if (k == n)
            {
                op = 1;
            }
            res = solve(op, n, std::ceil((double)k / 2)) * 2 % MOD;
            if (k % 2 == 1)
            {
                res -= getN(op, n, std::ceil((double)k / 2));
            }
            res %= MOD, res += MOD, res %= MOD;
            ans = ans ^ res;
        }
        printf("%lld\n", ans);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}

B. 建

题意

给定一张 nn 个点的有向图，初始时每个点 ii 都有一条边指向 i+1i + 1

再给定 qq 组询问，每个询问有如下三种类型：

  1. 含有两个参数 u,vu, v，表明插入一条从 uu 到 vv 的边
  2. 含有两个参数 u,vu, v，表明删除一条从 uu 到 vv 的边
  3. 仅含有一个参数 xx，表明查询 xx 可以到达的点的个数

注意，不保证图中没有重边 / 自环，但是保证每次操作后仍然存在 ii 指向 i+1i + 1 的边

对于所有数据，满足 1≤n,q≤1051 \le n, q \le 10 ^ 5

思路

首先由于每个点都一定可以到达在它之后的点，那么插入一条边 (u,v),(u<v)(u, v), (u < v) 就是无意义的

也就是说我们需要统计的只有 ii 可以到达的在 ii 之前的点即可

考虑使用线段树维护，每次修改操作在对应的区间加 11，删除则减 11

每次询问就相当于在找 ii 之前的第一个 00，也就是第一个在 ii 之前且 ii 无法到达的点

经典的线段树分治问题，在线段树上维护区间最小值，查询时在线段树上二分即可解决

时间复杂度为 O(nlog⁡n)O(n\log 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
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 <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 5e5 + 5;
    int n, q;
    struct Node
    {
        int min;
        int tag;
    };
    Node node[MAXN << 2];
    void pushup(int o)
    {
        node[o].min = std::min(node[o << 1].min, node[o << 1 | 1].min);
    }
    void pushdown(int o)
    {
        node[o << 1].min += node[o].tag, node[o << 1].tag += node[o].tag;
        node[o << 1 | 1].min += node[o].tag, node[o << 1 | 1].tag += node[o].tag;
        node[o].tag = 0;
    }
    void update(int o, int l, int r, int ql, int qr, int v)
    {
        if (ql <= l && r <= qr)
        {
            node[o].min += v, node[o].tag += v;
            return;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        if (mid >= ql)
        {
            update(o << 1, l, mid, ql, qr, v);
        }
        if (mid < qr)
        {
            update(o << 1 | 1, mid + 1, r, ql, qr, v);
        }
        pushup(o);
    }
    int query(int o, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
        {
            return node[o].min;
        }
        pushdown(o);
        int mid = (l + r) >> 1, res = 0;
        if (mid >= ql)
        {
            res += query(o << 1, l, mid, ql, qr);
        }
        if (mid < qr)
        {
            res += query(o << 1 | 1, mid + 1, r, ql, qr);
        }
        return res;
    }
    int find(int o, int l, int r, int x)
    {
        if (node[o].min != 0)
        {
            return l;
        }
        if (l == r)
        {
            return l + 1;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        if (x <= mid)
        {
            return find(o << 1, l, mid, x);
        }
        else
        {
            int res = find(o << 1 | 1, mid + 1, r, x);
            if (res == mid + 1)
            {
                res = find(o << 1, l, mid, x);
            }
            return res;
        }
    }
    int main()
    {
        freopen("build.in", "r", stdin);
        freopen("build.out", "w", stdout);
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= q; i++)
        {
            int op;
            scanf("%d", &op);
            if (op == 1)
            {
                int u, v;
                scanf("%d%d", &u, &v);
                if (u > v)
                {
                    update(1, 1, n, v + 1, u, 1);
                }
            }
            if (op == 2)
            {
                int u, v;
                scanf("%d%d", &u, &v);
                if (u > v)
                {
                    update(1, 1, n, v + 1, u, -1);
                }
            }
            if (op == 3)
            {
                int x;
                scanf("%d", &x);
                printf("%d\n", n - find(1, 1, n, x) + 2);
            }
        }
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}