1102Div2-①数学②构造+数学③前后缀最大值/并查集④分治+贡献法#

Dashboard - Codeforces Round 1102 (Div. 2) - Codeforces

A-数学#

题目重述#

给定一个长度为 $n$ 的序列 $b$ 。

对于两个正整数 $x \ge y$ ，定义欧几里得算法序列：

a_1=x,\quad a_2=y

对于任意 $1\le i\le k-2$ ：

a_{i+2}=a_i \bmod a_{i+1}

例如：

x=13,\ y=8

得到：

[13,8,5,3]

因为：

13\bmod 8=5

8\bmod 5=3

现在给定一个序列 $b$ ，允许任意重排其元素。

判断是否存在一组 $(x,y)$ ，使重排后的序列恰好成为某个欧几里得算法序列。

若存在输出任意一组 $(x,y)$ ，否则输出 $-1$ 。

性质分析#

根据余数定义：

a_{i+2}=a_i\bmod a_{i+1}

且余数满足：

0\le a_{i+2}<a_{i+1}

题目保证序列中的元素均为正整数，因此：

a_{i+2}>0

于是有：

a_{i+2}<a_{i+1}

即：

a_1>a_2>a_3>\cdots>a_k

因此：

任意合法欧几里得序列一定严格递减。

设将数组按降序排列得到：

c_1>c_2>\cdots>c_n

如果原数组能够重排成欧几里得序列，那么重排后的顺序只能是这个降序排列。

因为欧几里得序列严格递减。

同时根据定义必须满足：

c_i \bmod c_{i+1}=c_{i+2}

对于所有：

1\le i\le n-2

成立。

因此得到判定条件：

数组降序排列后必须严格递减；
对所有 $i$ ：

c_i\bmod c_{i+1}=c_{i+2}

若全部满足，则：

x=c_1,\quad y=c_2

就是一个合法答案。

正确性证明#

必要性

若存在一组 $(x,y)$ 使得数组能够重排成欧几里得序列。

由于欧几里得序列严格递减，因此重排后的序列必然等于降序排列：

c_1>c_2>\cdots>c_n

又根据定义：

a_{i+2}=a_i\bmod a_{i+1}

因此：

c_i\bmod c_{i+1}=c_{i+2}

对所有 $i$ 成立。

必要性成立。

充分性

若降序排列后满足：

c_i\bmod c_{i+1}=c_{i+2}

对所有 $i$ 成立。

取：

x=c_1,\quad y=c_2

根据欧几里得序列定义：

a_3=x\bmod y=c_3

a_4=c_2\bmod c_3=c_4

依次递推可得：

a_i=c_i

因此整个序列正好为：

c_1,c_2,\cdots,c_n

故原数组经过重排后确实能成为欧几里得序列。

充分性成立。

1
t = int(input())
2
for _ in range(t):
3
    n = int(input())
4
    b = list(map(int, input().split()))
5
    if n == 2:
6
        print(max(b), min(b))
7
        continue
8
    c = sorted(b, reverse=True)
9
    ok = True
10
    # 必须严格递减
11
    for i in range(n - 1):
12
        if c[i] <= c[i + 1]:
13
            ok = False
14
            break
15
    # 检查取模关系
16
    if ok:
17
        for i in range(n - 2):
18
            if c[i] % c[i + 1] != c[i + 2]:
19
                ok = False
20
                break
21
    if ok:
22
        print(c[0], c[1])
23
    else:
24
        print(-1)

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    ios::sync_with_stdio(false);
5
    cin.tie(nullptr);
6
    int T;
7
    cin >> T;
8
    while (T--) {
9
        int n;
10
        cin >> n;
11
        vector<long long> b(n);
12
        for (int i = 0; i < n; i++) {
13
            cin >> b[i];
14
        }
15
        if (n == 2) {
16
            cout << max(b[0], b[1]) << " "
17
                 << min(b[0], b[1]) << '\n';
18
            continue;
19
        }
20
        sort(b.begin(), b.end(), greater<long long>());
21
        bool ok = true;
22

23
        for (int i = 0; i < n - 1; i++) {
24
            if (b[i] <= b[i + 1]) {
25
                ok = false;
26
                break;
27
            }
28
        }
29
        if (ok) {
30
            for (int i = 0; i < n - 2; i++) {
31
                if (b[i] % b[i + 1] != b[i + 2]) {
32
                    ok = false;
33
                    break;
34
                }
35
            }
36
        }
37
        if (ok)
38
            cout << b[0] << " " << b[1] << '\n';
39
        else
40
            cout << -1 << '\n';
41
    }
42
    return 0;
43
}

复杂度分析#

排序复杂度：

O(n\log n)

检查复杂度：

O(n)

总复杂度：

O(n\log n)

B-构造+数学#

题目重述#

给定一个正整数 $n$ 。

需要找到两个非负整数 $a,b$ ，满足：

$a+b=n$
$a$ 是回文数
$b$ 能被 $12$ 整除

若存在这样的数对，输出任意一组；否则输出 $-1$ 。

思路分析#

由题意可得：

b=n-a

由于 $b$ 能被 $12$ 整除，因此：

n-a\equiv0\pmod{12}

即：

a\equiv n\pmod{12}

于是问题转化为：

找一个不超过 $n$ 的回文数 $a$ ，使得 $a$ 与 $n$ 在模 $12$ 意义下同余。

对于模 $12$ 的每个余数，都可以找到一个很小的回文数作为代表：

余数	回文数
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
10	22
11	11

其中：

22 \equiv 10 \pmod{12}

11 \equiv 11 \pmod{12}

因此对于任意余数 $r=n\bmod12$ ：

取表中对应的回文数 $a$ ，

则一定满足：

a\equiv n\pmod{12}

于是：

b=n-a

必然能被 $12$ 整除。

无解情况#

唯一特殊情况是：

n=10

因为：

10\bmod12=10

对应的最小回文数是：

a=22

但：

22>10

无法满足非负整数条件。

因此无解。

事实上：

当 $n=10$ 时输出 $-1$
其余所有 $n$ 都存在解

正确性证明#

设查表得到的数为 $a$ 。

回文性质#

表中的数字：

0,1,2,\cdots,9,11,22

均为回文数。

因此 $a$ 一定满足回文条件。

整除性质#

由构造可知：

a\equiv n\pmod{12}

因此：

n-a\equiv0\pmod{12}

即：

b=n-a

一定能被 $12$ 整除。

和为 n#

定义：

b=n-a

显然：

a+b=n

成立。

复杂度分析#

每组测试仅进行常数次运算：

O(1)

总复杂度：

O(t)

空间复杂度：

O(1)

1
t = int(input())
2
pal = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 22, 11]
3
for _ in range(t):
4
    n = int(input())
5
    a = pal[n % 12]
6
    if a > n:
7
        print(-1)
8
    else:
9
        print(a, n - a)

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
    int T;
8
    cin >> T;
9
    long long pal[12] = {
10
        0, 1, 2, 3, 4, 5,
11
        6, 7, 8, 9, 22, 11
12
    };
13
    while (T--) {
14
        long long n;
15
        cin >> n;
16
        long long a = pal[n % 12];
17
        if (a > n) {
18
            cout << -1 << '\n';
19
        } else {
20
            cout << a << ' ' << n - a << '\n';
21
        }
22
    }
23
    return 0;
24
}

C-前后缀最大值#

题意简述#

有 n 个首尾相连的容器。

第 i 个容器与第 (i mod n)+1 个容器之间有一个高度为 h_i 的连通口。

设最终水位为 w_i。

对于每条边满足：

如果

\max(w_i,w_{i+1}) \le h_i

则没有限制；

如果

\max(w_i,w_{i+1}) > h_i

则必须有

w_i=w_{i+1}

对于每个位置 i，要求：

w_i=0

求所有合法方案中：

\sum w_i

的最大值。

关键性质#

固定某个位置 i 为空。

把环从该位置断开。

设新的边序列为：

1
e[0],e[1],...,e[n-1]

其中：

1
e[j] = h[(i+j)%n]

此时问题变成了一条链。

水位能够达到多少？#

考虑链上的某个位置 k。

它左边经过的所有连通口高度为：

1
e[0],e[1],...,e[k-1]

右边经过的所有连通口高度为：

1
e[k],e[k+1],...,e[n-1]

若位置 k 的水位超过左边某个连通口高度，则根据题目条件，该连通口两侧必须保持相同高度。

继续向左传播，最终会传到空容器。

由于空容器高度为 0，因此不可能。

所以位置 k 的高度不能超过左侧路径上的最大连通口高度。

同理：

位置 k 的高度也不能超过右侧路径上的最大连通口高度。

因此：

w_k \le \min \left( \max_{0\le t<k} e_t, \max_{k\le t<n} e_t \right)

最优构造#

为了使总水量最大，

显然每个位置都应该取到允许的最大值。

定义：

前缀最大值#

pre[k] = \max(e_0,e_1,\dots,e_k)

后缀最大值#

suf[k] = \max(e_k,e_{k+1},\dots,e_{n-1})

则位置 k 的最大合法高度为：

\min(pre[k-1],suf[k])

因此答案为：

\sum_{k=1}^{n-1} \min(pre[k-1],suf[k])

注意：

位置 0 对应空容器，

其高度固定为 0。

正确性证明#

设当前固定位置 i 为空。

引理1#

位置 k 的高度不能超过左侧路径中的最大连通口高度。

证明：

若

w_k > \max(e_0,\dots,e_{k-1})

则左侧所有边都会触发

w_u=w_v

最终传递到空容器。

于是得到

w_k=0

矛盾。

故结论成立。

引理2#

位置 k 的高度不能超过右侧路径中的最大连通口高度。

证明同理。

因此：

w_k \le \min(pre[k-1],suf[k])

引理3#

令

w_k= \min(pre[k-1],suf[k])

则一定合法。

因为对于任意边，

两侧高度都不会超过限制值，

若超过则两侧高度相同，

因此满足题目要求。

定理#

上述构造得到最大总水量。

因为每个位置都已经达到其理论上界，

任何方案都不可能取得更大的总和。

故算法正确。

复杂度分析#

对于每个起点：

构造数组：O(n)
前缀最大值：O(n)
后缀最大值：O(n)
统计答案：O(n)

总复杂度：

O(n^2)

Easy Version 中：

\sum n \le 3000

1
for _ in range(int(input())):
2
    n = int(input())
3
    h = list(map(int, input().split()))
4
    ans = [0] * n
5
    for i in range(n):
6
        e = [h[(i + j) % n] for j in range(n)]
7
        pre = [0] * n
8
        suf = [0] * n
9
        pre[0] = e[0]
10
        for j in range(1, n):
11
            pre[j] = max(pre[j - 1], e[j])
12
        suf[n - 1] = e[n - 1]
13
        for j in range(n - 2, -1, -1):
14
            suf[j] = max(suf[j + 1], e[j])
15
        cur = 0
16
        for k in range(1, n):
17
            cur += min(pre[k - 1], suf[k])
18
        ans[i] = cur
19
    print(*ans)

C-并查集#

题意重述#

有 n 个无限高的连通容器围成一个环。

第 i 个容器与第 (i mod n)+1 个容器之间有一条高度为 h[i] 的连通口。

设各容器水位为 w[i]。

对于每条边 (i,i+1)：

如果

\max(w_i,w_{i+1}) > h_i

那么必须有

w_i=w_{i+1}

否则该状态非法。

对于每个位置 s，要求：

w_s=0

在所有合法方案中求

\sum_{i=1}^{n} w_i

的最大值。

物理意义#

考虑相邻两个容器。

连接口高度为 h_i。

若两边水位都不超过 h_i：

$w_i <= h_i$$w_{i+1} <= h_i$

则完全合法。

若有一边超过了连接口：

$max(w_i,w_{i+1}) > h_i$

那么根据连通器原理，两边最终必须处于同一水位：

w_i=w_{i+1}

因此对于每条边：

要么两边都不超过 h_i
要么两边高度相等

固定一个空容器#

设要求：

w_s=0

由于环被断开，

问题变成了一条链：

$s+1,s+2,...,s-1$

因为两条与 s 相邻的边都连接到高度为 0 的容器。

重要结论#

设链上某个位置的最终高度为 x。

若想把它提高到超过某条边的限制：

$x > h_i$

则必须与边另一侧高度相同。

于是会不断向外扩展。

换句话说：

一个高度为 x 的连通块能够存在，

当且仅当它覆盖了所有

h_i < x

的边。

转换#

考虑所有边高度。

若固定一个高度值 X。

把满足

h_i < X

的边看成必须连通。

于是这些边把若干顶点合并成若干连通块。

每个连通块中的所有点高度都必须相等。

如果连通块内没有空容器 s，

则整个连通块都可以取高度 X。

如果连通块包含 s，

由于

w_s=0

整个块只能取高度 0。

因此对于固定高度 X：

贡献为

X \times (\text{不包含 } s \text{ 的点数})

Easy 版：

n\le 3000

且

\sum n \le 3000

因此可以直接枚举答案对应的高度。

枚举高度#

注意最优解中的高度变化只会发生在某个 h_i 处。

因此考虑：

$X = 1$$X = h_1+1$$X = h_2+1$$...$$X = h_n+1$

按照边权从小到大加入。

使用并查集维护：

$h_i < X$

的边形成的连通块。

并查集维护#

对于每个连通块记录：

1
sz = 连通块大小
2
has = 是否包含空容器 s

若某块不包含 s：

贡献

sz \times X

否则贡献为 0。

设

alive(X)

表示所有不含 s 的点数之和。

则当前方案价值：

alive(X)\times X

取最大即可。

Easy Version 复杂度#

对于每个空容器：

重新建并查集
按边权排序加入

复杂度：

O(n^2 \log n)

由于

n\le3000

且

\sum n\le3000

可以通过。

1
def find(p, x):
2
    if p[x] != x:
3
        p[x] = find(p, p[x])
4
    return p[x]
5
def union(p, rank, x, y):
6
    rx, ry = find(p, x), find(p, y)
7
    if rx == ry:
8
        return rx
9
    if rank[rx] < rank[ry]:
10
        p[rx] = ry
11
        return ry
12
    elif rank[rx] > rank[ry]:
13
        p[ry] = rx
14
        return rx
15
    else:
16
        p[ry] = rx
17
        rank[rx] += 1
18
        return rx
19
t = int(input())
20
for _ in range(t):
21
    n = int(input())
22
    h = list(map(int, input().split()))
23
    edges = [(h[i], i) for i in range(n)]
24
    edges.sort()
25
    ans = [0] * n
26
    for s in range(n):
27
        p = list(range(n))
28
        rank = [0] * n
29
        sz = [1] * n
30
        has = [0] * n
31
        has[s] = 1
32
        alive = n - 1
33
        best = alive
34
        ptr = 0
35
        while ptr < n:
36
            H = edges[ptr][0]
37
            while ptr < n and edges[ptr][0] == H:
38
                idx = edges[ptr][1]
39
                u = idx
40
                v = (idx + 1) % n
41
                fu = find(p, u)
42
                fv = find(p, v)
43
                if fu != fv:
44
                    before = 0
45
                    if has[fu] == 0:
46
                        before += sz[fu]
47
                    if has[fv] == 0:
48
                        before += sz[fv]
49
                    root = union(p, rank, fu, fv)
50
                    if root == fu:
51
                        other = fv
52
                    else:
53
                        other = fu
54
                    sz[root] += sz[other]
55
                    has[root] |= has[other]
56
                    after = 0
57
                    if has[root] == 0:
58
                        after += sz[root]
59
                    alive += after - before
60
                ptr += 1
61
            best = max(best, alive * (H + 1))
62
        ans[s] = best
63
    print(*ans)

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
struct DSU {
5
    vector<int> fa, sz, has;
6

7
    DSU(int n,int s):fa(n),sz(n,1),has(n,0){
8
        iota(fa.begin(),fa.end(),0);
9
        has[s]=1;
10
    }
11

12
    int find(int x){
13
        return fa[x]==x?x:fa[x]=find(fa[x]);
14
    }
15

16
    void unite(int a,int b){
17
        a=find(a);
18
        b=find(b);
19

20
        if(a==b) return;
21

22
        if(sz[a]<sz[b]) swap(a,b);
23

24
        fa[b]=a;
25
        sz[a]+=sz[b];
26
        has[a]|=has[b];
27
    }
28
};
29

30
int main(){
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33

34
    int T;
35
    cin>>T;
36

37
    while(T--){
38

39
        int n;
40
        cin>>n;
41

42
        vector<long long> h(n);
43

44
        for(int i=0;i<n;i++) cin>>h[i];
45

46
        vector<long long> ans(n);
47

48
        vector<pair<long long,int>> edges;
49

50
        for(int i=0;i<n;i++)
51
            edges.push_back({h[i],i});
52

53
        sort(edges.begin(),edges.end());
54

55
        for(int s=0;s<n;s++){
56

57
            DSU dsu(n,s);
58

59
            long long curAlive=n-1;
60
            long long best=curAlive;
61

62
            int ptr=0;
63

64
            while(ptr<n){
65

66
                long long H=edges[ptr].first;
67

68
                while(ptr<n && edges[ptr].first==H){
69

70
                    int id=edges[ptr].second;
71

72
                    int u=id;
73
                    int v=(id+1)%n;
74

75
                    int fu=dsu.find(u);
76
                    int fv=dsu.find(v);
77

78
                    if(fu!=fv){
79

80
                        long long before=0;
81

82
                        if(!dsu.has[fu]) before+=dsu.sz[fu];
83
                        if(!dsu.has[fv]) before+=dsu.sz[fv];
84

85
                        dsu.unite(fu,fv);
86

87
                        int f=dsu.find(fu);
88

89
                        long long after=0;
90

91
                        if(!dsu.has[f])
92
                            after+=dsu.sz[f];
93

94
                        curAlive+=after-before;
95
                    }
96

97
                    ptr++;
98
                }
99

100
                best=max(best,curAlive*(H+1));
101
            }
102

103
            ans[s]=best;
104
        }
105

106
        for(auto x:ans)
107
            cout<<x<<" ";
108
        cout<<"\n";
109
    }
110

111
    return 0;
112
}

D-分治+贡献法#

题目大意#

给定两个长度为 n 的二进制数：

a_1=s,\qquad a_{2^k+1}=z

其余位置通过如下规则生成：

若当前已知位置为

p_1<p_2<\cdots<p_m

则同时进行：

a_{\frac{p_i+p_{i+1}}2} = a_{p_i}\oplus a_{p_{i+1}} \qquad (1\le i<m)

最终得到长度为

2^k+1

的完整序列。

对于每个数：

$x_i$ 表示其中 1 的个数；
$y_i$ 表示其中 0 的个数。

要求计算：

\sum_{i=1}^{2^k+1}x_i y_i

思路分析#

转化贡献

对于某个位置 $i$ ：

x_i y_i

表示：

任选一个值为 1 的二进制位；
再任选一个值为 0 的二进制位。

因此：

x_i y_i

实际上等价于

统计该位置有多少对二进制位取值不同。

于是整个答案可以看成：

对于任意两位二进制位，统计它们在多少个位置取值不同。

由于异或具有按位独立性，因此我们只需要研究单个二进制位即可。

单个位的演化规律#

设某一位在左右端点分别为：

L,R

其中：

L,R\in{0,1}

只有四种情况。

情况1：00#

例如：

1
0 ? ? ? 0

第一次填充：

1
0 ? 0 ? 0

继续递推：

1
0 0 0 0 0

最终全为 0。

情况2：01#

从小规模开始观察。

k=1

1
011

k=2

1
01101

k=3

1
011011011

可以发现循环节：

1
011

情况3：10#

同理：

k=1

1
101

k=2

1
10110

k=3

1
110110110

循环节：

1
110

情况4：11#

k=1

1
110

k=2

1
11011

k=3

1
101101101

循环节：

1
101

因此对于任意二进制位，只会出现以下四种模式：

类型	左端	右端	周期模式
c0	0	0	000
c1	0	1	011
c2	1	0	110
c3	1	1	101

统计四种类型的位数即可。

统计四种类型#

设：

1
c0

表示：

1
s[i]=0,z[i]=0

的位数。

设：

1
c1

表示：

1
s[i]=0,z[i]=1

的位数。

设：

1
c2

表示：

1
s[i]=1,z[i]=0

的位数。

设：

1
c3

表示：

1
s[i]=1,z[i]=1

的位数。

按模 3 分类#

因为最终序列的模式都是长度为 3 的循环。

设：

m=2^k+1

表示总位置数。

把所有位置按照下标模 3 分类。

模0位置数量#

1
N0 = (m + 2) // 3

模1位置数量#

1
N1 = (m + 1) // 3

模2位置数量#

1
N2 = m // 3

k 的奇偶性#

观察上面的构造可以发现：

当递推层数变化时，

10 与 11 两种模式会发生交换。

因此需要分类讨论。

k 为奇数#

此时：

于是：

1
x0 = c2 + c3
2
x1 = c1 + c2
3
x2 = c1 + c3

其中：

x0：模0位置上的 1 的个数；
x1：模1位置上的 1 的个数；
x2：模2位置上的 1 的个数。

k 为偶数#

此时：

于是：

1
x0 = c2 + c3
2
x1 = c1 + c3
3
x2 = c1 + c2

计算贡献#

对于某一类位置：

若其中有

x

个二进制位为 1，

则有

n-x

个二进制位为 0。

因此该位置贡献：

x(n-x)

若该类位置共有

cnt

个，

则总贡献：

cnt\cdot x(n-x)

因此最终答案为：

N_0x_0(n-x_0) + N_1x_1(n-x_1) + N_2x_2(n-x_2)

正确性证明#

对于任意位置：

x_i y_i

表示该位置上：

选择一个值为 1 的位；
选择一个值为 0 的位；

的方案数。

因此：

x_i y_i = {(u,v)\mid bit_u\ne bit_v}

即统计不同位对数量。

由于异或运算按位独立，

每个二进制位最终只可能属于四种周期模式：

因此只需要统计四类位数：

1
c0,c1,c2,c3

即可确定任意位置上 1 的数量。

对于模 0、模 1、模 2 三类位置，

分别统计：

1
x0,x1,x2

个 1。

则对应贡献为：

x_j(n-x_j)

乘上该类位置个数即可。

故公式正确。

复杂度分析#

统计四种类型：

O(n)

其余均为常数运算。

总复杂度：

O(n)

空间复杂度：

O(1)

满足：

\sum n\le10^5

的要求。

1
for _ in range(int(input())):
2
    n, k = map(int, input().split())
3

4
    s = input().strip()
5
    z = input().strip()
6

7
    c0 = c1 = c2 = c3 = 0
8

9
    for a, b in zip(s, z):
10
        if a == '0' and b == '0':
11
            c0 += 1
12
        elif a == '0' and b == '1':
13
            c1 += 1
14
        elif a == '1' and b == '0':
15
            c2 += 1
16
        else:
17
            c3 += 1
18

19
    m = (1 << k) + 1
20

21
    N0 = (m + 2) // 3
22
    N1 = (m + 1) // 3
23
    N2 = m // 3
24

25
    if k & 1:
26
        x0 = c2 + c3
27
        x1 = c1 + c2
28
        x2 = c1 + c3
29
    else:
30
        x0 = c2 + c3
31
        x1 = c1 + c3
32
        x2 = c1 + c2
33

34
    ans = (
35
        N0 * x0 * (n - x0)
36
        + N1 * x1 * (n - x1)
37
        + N2 * x2 * (n - x2)
38
    )
39

40
    print(ans)

音乐

音乐

1102Div2-①数学②构造+数学③前后缀最大值/并查集④分治+贡献法

1102Div2-①数学②构造+数学③前后缀最大值/并查集④分治+贡献法#

A-数学#

题目重述#

性质分析#

正确性证明#

复杂度分析#

B-构造+数学#

题目重述#

思路分析#

无解情况#

正确性证明#

回文性质#

整除性质#

和为 n#

复杂度分析#

C-前后缀最大值#

题意简述#

关键性质#

水位能够达到多少？#

最优构造#

前缀最大值#

后缀最大值#

正确性证明#

引理1#

引理2#

引理3#

定理#

复杂度分析#

C-并查集#

题意重述#

物理意义#

固定一个空容器#

重要结论#

转换#

枚举高度#

并查集维护#

Easy Version 复杂度#

D-分治+贡献法#

题目大意#

思路分析#

单个位的演化规律#

情况1：00#

情况2：01#

情况3：10#

情况4：11#

统计四种类型#

按模 3 分类#

模0位置数量#

模1位置数量#

模2位置数量#

k 的奇偶性#

k 为奇数#

k 为偶数#

计算贡献#

正确性证明#

复杂度分析#

音乐

目录