题解：P17301 [ICPC 2026 Xi'an I] Unreachable Land

· · 题解

题意简述

初值为 a，依次处理模数 m,m-1,\dots,1。 处理模数 j 时，可以执行 a\leftarrow a\bmod j，也可以跳过。 即使取模后数值不变，执行与跳过仍算两种不同选择。 求最终得到 b 的方案数。

解题思路

先研究当前值已经小于 m 的情况。 定义 f_x 为当前值是 x， 接下来依次处理模数 x,x-1,\dots,1 时，最终得到 b 的方案数。

当前值已经等于目标时，不再执行任何取模便得到唯一方案，所以 f_b=1。 若 x<b，后续取模只会让数值继续减小，所以 f_x=0。

对于 x>b，按第一次选择执行取模的模数 j 分类。 在模数 x,x-1,\dots,j+1 处必须全部跳过， 否则 j 就不是第一次执行取模的位置。

执行 x\bmod j 后记：

r=x\bmod j

此后从 j-1 到 r+1 的所有模数都大于当前值 r。 在这些位置执行取模或跳过都不会改变数值， 但两种选择会被分别计数，因此产生：

2^{j-r-1}

处理到模数 r 后，剩余方案恰由 f_r 统计。 若 j\le b，则 r<j\le b，除 r=b 的边界外都无法再回到 b； 而 j=b 时必有 r<b，所以只需枚举 j>b。 于是得到：

f_x=\sum_{j=b+1}^{x}f_{x\bmod j}2^{j-(x\bmod j)-1}

每个合法方案都有唯一的第一次执行取模的位置， 而每个转移项都完整枚举了取模后不改变数值的选择， 再接上由 f_r 统计的后缀。 因此该转移不重不漏。

原问题从 a\ge m 开始。 同样枚举第一次执行取模的模数，答案为：

\operatorname{ans}=\sum_{j=b+1}^{m}f_{a\bmod j}2^{j-(a\bmod j)-1}

最后一式只需枚举一次。 瓶颈在于计算 f_b,f_{b+1},\dots,f_{m-1}。

令：

s=\lfloor\sqrt m\rfloor

再令 c=\max(b+1,s+1)。

对 b<j\le s 的部分直接枚举。 下面只考虑 j\ge c。

固定：

k=\left\lfloor\frac{x}{j}\right\rfloor

产生同一个 k 的模数 j 构成连续区间：

\max\left(c,\left\lfloor\frac{x}{k+1}\right\rfloor+1\right) \le j\le \left\lfloor\frac{x}{k}\right\rfloor

令 y=x-kj，则 y=x\bmod j。 同一段内的 y 都满足 y\equiv x\pmod k， 并且相邻两个 y 相差 k。 由于 x 与 y 对 k 同余，有：

\begin{aligned} j-y-1 & =\frac{x-y}{k}-y-1 \\ & =\left\lfloor\frac{x}{k}\right\rfloor-\left\lfloor\frac{y}{k}\right\rfloor-y-1 \end{aligned}

所以每个转移项可以拆成：

f_y2^{j-y-1} =2^{\lfloor x/k\rfloor-1} f_y2^{-y-\lfloor y/k\rfloor}

对每一对 (k,r)，其中 r=x\bmod k，维护：

g_{k,r}=\sum f_y2^{-y-\lfloor y/k\rfloor}

求和范围是当前区间已经覆盖到的所有 y\equiv r\pmod k。 那么固定 k 的整段贡献就是：

g_{k,r}2^{\lfloor x/k\rfloor-1}

还需说明这个前缀和可以增量维护。 对固定的 (k,r)，相邻两次出现的 x 相差 k。 区间左端：

l=\max\left(c,\left\lfloor\frac{x}{k+1}\right\rfloor+1\right)

在 x 增加 k 时，l 只会增加 0 或 1。 对应的最大余数 x-kl 便只会保持不变或增加 k。 因此每次至多向 g_{k,r} 加入一个新状态。 代码用 lst 记录当前端点。

因为 j\ge c，所以只需枚举 k\le x/c。 小模数部分总耗时为 O(ms)， 大模数部分总耗时为 O(m^2/c)。 取 s=\lfloor\sqrt m\rfloor 后，单组时间复杂度为 O(m\sqrt m)。

可用的 k 小于 \sqrt m，所有 (k,r) 的数量为：

\sum_{k=1}^{O(\sqrt m)}k=O(m)

所以空间复杂度为 O(m)。 代码预处理 2 的正幂与逆幂，所有运算均对 998244353 取模。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
const int M=400005;
const int K=450;
const int mod=998244353;
const int inv2=499122177;
int f[N],pw[M],ip[M],g[K][K],lst[K][K];
int solve(int a,int b,int m)
{
    fill(f,f+m,0);
    f[b]=1;
    int s=(int)sqrt(m);
    int c=max(b+1,s+1);
    int q=(m-1)/c;
    for(int i=1;i<=q;i++)
    {
        fill(g[i],g[i]+i,0);
        fill(lst[i],lst[i]+i,-1);
    }
    for(int i=b+1;i<m;i++)
    {
        ll res=0;
        for(int j=b+1;j<=min(s,i);j++)
        {
            int r=i%j;
            res+=(ll)f[r]*pw[j-r-1]%mod;
        }
        for(int k=1;k<=i/c;k++)
        {
            int l=max(c,i/(k+1)+1);
            int y=i-k*l;
            int r=i%k;
            if(lst[k][r]<y)
            {
                g[k][r]=int((g[k][r]+(ll)f[y]*ip[y+y/k])%mod);
                lst[k][r]=y;
            }
            res+=(ll)g[k][r]*pw[i/k-1]%mod;
        }
        f[i]=int(res%mod);
    }
    ll ans=0;
    for(int j=b+1;j<=m;j++)
    {
        int r=a%j;
        ans+=(ll)f[r]*pw[j-r-1]%mod;
    }
    return int(ans%mod);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pw[0]=1;
    ip[0]=1;
    for(int i=1;i<M;i++)
    {
        pw[i]=int((ll)pw[i-1]*2%mod);
        ip[i]=int((ll)ip[i-1]*inv2%mod);
    }
    int T;
    cin>>T;
    while(T--)
    {
        int a,b,m;
        cin>>a>>b>>m;
        cout<<solve(a,b,m)<<'\n';
    }
    return 0;
}