#P9823. [ICPC 2020 Shanghai R] The Journey of Geor Autumn

    ID: 9186 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>动态规划,dp2020上海O2优化组合数学逆元ICPC

[ICPC 2020 Shanghai R] The Journey of Geor Autumn

Description

给定 1k1071 \le k \le 10^7,我们规定满足以下性质的 1n1\sim n(其中 1n107 1\le n \le 10^7) 的排列为“好排列”:

$$\forall k \min\{a_{i-k},a_{i-k+1},...,a_{i-1}\}$$

求好排列的个数。对 998244353998244353 取模。

Input Format

一行,两个整数 n,kn,k

Output Format

一行,为好排列的个数对 998244353998244353 取模的值。

1 1
1
2 3
2
3 2
4
4 2
10