洛谷 SCP-S 2026 第一轮模拟赛（提高级 C++）

（1）

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | const int N = 20, mod = 998244353;
 5 | int n, a[N][N], f[1 << N];
 6 |
 7 | int main() {
 8 |     cin >> n;
 9 |     for (int i = 0; i < n; i++)
10 |         for (int j = 0; j < n; j++)
11 |             cin >> a[i][j];
12 |     f[0] = 1;
13 |     for (int i = 0; i < (1 << n); i++)
14 |         for (int j = 0; j < n; j++)
15 |             if (i >> j & 1)
16 |                 (f[i] += 1ll * f[i ^ (1 << j)] *
17 |                          a[__builtin_popcount(i) - 1][j] % mod) %= mod;
18 |     cout << f[(1 << n) - 1];
19 |     return 0;
20 | }

保证输入的整数满足 $1\le n\le20$，$1\le a_{i,j}<998244353$，完成下面的判断题和单选题。

（2）

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | typedef long long ll;
 5 | ll len[90], dp[90][2];
 6 |
 7 | void init() {
 8 |     len[0] = 1, len[1] = 2, dp[1][1] = 1;
 9 |     for (int i = 2; i <= 86; i++) {
10 |         len[i] = len[i - 1] + len[i - 2];
11 |         int op = len[i - 1] & 1;
12 |         dp[i][0] = dp[i - 1][0] + dp[i - 2][0 ^ op];
13 |         dp[i][1] = dp[i - 1][1] + dp[i - 2][1 ^ op];
14 |     }
15 | }
16 |
17 | int solve1(int n, int p) {
18 |     string s = "0", nxt = "01", tmp;
19 |     while (nxt.length() < n)
20 |         tmp = nxt + s, s = nxt, nxt = tmp;
21 |     int ans = 0;
22 |     for (int i = p; i < n; i += 2) ans += nxt[i] - '0';
23 |     return ans;
24 | }
25 |
26 | int value(int pos) {
27 |     if (pos <= 1) return pos;
28 |     int k = 0;
29 |     while (len[k + 1] <= pos) k++;
30 |     return value(pos - len[k]);
31 | }
32 |
33 | int solve2(int n, int p) {
34 |     int ans = 0;
35 |     for (int i = p; i < n; i += 2) ans += value(i);
36 |     return ans;
37 | }
38 |
39 | ll solve3(ll n, int p) {
40 |     int k = 0; ll ans = 0;
41 |     while (len[k + 1] <= n) k++;
42 |     for (; k >= 0; k--) if (len[k] <= n)
43 |         ans += dp[k][p], n -= len[k], p ^= len[k] & 1;
44 |     return ans;
45 | }
46 |
47 | int main() {
48 |     ll n; int p;
49 |     cin >> n >> p, init();
50 |     if (n <= 1e6)
51 |         cout << solve1(n, p) << ' ' << solve2(n, p) << ' '
52 |              << solve3(n, p) << endl;
53 |     else
54 |         cout << solve3(n, p) << endl;
55 |     return 0;
56 | }

假设输入的整数满足 $1\le n\le10^{18}$，$p\in\{0,1\}$，完成下面的判断题和单选题。

（3）

 1 | #include <bits/stdc++.h>
 2 | using namespace std;
 3 |
 4 | typedef long long ll;
 5 | typedef unsigned long long ull;
 6 | const int N = 100005, M = 200005, S = 400037;
 7 | const int P = 998244353, iv2 = (P + 1) / 2;
 8 |
 9 | int n, m, w[M], sum, dep[N], ct[M], sw[M], cur[M], ans[N];
10 | ull h[N], he[M];
11 | bool vis[N];
12 | vector<pair<int, int> > G[N], T[N];
13 | mt19937_64 rnd(random_device{}());
14 |
15 | int tot, hd[S];
16 | struct node { int nxt; ull key; } mp[M];
17 | int get(ull key) {
18 |     int u = key % S;
19 |     for (int i = hd[u]; i; i = mp[i].nxt)
20 |         if (mp[i].key == key) return i;
21 |     return mp[++tot] = {hd[u], key}, hd[u] = tot;
22 | }
23 |
24 | void dfs1(int u, int p) {
25 |     vis[u] = 1;
26 |     for (auto [v, i] : G[u]) if (i ^ p) {
27 |         if (!vis[v])
28 |             dep[v] = dep[u] + 1, T[u].push_back({v, i}),
29 |             dfs1(v, i), h[u] ^= h[v], he[i] = h[v];
30 |         else if (dep[v] < dep[u])
31 |             he[i] = rnd(), h[u] ^= he[i], h[v] ^= he[i];
32 |     }
33 | }
34 |
35 | void dfs2(int u, ll c, ll b, ll b2) {
36 |     ans[u] = ((c + b * sum - (b * b + b2) % P * iv2) % P + P) % P;
37 |     for (auto [v, i] : T[u]) {
38 |         ll w = ::w[i];
39 |         if (!he[i]) {
40 |             dfs2(v, c, (b + w) % P, (b2 + w * w) % P);
41 |             continue;
42 |         }
43 |         int j = get(he[i]);
44 |         if (ct[j] == 1) dfs2(v, c, b, b2);
45 |         else {
46 |             int d = (w * (sw[j] - cur[j] * 2 - w) % P + P) % P;
47 |             cur[j] = (cur[j] + w) % P;
48 |             dfs2(v, (c + d) % P, b, b2);
49 |             cur[j] = (cur[j] - w + P) % P;
50 |         }
51 |     }
52 | }
53 |
54 | int main() {
55 |     ios::sync_with_stdio(0), cin.tie(0);
56 |     cin >> n >> m;
57 |     for (int i = 1, u, v; i <= m; i++)
58 |         cin >> u >> v >> w[i], sum = (sum + w[i]) % P,
59 |         G[u].push_back({v, i}), G[v].push_back({u, i});
60 |     dfs1(1, 0);
61 |     for (int i = 1, j; i <= m; i++) if (he[i])
62 |         j = get(he[i]), ct[j]++, sw[j] = (sw[j] + w[i]) % P;
63 |     dfs2(1, 0, 0, 0);
64 |     for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
65 | }

假设输入的整数满足 $3\le n\le10^5$，$2\le m\le2\times10^5$，$0\le w_i<998244353$，且输入的图连通、无自环或重边，不考虑异或哈希值的冲突，完成下面的判断题和单选题。

（1）（线性筛）给定一个正整数 $n$，要对于 $i=1\sim n$求出$i^i$取模 998244353 的结果。满足$1\le n\le10^7$。你需要设计一个 $O(n)$ 的算法。

提示：在线性筛的过程中同步计算 $f_i=i^i\bmod998244353$。质数可以直接使用快速幂；合数被筛到时，尝试将 $f_{pq}$表示成$f_p$与$f_q$ 的幂的乘积，从而由已有结果完成转移。

令 $B=\lfloor\sqrt n\rfloor$。$f_p$的幂可将指数按$B$ 分块并预处理；$f_q$的幂利用对于枚举的$q$，指数递增的性质，根据相邻质数之差增量维护。总时间复杂度即可达到 $O(n)$。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 5, SN = (int)sqrt(N) + 5, mod = 998244353;
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ull * res * a % mod;
        ①
        b >>= 1;
    }
    return res;
}
int bsgs1[SN][SN], bsgs2[SN][SN];
bool vis[N];
int f[N], pr[N / 10], len;
int powers[N], S;
int main() {
    int n;
    scanf("%d", &n);
    f[1] = 1;
    const int B = sqrt(n);
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pr[++len] = i, f[i] = qpow(i, i);
            if (i <= B) {
                bsgs1[i][0] = 1;
                for (int j = 1; j <= B; j++)
                    bsgs1[i][j] = 1ull * bsgs1[i][j - 1] * f[i] % mod;
                bsgs2[i][0] = 1;
                for (int j = 1; j <= B; j++)
                    ②
            }
        }
        powers[0] = 1;
        int cur = 1, gap = 0;
        for (int j = 1; j <= len && i * pr[j] <= n; j++) {
            vis[pr[j] * i] = 1;
            int now = pr[j] - pr[j - 1];
            ③
                powers[ex] = 1ull * powers[ex - 1] * f[i] % mod;
            gap = max(gap, now);
            cur = 1ull * cur * powers[now] % mod;
            ④
            if (⑤)
                break;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", f[i]);
    return 0;
}