【链分解，路径独立集计数】面包题

题意概括

从 $1\sim n$ 中选择一个子集 $S$。

对于任意被选中的数 $x$，如果 $kx\le n$，则 $kx$ 不能同时被选中。

需要统计合法子集的数量，并对 $998244353$ 取模。

由于 $n,k\le 10^9$，无法逐个处理所有整数。关键在于研究限制关系 $x\leftrightarrow kx$ 会形成怎样的结构。

样例分析

以 $n=4,k=2$ 为例，限制关系为

$1\longleftrightarrow 2\longleftrightarrow 4,$

而数字 $3$ 不与其他数字产生冲突。

因此，所有数字被分成两部分：

$1,2,4$

和

3\.

在链 $1,2,4$ 中不能选择相邻元素，合法选择有

$\varnothing,{1},{2},{4},{1,4},$

共 $5$ 种。

对于单独的数字 $3$，可以选或不选，共 $2$ 种。

两部分互不影响，因此答案为

$5\times 2=10.$

算法思路

将数字分解成若干条链

对于任意正整数 $x$，不断除去它所含的因子 $k$，可以将其唯一表示为

$x=bk^t,$

其中 $b$ 不能被 $k$ 整除。

例如，当 $k=2$ 时：

$12=3\times 2^2,$

对应的链起点是 $3$。

固定一个不能被 $k$ 整除的整数 $b$，所有形如

$b,bk,bk^2,bk^3,\ldots$

且不超过 $n$ 的数构成一条链。

不同的链不会相交，因为一个整数除去所有因子 $k$ 后得到的 $b$ 是唯一的。

同时，题目的冲突只发生在 $x$ 和 $kx$ 之间。因此，在每条链中，相邻的两个数不能同时选择，不同链之间完全独立。

原问题就转化为：

• 将 $1\sim n$ 分成若干条链。
• 计算每条链中不选择相邻元素的方案数。
• 将所有链的方案数相乘。

一条链的方案数

设 $f\_i$ 表示长度为 $i$ 的链中，不选择相邻元素的方案数。

空链只有一种方案，因此

$f\_0=1.$

长度为 $1$ 的链可以选择或不选择，因此

$f\_1=2.$

考虑一条长度为 $i$ 的链，并观察最后一个元素。

如果不选择最后一个元素，那么前 $i-1$ 个元素可以任意合法选择，方案数为

$f\_{i-1}.$

如果选择最后一个元素，那么倒数第二个元素必须不选，前 $i-2$ 个元素可以任意合法选择，方案数为

$f\_{i-2}.$

所以

$f\_i=f\_{i-1}+f\_{i-2}.$

这就是斐波那契型递推。

前几个值为

$ f\_0=1,\quad f\_1=2,\quad f\_2=3,\quad f\_3=5,\quad f\_4=8. $

统计每种长度的链有多少条

接下来需要计算长度恰好为 $i$ 的链有多少条。

一条链的起点 $b$ 必须满足：

1. $b$ 不能被 $k$ 整除。
2. 链中至少有 $i$ 个元素：

$bk^{i-1}\le n.$

3. 链中不能有第 $i+1$ 个元素：

$bk^i>n.$

因此 $b$ 的范围为

$ \left\lfloor\frac{n}{k^i}\right\rfloor < b \le \left\lfloor\frac{n}{k^{i-1}}\right\rfloor, $

并且 $k\nmid b$。

设

$g(x)$

表示 $1\sim x$ 中不能被 $k$ 整除的整数个数。

其中共有

$\left\lfloor\frac{x}{k}\right\rfloor$

个整数能够被 $k$ 整除，所以

$g(x)=x-\left\lfloor\frac{x}{k}\right\rfloor.$

令

$q\_i=\left\lfloor\frac{n}{k^i}\right\rfloor.$

那么长度恰好为 $i$ 的链的数量为

$c\_i=g(q\_{i-1})-g(q\_i).$

这些链各自有 $f\_i$ 种选择方式，因此它们对答案的贡献为

$f\_i^{c\_i}.$

最终答案为

$\prod\_{i\ge 1} f\_i^{c\_i}.$

如何枚举所有长度

不需要真的计算 $k^i$，否则可能发生溢出。

从

$q\_0=n$

开始，每次令

$ q\_i=\left\lfloor\frac{q\_{i-1}}{k}\right\rfloor. $

当 $q\_{i-1}=0$ 时停止。

因为 $k\ge 2$ 且 $n\le 10^9$，链的最大长度不会超过 $30$。

固定底数快速幂

对于每一层，需要计算

$f\_i^{c\_i}\bmod 998244353.$

普通快速幂已经能够通过本题。为了降低 $10^5$ 组数据下的常数，可以提前预处理

$f\_i^{2^j}$

的值。

之后将指数 $c\_i$ 按二进制分解，只需要乘上对应的预处理结果。

算法流程

对于每组数据：

1. 令当前上界 $a=n$，链长 $i=1$。
2. 计算下一层上界

$b=\left\lfloor\frac{a}{k}\right\rfloor.$

3. 长度恰好为 $i$ 的链数为

$

\left(a-\left\lfloor\frac{a}{k}\right\rfloor\right)

\left(b-\left\lfloor\frac{b}{k}\right\rfloor\right). $

4. 将答案乘上对应的

$f\_i^{c\_i}.$

5. 令 $a=b$，链长增加 $1$。
6. 重复上述过程，直到 $a=0$。

正确性说明

引理一：所有整数会被唯一划分为若干条链

任意正整数 $x$ 都可以不断除以 $k$，直到所得整数不能被 $k$ 整除。

因此存在唯一的 $b,t$，满足

$x=bk^t,\qquad k\nmid b.$

所以每个整数恰好属于一条以 $b$ 为起点的链，不会遗漏，也不会属于两条不同的链。

引理二：不同链之间没有选择冲突

题目的冲突只可能发生在 $x$ 和 $kx$ 之间。

如果

$x=bk^t,$

那么

$kx=bk^{t+1},$

两者除去所有因子 $k$ 后得到的起点仍然是同一个 $b$。

因此一条限制边的两个端点必然位于同一条链，不同链之间不存在限制关系。

引理三：长度为 $i$ 的链有 $f\_i$ 种合法选择

对于链的最后一个元素：

• 不选择它时，前 $i-1$ 个元素有 $f\_{i-1}$ 种方案。
• 选择它时，倒数第二个元素不能选择，前 $i-2$ 个元素有 $f\_{i-2}$ 种方案。

两类情况互不相交，并覆盖所有合法方案，因此

$f\_i=f\_{i-1}+f\_{i-2}.$

引理四：算法计算出的 $c\_i$ 等于长度恰好为 $i$ 的链数

长度恰好为 $i$ 的链起点满足

$q\_i\<b\le q\_{i-1},$

并且 $b$ 不能被 $k$ 整除。

区间 $1\sim q\_{i-1}$ 中符合条件的数有 $g(q\_{i-1})$ 个，区间 $1\sim q\_i$ 中符合条件的数有 $g(q\_i)$ 个。

两者相减得到

$c\_i=g(q\_{i-1})-g(q\_i),$

正好是长度恰好为 $i$ 的链数。

定理：算法输出所有合法子集的数量

根据引理一，所有整数被唯一分成若干条链。

根据引理二，不同链的选择互不影响。

根据引理三，每条长度为 $i$ 的链有 $f\_i$ 种合法选择。

根据引理四，共有 $c\_i$ 条长度为 $i$ 的链，因此所有此类链共有

$f\_i^{c\_i}$

种组合方式。

将所有链长的贡献相乘，得到的结果不重不漏地统计了全部合法子集。

实现细节与易错点

1. 空集也是合法方案，已经包含在每条链的动态规划中。
2. 当 $k>n$ 时，所有链的长度都是 $1$，答案自然变成

$2^n.$

3. 不要直接计算 $k^i$。通过不断整除 $n$ 可以避免溢出。
4. 链数量和指数最大达到 $10^9$，需要使用 long long。
5. 模乘中的两个数均小于 $998244353$，使用 long long 足以容纳乘积。
6. 在本题范围内，链长最多为 $30$，数组开到 $35$ 即可。

参考实现

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

const ll md = 998244353;
ll f[35], pw[35][31];

ll qp(int x, ll e) {
    ll r = 1;
    while(e) {
        int b = __builtin_ctzll(e);
        r = r * pw[x][b] % md;
        e &= e - 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    f[0] = 1;
    f[1] = 2;
    for(int i = 2; i < 35; i++) {
        f[i] = (f[i - 1] + f[i - 2]) % md;
    }

    for(int i = 1; i < 35; i++) {
        pw[i][0] = f[i];
        for(int j = 1; j <= 30; j++) {
            pw[i][j] = pw[i][j - 1] * pw[i][j - 1] % md;
        }
    }

    int t;
    cin >> t;

    while(t--) {
        ll n, k;
        cin >> n >> k;

        ll ans = 1;
        ll a = n;
        int len = 1;

        while(a) {
            ll b = a / k;
            ll cnt = (a - b) - (b - b / k);

            ans = ans * qp(len, cnt) % md;

            a = b;
            len++;
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度分析

对于一组数据，整数 $n$ 最多被除以 $k$ 共

$O(\log\_k n)$

次。

每次计算一次固定底数的二进制幂，指数最多有

$O(\log n)$

个二进制位。

因此单组数据的最坏时间复杂度为

$O(\log\_k n\log n).$

由于 $n\le 10^9$，两层循环的长度都不超过约 $30$。

总时间复杂度为

$O\left(T\log\_k n\log n\right).$

预处理数组规模为常数，空间复杂度为

$O(\log^2 n).$