2025 ICPC Asia Manila Regional（2025 ICPC 亚洲菲律宾马尼拉）——vp 中通过题目总结（把题目对取模的要求用注释写在末尾）

题目 H. Prime Topology

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

样例输出

1
2
3

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, 3, 6\}$ ：任意两元素差值分别为 $|1-3|=2$ ， $|3-6|=3$ ， $|1-6|=5$ ，均为素数。
$\{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。

注意，这道题目的这个询问量特别高，因此要把东西都处理出来。

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

源代码

/**
 * 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

题目描述
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 也会尝试向相同的方向移动一步。移动规则如下：

如果 Hero A 的移动方向被障碍物或网格边界阻挡，那么 Hero A 无法移动，此时 Hero A 和 Clone B 都不会移动。
如果 Hero A 可以移动，但 Clone B 的移动方向被障碍物或边界阻挡，则 Hero A 会正常移动一步，而 Clone B 会停留在原地。
如果两者前方均无阻挡，则两人都正常向该方向移动一步。

求使得 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

样例输出

1
2

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

2025 CCPC 郑州——G. Plus Xor（ n 方复杂度，要想到记忆化 bfs 搜索）（记忆化 bfs 最重要的就是确定状态）（异或 b 只能改变 __lg(b)+1 位）（采用塞入的时候确定答案的，应该采用一 check/is_find_ans 函数，确保初始塞入情况和中途塞入情况采用同样的判断逻辑）

这道题目比这个 G 简单，比较容易发现：

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

源代码

/**
 * 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

源代码

题目4

源代码

题目5

源代码