ABC460-多源BFS+欧几里得#

AtCoder Beginner Contest 460 - AtCoder

Easy：A、B、C

Hard：D、E

D-多源BFS

题意：

有一个H×W的网格，每个格子初始为白色(.)或黑色(#)。进行10^100次操作，每次操作同时对所有格子应用以下规则：

白色格子：如果其8邻域内至少有一个黑色格子，则变为黑色
黑色格子：变为白色

求10^100次操作后每个格子的颜色。

题解：

第一步：先进行一次特殊操作

不直接对原图进行BFS
而是先将原图进行一次变换：只有那些初始为白色且8邻域中有黑色的格子才被标记为黑色
这一步等价于”去掉孤立的黑色，只保留边界”

第二步：对变换后的图进行多源BFS

以变换后的黑色格子为源点
计算每个格子到最近黑色格子的切比雪夫距离
距离为偶数 → 白色(.)，距离为奇数 → 黑色(#)

原始操作定义：

白色→黑色：当且仅当8邻域有黑色
黑色→白色：无条件

10^100次操作后（偶数次），相当于：

首先”过滤”掉那些会立即变白的初始黑色（因为没有白色邻居的黑色会变成孤立的白色）
然后黑色像”波”一样向外扩散，每次扩散一层
偶数次操作后，波前扩散了偶数层，所以距离奇偶性决定最终颜色

想象黑色是”波源”：

第1步：原黑色变白，它们周围的白色变黑（波向外扩散1层）
第2步：新黑色变白，它们周围的白色变黑（波再扩散1层）
…
第k步：波扩散了k层

10^100是偶数，所以：

初始黑色的”波”扩散了偶数层
距离波源奇数层的格子最终是黑色
距离波源偶数层的格子最终是白色

但初始的孤立黑色（没有白色邻居）在第1步就变白了，不会成为波源。所以第一步要预处理，只保留有白色邻居的黑色作为波源。

1
from collections import deque
2

3
def solve():
4
    H, W = map(int, input().split())
5
    grid = [list(input().strip()) for _ in range(H)]
6

7
    # 8个方向
8
    dx = [1, 0, -1, 0, 1, -1, -1, 1]
9
    dy = [0, 1, 0, -1, 1, 1, -1, -1]
10

11
    def in_bounds(x, y):
12
        return 0 <= x < H and 0 <= y < W
13

14
    # 第一步：预处理，只保留有白色邻居的黑色
15
    new_grid = [['.'] * W for _ in range(H)]
16
    for i in range(H):
17
        for j in range(W):
18
            if grid[i][j] == '#':
19
                # 检查8邻域是否有白色
20
                for d in range(8):
21
                    nx, ny = i + dx[d], j + dy[d]
22
                    if in_bounds(nx, ny) and grid[nx][ny] == '.':
23
                        new_grid[nx][ny] = '#'
24

25
    grid = new_grid
26

27
    # 第二步：多源BFS计算距离
28
    INF = 10**9
29
    dist = [[INF] * W for _ in range(H)]
30
    q = deque()
31

32
    for i in range(H):
33
        for j in range(W):
34
            if grid[i][j] == '#':
35
                dist[i][j] = 0
36
                q.append((i, j))
37

38
    while q:
39
        x, y = q.popleft()
40
        for d in range(8):
41
            nx, ny = x + dx[d], y + dy[d]
42
            if in_bounds(nx, ny) and dist[nx][ny] == INF:
43
                dist[nx][ny] = dist[x][y] + 1
44
                q.append((nx, ny))
45

46
    # 第三步：根据距离奇偶性输出
47
    for i in range(H):
48
        row = []
49
        for j in range(W):
50
            if dist[i][j] % 2 == 0:
51
                row.append('.')
52
            else:
53
                row.append('#')
54
        print(''.join(row))
55

56
solve()

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <string.h>
4

5
#define MAXN 1000005
6

7
typedef struct {
8
    int x, y;
9
} Point;
10

11
Point q[MAXN];
12
int head, tail;
13

14
int H, W;
15
char grid[MAXN];
16
char new_grid[MAXN];
17
int dist[MAXN];
18

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

22
int idx(int i, int j) {
23
    return i * W + j;
24
}
25

26
int in_bounds(int x, int y) {
27
    return x >= 0 && x < H && y >= 0 && y < W;
28
}
29

30
void push(int x, int y) {
31
    q[tail].x = x;
32
    q[tail].y = y;
33
    tail++;
34
}
35

36
Point pop() {
37
    return q[head++];
38
}
39

40
int empty() {
41
    return head == tail;
42
}
43

44
int main() {
45
    scanf("%d %d", &H, &W);
46

47
    for (int i = 0; i < H; i++) {
48
        scanf("%s", grid + i * W);
49
    }
50

51
    // 第一步：预处理
52
    memset(new_grid, '.', sizeof(new_grid));
53

54
    for (int i = 0; i < H; i++) {
55
        for (int j = 0; j < W; j++) {
56
            if (grid[idx(i, j)] == '#') {
57
                for (int d = 0; d < 8; d++) {
58
                    int nx = i + dx[d];
59
                    int ny = j + dy[d];
60
                    if (in_bounds(nx, ny) && grid[idx(nx, ny)] == '.') {
61
                        new_grid[idx(nx, ny)] = '#';
62
                    }
63
                }
64
            }
65
        }
66
    }
67

68
    memcpy(grid, new_grid, sizeof(grid));
69

70
    // 第二步：BFS
71
    memset(dist, -1, sizeof(dist));
72
    head = tail = 0;
73

74
    for (int i = 0; i < H; i++) {
75
        for (int j = 0; j < W; j++) {
76
            if (grid[idx(i, j)] == '#') {
77
                dist[idx(i, j)] = 0;
78
                push(i, j);
79
            }
80
        }
81
    }
82

83
    while (!empty()) {
84
        Point p = pop();
85
        int x = p.x, y = p.y;
86

87
        for (int d = 0; d < 8; d++) {
88
            int nx = x + dx[d];
89
            int ny = y + dy[d];
90

91
            if (in_bounds(nx, ny) && dist[idx(nx, ny)] == -1) {
92
                dist[idx(nx, ny)] = dist[idx(x, y)] + 1;
93
                push(nx, ny);
94
            }
95
        }
96
    }
97

98
    // 第三步：输出
99
    for (int i = 0; i < H; i++) {
100
        for (int j = 0; j < W; j++) {
101
            int id = idx(i, j);
102
            if (dist[id] % 2 == 0) {
103
                printf(".");
104
            } else {
105
                printf("#");
106
            }
107
        }
108
        printf("\n");
109
    }
110

111
    return 0;
112
}

E-欧几里得

题意：

定义 concat(x,y) 为将x和y的十进制表示拼接起来形成的整数。例如 concat(123,45) = 12345。

给定N和M，求有多少对正整数(x,y)，满足：

1 ≤ x ≤ N
1 ≤ y ≤ N
concat(x,y) ≡ x + y (mod M)

有T个测试用例，需要对998244353取模。

题解：

数学推导：

数学公式推导

一、基本定义与展开

设 $y$ 的十进制位数为 $k$ ，即 $10^{k-1} \leq y < 10^k$

拼接公式：
$\text{concat}(x,y) = x \cdot 10^k + y$
二、条件方程
$\text{concat}(x,y) \equiv x + y \pmod M$
代入拼接公式：
$x \cdot 10^k + y \equiv x + y \pmod M$
三、方程化简

两边同时减去 $y$ ：
$x \cdot 10^k \equiv x \pmod M$
移项：
$x \cdot 10^k - x \equiv 0 \pmod M$
提取公因子 $x$ ：
$x(10^k - 1) \equiv 0 \pmod M$
四、模方程的标准形式
$x(10^k - 1) \equiv 0 \pmod M$
这等价于：
$M \mid x(10^k - 1)$
即 $M$ 整除 $x(10^k - 1)$ 。

五、最大公约数化简

设：
$d_k = \gcd(M, 10^k - 1)$
由最大公约数定义，存在整数 $u_k, v_k$ 满足：
$M = d_k \cdot u_k, \quad 10^k - 1 = d_k \cdot v_k$
且 $\gcd(u_k, v_k) = 1$ 。

六、整除条件转化
$M \mid x(10^k - 1) \iff d_k \cdot u_k \mid x \cdot d_k \cdot v_k$
两边约去 $d_k$ ：
$u_k \mid x \cdot v_k$
七、互质性质的应用

由于 $\gcd(u_k, v_k) = 1$ ，由欧几里得引理：
$u_k \mid x \cdot v_k \text{ 且 } \gcd(u_k, v_k) = 1 \implies u_k \mid x$
八、必要条件
$u_k \mid x$
其中：
$u_k = \frac{M}{d_k} = \frac{M}{\gcd(M, 10^k - 1)}$
记 $g_k = u_k = \frac{M}{\gcd(M, 10^k - 1)}$ ，则：
$x \equiv 0 \pmod{g_k}$
九、x的解集
$x \in \{g_k, 2g_k, 3g_k, \ldots\} \cap [1, N]$
数量：
$C_x(k) = \left\lfloor \frac{N}{g_k} \right\rfloor$
十、y的约束

$y$ 是 $k$ 位数且不超过 $N$ ：
$10^{k-1} \leq y \leq \min(10^k - 1, N)$
记：
$L_k = 10^{k-1}, \quad R_k = \min(10^k - 1, N)$
数量：
$C_y(k) = \max(0, R_k - L_k + 1)$
十一、总答案

第 $k$ 组的贡献：
$A_k = C_x(k) \cdot C_y(k)$
总答案（模 $998244353$ ）：
$\text{Ans} = \sum_{k=1}^{\lfloor \log_{10} N \rfloor + 1} C_x(k) \cdot C_y(k) \pmod{998244353}$
十二、公式总结
$\boxed{\text{Ans} = \sum_{k=1}^{\lfloor \log_{10} N \rfloor + 1} \left\lfloor \frac{N}{M / \gcd(M, 10^k - 1)} \right\rfloor \cdot \max(0, \min(10^k - 1, N) - 10^{k-1} + 1)}$

1
MOD = 998244353
2
def gcd(a, b):
3
    while b:
4
        a, b = b, a % b
5
    return a
6
T = int(input())
7
# 预计算10的幂
8
pow10 = [1]
9
for i in range(1, 19):
10
    pow10.append(pow10[-1] * 10)
11
for _ in range(T):
12
    N, M = map(int, input().split())
13
    # N的位数
14
    len_N = len(str(N))
15
    ans = 0
16
    for k in range(1, len_N + 1):
17
        # 计算gcd和g
18
        d = gcd(M, pow10[k] - 1)
19
        g = M // d
20
        # x的个数
21
        cnt_x = N // g
22
        if cnt_x == 0:
23
            continue
24
        # y的范围：k位数，且≤N
25
        L = pow10[k - 1]  # 最小k位数
26
        R = min(N, pow10[k] - 1)  # 最大k位数
27
        if L > R:
28
            continue
29
        cnt_y = R - L + 1
30
        ans = (ans + cnt_x % MOD * (cnt_y % MOD)) % MOD
31
    print(ans % MOD)

音乐

音乐

ABC460-多源BFS+欧几里得#

音乐

目录