2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——vp 中通过题目总结（把题目对取模的要求用注释写在末尾） · znzryb
## 题目 H. Prime Topology
[https://codeforces.com/gym/106262/problem/H](https://codeforces.com/gym/106262/problem/H)
**题目描述**
定义集合 $U_n = \{1, 2, 3, \dots, n\}$。
如果 $U_n$ 的一个子集 $S$ 满足：对于 $S$ 中任意两个不同的元素 $a$ 和 $b$，它们的绝对差 $|a - b|$ 都是素数，则称该子集 $S$ 为**素数间距的（prime-spaced）**。
给定正整数 $n$ 和 $k$，求在 $U_n$ 中，大小为 $k$ 的素数间距子集的数量。
由于答案可能很大，请输出其对 104206969 取模后的结果。
本题包含多组独立测试数据。
**输入格式**
第一行包含一个整数 $T$（$1 \le T \le 2 \times 10^5$），表示测试数据的组数。
接下来 $T$ 行，每行包含两个由空格分隔的整数 $n$ 和 $k$（$1 \le k \le n \le 10^7$）。
**输出格式**
对于每组测试数据，输出一行，表示大小为 $k$ 的素数间距子集的数量对 104206969 取模的值。
**样例输入**
```
3
5 2
6 3
10000000 10000000
```
**样例输出**
```
5
2
0
```
**样例解释**
对于第一组样例 $n=5, k=2$：
$U_5 = \{1, 2, 3, 4, 5\}$，要求找出大小为 2 且元素差值的绝对值为素数的子集。
差值为 2（素数）的子集有：$\{1, 3\}, \{2, 4\}, \{3, 5\}$
差值为 3（素数）的子集有：$\{1, 4\}, \{2, 5\}$
总共有 5 个满足条件的子集，故输出 5。
对于第二组样例 $n=6, k=3$：
$U_6 = \{1, 2, 3, 4, 5, 6\}$，要求找出大小为 3 且任意两个元素差值的绝对值均为素数的子集。
满足条件的子集仅有以下 2 个：
1. $\{1, 3, 6\}$：任意两元素差值分别为 $|1-3|=2$，$|3-6|=3$，$|1-6|=5$，均为素数。
1. $\{1, 4, 6\}$：任意两元素差值分别为 $|1-4|=3$，$|4-6|=2$，$|1-6|=5$，均为素数。
总共有 2 个满足条件的子集，故输出 2。
对于第三组样例 $n=10000000, k=10000000$：
要求选出大小等于全集的子集，即只能选择集合本身。显然该集合中包含了差值为 1 的元素对（如 1 和 2，且 1 不是素数），因此不存在满足条件的子集，故输出 0。
首先要注意到，**除了 2 以外所有的素数都是奇数，奇数+奇数就是偶数一定是可以被除的**。所以说只能是 2+另一素数+2。
注意，这道题目的这个询问量特别高，因此要把东西都处理出来。
```cpp
if (K==1) {
cout<<N<<"\n";
return;
}
ll ans=0;
// 除了 2 以外所有的素数都是奇数，奇数+奇数就是偶数一定是可以被除的
if (K==2) {
ans=N*cnt_prime[N]-pre_sum[N];
ans%=mod;
if (ans<0) {
ans+=mod;
}
cout<<ans<<"\n";
return;
}
if (K==3) {
ans=N*cnt_prime_add2[N-2]*2-pre_sum_add2[N-2];
ans%=mod;
if (ans<0) {
ans+=mod;
}
cout<<ans<<"\n";
return;
}
if (K==4) {
// 只有一个数，就是 3。
for (auto p:p_add4_is_p) {
ll len=p+2+2;
if (len>=N) {
break;
}
// if (minp[p+2+2]==p+2+2 && minp[p+2]==p+2) {
ans+=(N-len);
ans%=mod;
// }
}
cout<<ans<<"\n";
return;
}
if (K>=5) {
cout<<0<<"\n";
return;
}
```
AC
[https://codeforces.com/gym/106262/submission/365350177](https://codeforces.com/gym/106262/submission/365350177)
::: 源代码
```cpp
/**
* Problem: H. Prime Topology
* Contest: 2025 ICPC Asia Manila Regional
* Judge: Codeforces
* URL: https://codeforces.com/gym/106262/problem/H
* Created: 2026-03-04 19:32:02
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e7+100/*, INF = (1ll<<61)-1*/;
static constexpr ll mod = 104206969;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
// minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
// ll minp[MAXN+100];
vector<ll> minp,primes,p_add4_is_p={3};
vector<ll> pre_sum,pre_sum_add2,cnt_prime,cnt_prime_add2;
void sieve(ll n){
minp.resize(n+5);
pre_sum.resize(n+5);
pre_sum_add2.resize(n+5);
cnt_prime.resize(n+5);
cnt_prime_add2.resize(n+5);
// minp[1]=1; // 加了这句话可能把 1 误判成素数，要小心
for(int i=2;i<=n;++i){
if(minp[i]==0){ // 是素数
minp[i]=i;
primes.push_back(i);
}
for(auto p:primes){
if(i*p>n){ // 超范围了
break;
}
minp[i*p]=p;
// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
// i * p_next = (p * k) * p_next 最小的应该是p
if(p==minp[i]){
break;
}
}
}
for (int i=2;i<=n;++i) {
pre_sum[i]=pre_sum[i-1];
cnt_prime[i]=cnt_prime[i-1];
pre_sum_add2[i]=pre_sum_add2[i-1];
cnt_prime_add2[i]=cnt_prime_add2[i-1];
if (minp[i]==i) {
pre_sum[i]+=i;
pre_sum[i]%=mod;
cnt_prime[i]++;
if (minp[i+2]==i+2) {
pre_sum_add2[i]+=(i+2)*2;
pre_sum_add2[i]%=mod;
cnt_prime_add2[i]++;
}
}
}
// for (auto p:primes) {
// if (minp[p+2]==p+2) {
// p_add2_is_p.push_back(p);
// if (minp[p+4]==p+4) {
// p_add4_is_p.push_back(p);
// }
// }
// }
}
void Solve() {
ll N,K;
cin >> N >> K;
if (K==1) {
cout<<N<<"\n";
return;
}
ll ans=0;
// 除了 2 以外所有的素数都是奇数，奇数+奇数就是偶数一定是可以被除的
if (K==2) {
// for (auto p:primes) {
// if (p>=N) {
// break;
// }
// ans+=N-p;
// ans%=mod;
// }
ans=N*cnt_prime[N]-pre_sum[N];
ans%=mod;
if (ans<0) {
ans+=mod;
}
cout<<ans<<"\n";
return;
}
if (K==3) {
// for (auto p:p_add2_is_p) {
// ll len=p+2;
// if (len>=N) {
// break;
// }
// // if (minp[p+2]==p+2) {
// ans+=(N-len)*2;
// ans%=mod;
// // }
// }
ans=N*cnt_prime_add2[N-2]*2-pre_sum_add2[N-2];
ans%=mod;
if (ans<0) {
ans+=mod;
}
cout<<ans<<"\n";
return;
}
if (K==4) {
// 只有一个数，就是 3。
for (auto p:p_add4_is_p) {
ll len=p+2+2;
if (len>=N) {
break;
}
// if (minp[p+2+2]==p+2+2 && minp[p+2]==p+2) {
ans+=(N-len);
ans%=mod;
// }
}
cout<<ans<<"\n";
return;
}
if (K>=5) {
cout<<0<<"\n";
return;
}
// modulo 104206969
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
sieve(MAXN);
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106262/submission/365350177
_______________[ Stress test, testcase 18 INPUT ]_______________
1
10 4
_______________[ Stress test, testcase 18 OUTPUT]_______________
9
expected:3
*/
```
:::
## 题目 E. Long Distance Examination（远程操作克隆机器人，两人在不同迷宫中，B 尽力复刻 A 的所有操作）
[https://codeforces.com/gym/106262/problem/E](https://codeforces.com/gym/106262/problem/E)
**题目描述**
**Hero A 在网格 A 中，他正在远程控制位于网格 B 中的克隆人 Clone B 走迷宫**。
两个网格的大小均为 $r \times c$。网格中包含空地（`.`）、障碍物（`X`）、起点（`S`）和终点（`D`）。起点 `S` 在两个网格中各出现一次，分别表示 Hero A 和 Clone B 的初始位置；终点 `D` 只在网格 B 中出现一次，表示 Clone B 需要到达的目的地。
Hero A 可以向上下左右四个方向移动，每次一步。他每尝试向某个方向移动一步，Clone B 也会**尝试**向相同的方向移动一步。**移动规则如下**：
1. 如果 Hero A 的移动方向被障碍物或网格边界阻挡，那么 Hero A 无法移动，此时 Hero A 和 Clone B **都不会移动**。
1. 如果 Hero A 可以移动，但 Clone B 的移动方向被障碍物或边界阻挡，则 Hero A 会正常移动一步，而 Clone B 会**停留在原地**。
1. 如果两者前方均无阻挡，则两人都正常向该方向移动一步。
求使得 Clone B 到达终点 `D`，Hero A 最少需要移动的步数。如果无法到达，输出 `-1`。
**输入格式**
第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。
对于每组测试数据：
第一行包含两个由空格分隔的正整数 $r$ 和 $c$（$1 \le r, c \le 100, 2 \le r \times c \le 1000$）。
接下来 $r$ 行，每行包含一个长度为 $c$ 的字符串，表示网格 A 的状态。
再接下来 $r$ 行，每行包含一个长度为 $c$ 的字符串，表示网格 B 的状态。
字符仅包含 `.`、`X`、`S` 和 `D`。
**输出格式**
对于每组测试数据，输出一行，包含一个整数，表示最少需要的步数。如果不可达，则输出 `-1`。
**样例输入**
```
2
5 5
S....
.....
.....
.....
.....
....S
.....
.....
.....
....D
7 5
XXXXX
XXXXX
XS..X
X.X.X
X...X
XXXXX
XXXXX
XXXXX
XS..X
XXX.X
X...X
XXX.X
XD..X
XXXXX
```
**样例输出**
```
4
14
```
**样例解释**
对于第一组样例：
网格 A 的起点在左上角，网格 B 的起点在右上角，终点在右下角。尽管 Hero A 和 Clone B 的起点不同，由于两个网格中间都没有障碍物，Hero A 只需要一直向下走 4 步，Clone B 也会无阻挡地同时向下走 4 步到达终点。最少步数为 4。
对于第二组样例：
Hero A 位于网格 A 的 `(3, 2)`，而 Clone B 位于网格 B 的 `(2, 2)`。由于网格 B 中有较多障碍物阻挡了直接向下走向终点的路径，Hero A 可以利用“自己移动而 Clone B 被墙挡住留在原地”的机制来调整两者之间的相对位置。
最优解是 Hero A 在网格 A 中顺时针绕行：
- Hero A 走一圈（右右下下左左上上，共 8 步）回到原点，此时 Clone B 会在跟随移动的过程中被障碍物卡住，最终停留在网格 B 的 `(4, 2)` 位置。
- 随后 Hero A 继续走第二圈（右右下下左左，走 6 步时），Clone B 会顺势移动到 `(6, 2)` 的终点 `D`。
总共花费 $8 + 6 = 14$ 步，使得 Clone B 到达终到达终点。
比较像这道题目 2025 CCPC 郑州的这道题目。
[https://qoj.ac/contest/2661/problem/15307](https://qoj.ac/contest/2661/problem/15307)
[2025 CCPC 郑州——G. Plus Xor（ n 方复杂度，要想到记忆化 bfs 搜索）（记忆化 bfs 最重要的就是确定状态）（异或 b 只能改变 __lg(b)+1 位）（采用塞入的时候确定答案的，应该采用一 check/is_find_ans 函数，确保初始塞入情况和中途塞入情况采用同样的判断逻辑）](/2026/03/04/20260304-51830021)
这道题目比这个 G 简单，比较容易发现：
```cpp
struct XY_AB{
ll xa,ya,xb,yb;
bool operator<(const XY_AB &o) const {
if (xa!=o.xa) return xa<o.xa;
if (ya!=o.ya) return ya<o.ya;
if (xb!=o.xb) return xb<o.xb;
return yb<o.yb;
}
};
```
一个完整状态由 A 的位置和这个 B 的位置确定，我们只需要对这一状态进行记忆化 bfs 即可。
AC
[https://codeforces.com/gym/106262/submission/365338227](https://codeforces.com/gym/106262/submission/365338227)
::: 源代码
```cpp
/**
* Problem: E. Long Distance Examination
* Contest: 2025 ICPC Asia Manila Regional
* Judge: Codeforces
* URL: https://codeforces.com/gym/106262/problem/E
* Created: 2026-03-04 18:35:58
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct XY_AB_STEP{
ll xa,ya,xb,yb,step;
};
struct XY_AB{
ll xa,ya,xb,yb;
bool operator<(const XY_AB &o) const {
if (xa!=o.xa) return xa<o.xa;
if (ya!=o.ya) return ya<o.ya;
if (xb!=o.xb) return xb<o.xb;
return yb<o.yb;
}
};
/* -> (Right, Down, Left, Up)
| |
<-
*/
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
ll N_i,M_j;
bool check(vector<vector<char>> &A,ll i,ll j) {
if (i<1 || i>N_i) {
return false;
}
if (j<1 || j>M_j) {
return false;
}
if (A[i][j]=='X') {
return false;
}
return true;
}
void Solve() {
cin >> N_i >> M_j;
vector<vector<char>> A(N_i+2,vector<char>(M_j+2)),B(N_i+2,vector<char>(M_j+2));
ll sax,say,sbx,sby,ebx,eby;
for (int i=1;i<=N_i;++i) {
for (int j=1;j<=M_j;++j) {
cin>>A[i][j];
if (A[i][j]=='S') {
tie(sax,say)=tuple(i,j);
}
}
}
for (int i=1;i<=N_i;++i) {
for (int j=1;j<=M_j;++j) {
cin>>B[i][j];
if (B[i][j]=='S') {
tie(sbx,sby)=tuple(i,j);
}else if (B[i][j]=='D') {
tie(ebx,eby)=tuple(i,j);
}
}
}
// bfs
do {
queue<XY_AB_STEP> q;
q.push({sax,say,sbx,sby,0});
set<XY_AB> memo;
ll idx=0;
while (!q.empty()) {
auto [ax,ay,bx,by,step]=q.front();
memo.insert({ax,ay,bx,by});
// ++idx;
// if (idx>M_j*N_i*M_j*N_i) {
// cout<<-1<<"\n";
// return;
// }
q.pop();
for (int i=0;i<4;++i) {
ll to_ax=ax+dx[i],to_ay=ay+dy[i],to_bx=bx+dx[i],to_by=by+dy[i];
if (!check(A,to_ax,to_ay)) {
continue;
}
if (check(B,to_bx,to_by)) {
if (to_bx==ebx && to_by==eby) {
cout<<step+1<<"\n";
return;
}
if (memo.contains({to_ax,to_ay,to_bx,to_by})) {
continue;
}
memo.insert({to_ax,to_ay,to_bx,to_by});
q.push({to_ax,to_ay,to_bx,to_by,step+1});
}else {
if (memo.contains({to_ax,to_ay,bx,by})) {
continue;
}
memo.insert({to_ax,to_ay,bx,by});
q.push({to_ax,to_ay,bx,by,step+1});
}
}
}
cout<<-1<<"\n";
return;
}while (false);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106262/submission/365338227
*/
```
:::
## 题目3
::: 源代码
```cpp
```
:::
## 题目4
::: 源代码
```cpp
```
:::
## 题目5
::: 源代码
```cpp
```
:::