我们计算出 \([1,n]\) 每个位置的 \(\frac{m}{mul_i}\) ，即每个位置其前缀质因子都存在数的个数，把他们乘法原理乘在一起，就代表长度为 \(n\) 明确的数列的个数 \(\prod_{i=1}^n \frac{m}{mul_i}\) ，因为每个位置组合的都是包含所有前缀质因子，除了在 \(1\) 处删除，其他地方 \(gcd(i,a[i]) \neq 1\) 不能删 。
最后对于长度 \(n\) 的数列，所有情况一共 \(m^n\) 种，所以最后不明确的数列个数为 \(m^n - \prod_{i=1}^n \frac{m}{mul_i}\)。
我们对 \([1,n]\) 所有长度的答案求和，有 \(ans = \sum_{i=1}^n (m^i - \prod_{j=1}^i \frac{m}{mul_j})\) ，注意到 \(m^i\) 、 \(mul_i\) 以及 \(\prod_{j=1}^i \frac{m}{mul_j}\) 可以从 \(1\) 递推，过程中加到答案里即可 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;const int mod = 998244353;int cnt;int vis[300007];int prime[300007] = { 1 };void euler_screen(int n) {for (int i = 2;i <= n;i++) {if (!vis[i]) prime[++cnt] = i;for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {vis[i * prime[j]] = 1;if (i % prime[j] == 0) break;}}}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;ll m;cin >> n >> m;euler_screen(n);int base = 1, mul = 1, ans = 0;llfact = 1;for (int i = 1;i <= n;i++) {if (!vis[i] && fact <= m) fact *= i;base = 1LL * m % mod * base % mod;mul = 1LL * m / fact % mod * mul % mod;ans = ((ans + base) % mod - mul + mod) % mod;}cout << ans << '\n';return 0;}E题解知识点：bfs 。
思考明白了就是一个很简单的01bfs 。
注意到我们需要让从第一行到第 \(n\) 行不存在路径，反过来想就是需要一条从第一列到第 \(m\) 列连续的横向仙人掌路径，才能阻挡所有竖向路径，这个路径要求花费最少，于是问题转化问从第一列出发到第 \(m\) 列的仙人掌最短路，起点是第一列所有点，有仙人掌的格子花费为 \(0\) ，没有的花费是 \(1\)。
搜索过程中用一个 map 记录前驱坐标即可复原路径 。
这道题主要在这个思考和转化的过程 。
时间复杂度 \(O(nm)\)
空间复杂度 \(O(nm)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;const int dir[4][2] = { {1,1},{1,-1},{-1,1},{-1,-1} };const int dir2[4][2] = { {1,0},{0,1},{0,-1},{-1,0} };bool solve() {int n, m;cin >> n >> m;vector<vector<char>> dt(n + 1, vector<char>(m + 1));for (int i = 1;i <= n;i++)for (int j = 1;j <= m;j++)cin >> dt[i][j];auto check = [&](int x, int y) {bool ok = 1;for (int i = 0;i < 4;i++) {int xx = x + dir2[i][0];int yy = y + dir2[i][1];if (xx <= 0 || xx > n || yy <= 0 || yy > m) continue;ok &= dt[xx][yy] != '#';}return ok;};deque<pair<int, int>> dq;vector<vector<bool>> vis(n + 1, vector<bool>(m + 1));map<pair<int, int>, pair<int, int>> pre;pair<int, int> p = { 0,0 };for (int i = 1;i <= n;i++) {if (dt[i][1] == '#') dq.push_front({ i,1 }), vis[i][1] = 1, pre[{i, 1}] = { 0,0 };else if (check(i, 1)) dq.push_back({ i,1 }), vis[i][1] = 1, pre[{i, 1}] = { 0,0 };}while (!dq.empty()) {auto [x, y] = dq.front();dq.pop_front();if (y == m) {p = { x,y };break;}for (int i = 0;i < 4;i++) {int xx = x + dir[i][0];int yy = y + dir[i][1];if (xx <= 0 || xx > n || yy <= 0 || yy > m || vis[xx][yy]) continue;if (dt[xx][yy] == '#') dq.push_front({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y };else if (check(xx, yy)) dq.push_back({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y };}}auto &[px, py] = p;if (!px && !py) return false;cout << "YES" << '\n';while (px || py) {dt[px][py] = '#';p = pre[{px, py}];}for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {cout << dt[i][j];}cout << '\n';}return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << "NO" << '\n';}return 0;}