嘘~ 正在从服务器偷取页面 . . .

CF1359E Modular Stability 题解

发布日期: 2023-10-11

更新日期: 2023-10-11

文章字数: 511

CF1359E Modular Stability 题解

题意：

求有多少个长度为 $k$ 的序列 $a$，满足以下条件：

$\forall 1 \le i < k,a_i < a_{i+1}$

$\forall 1 \le i \le k,1 \le a_i \le n$

对于任意一个 $1$ 至 $k$ 的排列 $p$，满足
$\begin{aligned} &( (((x \bmod a_1)\bmod a_2)\bmod a_3)\bmod \cdots \bmod a_k) \\[6pt]= &((((x \bmod a_{p_1})\bmod a_{p_2})\bmod a_{p_3} )\bmod \cdots \bmod a_{p_k}) \end{aligned}$
其中 $x$ 为任意非负整数。

结果对 $998244353$ 取模。

输入格式：

输入一行两个整数 $n,k$，意义如题目描述所示。

输出格式：

输出一个整数表示答案。

数据范围：

$1 \le n,k \le 5 \times 10^5$。

考虑如何使得 $(x \bmod a) \bmod b = (x \bmod b) \bmod a$ ，其中 $a < b$

稍微搞一搞可以发现上面的式子等价于 $x\equiv x + by \pmod{a}$ ，则 $a \mid b$ 时恒成立

那么有 $a_i \mid a_{i+1}$ ，其中 $i < k$ 。因此我们只需要枚举 $a_1$ ，然后看看有多少倍数合法，从里面选 $k-1$ 个就好

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(1e6 + 15))

int fac[N],inv[N];
void init(int n)
{
    fac[0] = 1, inv[0] = inv[1] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2; i <= n; i++) inv[i] = inv[i] * inv[i - 1] % mod;
}
int C(int n, int m)
{
    if(!m) return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init((int)(1e6 + 5));
    int n,k,res = 0; cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        if(n / i < k) break;
        add(res, C(n / i - 1, k - 1));
    }
    cout << res << '\n';
    return 0;
}