题目来源: 2023 ICPC 陕西省赛: D. Function

题面

给定函数 \(f\) 满足: \[ f(x)=\begin{cases} \displaystyle 1+\sum_{k=2}^a f(kx)&x\le n\\ 0&x>n \end{cases} \] 输入 \(n\), 求 \(f(1)\bmod p\). 其中 \(a=20210926\), \(p=998244353\).

数据范围

\[ 1\le n\le10^9 \]

题解

本质上, 题设给出的函数是一个关于 \(x\) 和 \(n\) 的二元函数, 记: \[ F(x,n)=\begin{cases} \displaystyle 1+\sum_{k=2}^a F(kx,n)&x\le n\\ 0&x>n \end{cases} \] 可知 \(f(x)=F(x,n)\). 在题解的后文中将完全不再使用题面所给出的一元函数 \(f\), 均使用二元函数 \(F\). 题面所求转换为求 \(F(1,n)\bmod p\).

根据 \(F\) 的定义, 可知: \[ F(x,y)=F\left(\frac xz,\frac yz\right)=F\left(1,\frac yx\right)\tag1 \] 记 \(g(y)=F(1,y)\). 则所求转换为求 \(g(n)\), 且有下式成立: \[ g(y)=1+\sum_{k=2}^a g\left(\frac yk\right) \] 此时, 根据该式直接进行记忆化搜索, 复杂度为 \(O(n^2)\), 显然不能满意.

而对于 \(F(x,y)\), 当 \(x\) 是正整数时, 有\(\newcommand{\flor}[1]{\left\lfloor#1\right\rfloor}\) \[ F(x,y)=F(x,\flor y)\tag2 \] 故可以得到 \[ g(y)=1+\sum_{k=2}^a g\left(\flor{\frac yk}\right) \] 在这种情况下, 可以进行数论分块, \(\flor{y/k}\) 只有 \(O(\sqrt y)\) 个取值.

依托数论分块进行记忆化搜索求解 \(g(n)\):

对于 \(\flor{n/k}\le \sqrt n\) 的情况, 将 \(g(1),g(2),\cdots,g(\sqrt n)\) 全部进行预处理, 共需求解 \(\sqrt n\) 个值, 在数论分块的情况下, 每个值有 \(O(\sqrt{\sqrt n})\) 项相加, 该情况下的总复杂度为 \(O(n^{3/4})\).

对于 \(\flor{n/k}>\sqrt n\) 的情况, 此时可知 \(k<\sqrt n\), 此时记 \(h_n(k)=g(\flor{n/k})\), 则需求解 \(h_n(1),h_n(2),\cdots,h_n(\sqrt n)\). 其中 \(h_n(k)\) 共有 \(O(\sqrt{n/k})\)​ 项相加, 该情况下的总复杂度为 \[ \sum_{k=1}^\sqrt nO\left(\sqrt {\frac{n}{k}}\right)=O(\sqrt n)\cdot\sum_{k=1}^{\sqrt n}\frac1{\sqrt k}=O(\sqrt n)\cdot O\left(\sqrt{\sqrt n}\right)=O(n^{3/4}) \] 故记忆化搜索的总复杂度为 \(O(n^{3/4})\).

需要注意在数论分块时, 分块的边界除了算法本身的 \(n/(n/k)\), 还要注意 \(k\le a\). 即分块区间为 \[ \left[k,\min\left(\flor{\frac n{\flor{n/k}}},a\right)\right] \]

备注

题解中公式(1)该公式对所有的正实数 \(x,y\) 均成立. 公式(1)的证明如下:

首先, 对于 \(x>y\) 的情况, \[ F(x,y)=F\left(\frac xz,\frac yz\right)=0 \] 下考虑 \(x\le y\) 的情况. 由定义，等式成立的一个充分条件为: \(\forall k\in[2,a]\cap\mathbb N\) 均有 \(\displaystyle F(kx,y)=F\left(\frac {kx}z,\frac yz\right)\). 对充分条件中 \(kx\le y\) 的情况再次应用充分条件. 每次充分条件后, \(F\) 的第一元参数都至少变为两倍. 故经有限次应用充分条件后, \(F\) 的第一元参数均会大于第二元, 充分条件成立. 故对于所有 \(x\le y\) 的情况也成立.

题解中公式(2)的证明亦同理, 但该公式仅对所有的正整数 \(x\) 和正实数 \(y\) 成立.

若 \(x\) 为整数且 \(x>y\), 则 \(x>\flor y\), 根据定义 \(F(x,y)=F(x,\flor y)=0\). 对于 \(x\) 为整数且 \(x\le y\) 的情况, 由于 \(x\) 为整数, 故也有 \(x\le\flor y\). 使用与公式(1)相同的证明方法, 即得证.

题目中, 若 \(F\) 中的参数 \(a\) 取 \(+\infty\), 则由阿基米德公理, 对于给定的 \(x,y\), 定义依然是有限个非0项求和. 公式(1)(2)依然成立, 基于 \(a\) 是常数的做法依然成立, 且不需要再额外检测数论分块的边界.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

const int m = 1e9, ghn = sqrt(m);
const int p = 998244353;
int g[ghn + 7], h[ghn + 7], n;

int solve(int hi)
{
    int ans = 1;
    int hn = n / hi;
    if (hn <= ghn)
        return g[hn];
    if (h[hi])
        return h[hi];
    for (int j = 2; j <= hn && j <= 20210926; ++j)
    {
        int jp = min(hn / (hn / j), 20210926);
        if (hn / j <= ghn)
            ans += 1ll * (jp - j + 1) % p * g[hn / j] % p, ans %= p, j = jp;
        else
            ans += solve(hn / j), ans %= p;
    }
    return h[hi] = ans;
}

int main()
{
    for (int i = 1; i <= ghn; ++i)
    {
        g[i] = 1;
        for (int j = 2; j <= i && j <= 20210926; ++j)
        {
            int jp = i / (i / j);
            g[i] += 1ll * (jp - j + 1) % p * g[i / j] % p, g[i] %= p, j = jp;
        }
    }
    cin >> n;
    int ans;
    if (n <= ghn)
        ans = g[n];
    else
        ans = solve(1);
    cout << ans;
}

花絮

笔者于比赛开始后103分钟通过本题，获得了本题的最快解题奖。