题解：P11626 [迷宫寻路 Round 3] 七连击

high_sky · 2025-11-20 21:42:03 · 题解

题目概述

有一个长度为 n 的序列，将这个序列砍 7 刀，分成了 8 个部分，取前 7 个部分进行讨论。

对于每个部分，贡献为这一段的最大公约数。

求所有情况的贡献和并对 998244353 取模。

数据范围：1\leq n\leq 10^5,0\leq a_i\leq 10^9。

分析

真服了，那个 a_i=0 直接耗了我好久，看了 60 分求调代码的那个贴子才恍然大悟，而且那个贴子下面有数据。

不知道为什么你们一眼看到的就是动态规划，本蒟蒻只会组合计数的方法。

首先不难想到把无关项提到前面去，那么通过这个不难得出来我们需要知道一个区间在第 k(1\leq k\leq 7) 个块时对答案的贡献。

也就是说我们枚举这个区间和它在第几个块，组合数计算就行了。

对于 k=1 我是特殊处理的。

考虑 k\geq 2 的情况，你这里可能需要注意一下枚举区间的范围。

由于我们枚举出了这个区间（假设为 [i,j]）以及知道它在第几个块，那么我们可以把它对答案的贡献系数分成左边分成 k-1 块的方案以及剩下的部分分成其它块的答案。

考虑左边的，由于已经枚举了左端点，所以就是算切了一刀，于是左边的贡献就是 \binom{i-2}{k-2}，因为只有 i-1 个数最右边还被切过了，因此只剩下 i-2 个空给 k-2 次切的机会。

考虑右边的，十分类似，但是这里我们没有多切一刀，因为你可以看作这个是属于前面的，因此右边的贡献就是 \binom{n-j}{7-k}。

于是我们的答案实际上就是（k=1 特殊讨论）：

于是得到了我们的 \mathcal{O}(7n^2) 代码：

int ans = 0;
int t = 0;
for (int i = 1;i <= n - 6;i ++) {
    t = gcd(t,a[i]);
    int rest = n - i;
    ans = (ans + C(rest,6) * t % mod) % mod;
}
for (int k = 2;k <= 7;k ++)
    for (int i = k;i <= n - (7 - k);i ++) {
        int t = 0;
        for (int j = i;j <= n - (7 - k);j ++) {
            t = gcd(t,a[j]);
            ans = (ans + C(i - 2,k - 2) * C(n - j,7 - k) % mod * t % mod) % mod;
        }
    }

很短，但是可以拿 40 分。

接下来考虑优化，我们注意到我们的 j 右移的时候这个当前的最大公约数是单调不增的，而且相同的部分一定是一段一段的。

而且有一个经典的结论就是：前缀（或者是后缀）的最大公约数的种类个数是 \mathcal{O}(\log V) 级别的，其中 V 是值域。

这个证明也很简单，因为你加进来一个数求最大公约数的时候至少是减半的。

也就是说我们不需要枚举 j，我们只需要得到这一段一段的为相同最大公约数的区间即可，你还需要预处理一个前缀和，是关于后面的那个组合数的前缀和，之后直接计算就行。

我这里采用了二分找位置，时间复杂度可能有点大，区间求最大公约数可以直接用ST表维护即可。

不知道Erine怎么做到少一个 \log 的，本蒟蒻不会。

代码

时间复杂度 \mathcal{O}(n\log n\log V)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 100005
using namespace std;
const int mod = 998244353;
int gcd(int a,int b) {
    return b ? gcd(b,a % b) : a;
}
int jc[N],inv[N],lg[N];
int C(int a,int b) {
    if (a < 0 || b < 0 || a < b) return 0;
    return jc[a] * inv[b] % mod * inv[a - b] % mod;
}
int st[N][23];
int query(int l,int r) {
    int k = lg[r - l + 1];
    return gcd(st[l][k],st[r - (1 << k) + 1][k]);
}
int n,a[N],sum[8][N];
signed main(){
    for (int i = 2;i < N;i ++) lg[i] = lg[i >> 1] + 1;
    jc[0] = jc[1] = inv[0] = inv[1] = 1;
    for (int i = 2;i < N;i ++) jc[i] = jc[i - 1] * i % mod,inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 2;i < N;i ++) inv[i] = inv[i - 1] * inv[i] % mod;
    cin >> n;
    for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),st[i][0] = a[i];
    for (int j = 1;(1 << j) <= n;j ++)
        for (int i = 1;i + (1 << j) - 1 <= n;i ++)
            st[i][j] = gcd(st[i][j - 1],st[i + (1 << j - 1)][j - 1]);
    int ans = 0;
    int t = 0;
    for (int i = 1;i <= n - 6;i ++) {
        t = gcd(t,a[i]);
        int rest = n - i;
        ans = (ans + C(rest,6) * t % mod) % mod;
    }
    for (int k = 2;k <= 7;k ++) {
        sum[k][0] = C(0,7 - k);
        for (int i = 1;i <= n;i ++) sum[k][i] = (sum[k][i - 1] + C(i,7 - k)) % mod;
    }
    for (int k = 2;k <= 7;k ++)
        for (int i = k;i <= n - (7 - k);i ++) {
            int now = a[i];
            int l = i;
            for (;l <= n && a[l] == 0;l ++);
            now = a[l];
            int r = n - (7 - k),res = l - 1,tot = 0;
            int xs1 = C(i - 2,k - 2);
            while(res < n - (7 - k)) {
                int lst = res + 1;
                l = res + 1,r = n - (7 - k),res = l;
                while(l <= r) {
                    int mid = l + r >> 1;
                    if (query(i,mid) >= now) l = mid + 1,res = mid;
                    else r = mid - 1;
                }
                tot = (tot + now * (sum[k][n - lst] - (n - res - 1 >= 0 ? sum[k][n - res - 1] : 0) + mod) % mod) % mod;
                now = query(i,res + 1);
            }
            ans = (ans + tot * xs1 % mod) % mod;
        }
    cout << ans;
    return 0;
}