K. 多项式求导

Codeforces
IDCF10217K
Time1000ms
Memory256MB
Difficulty
English · Original
Formal · Original
一元多项式形如 $a_n x^n + a_{n -1} x^(n -1) +...... + a_2 x^2 + a_1 x + a_0 ​$,它是代数学研究的基本对象之一。求导是数学计算中的一个计算方法,它的表示当自变量的增量趋于零时因变量的增量与自变量的增量之商的极限。 早在高中学习导数的时候,天天就觉得给一元多次多项式求导是个简单到浪费脑细胞的工作。于是他在课间使用 C 语言写了一个给多项式求导的小程序。时隔这么多年,他早已找不到当年写的这段小程序代码了,希望聪明的你可以帮他重新完成这段给一元多项式求导的程序代码。 输入共两行,第一行输入两个正整数 $n$ 和 $k " "(1 <= n, k <= 100)$,分别表示输入的多项式次数 $n$,和程序需要对该多项式进行求导运算的阶数 $k$。 第二行输入 $n + 1$ 个非负整数 $a_n, \\\\cdots, a_1, a_0$ 由空格间隔开,其中第 $i$ 个整数为 $a_{n -i + 1} " "(0 <= a_{n -i + 1} <= 100)$,描述输入多项式第 $i -1$ 次项 $x^(i -1)$ 的系数。 请输出一行,包含 $n + 1$ 个非负整数 $a_n, \\\\cdots, a_1, a_0$ 由空格间隔开,其中第 $i$ 个整数为 $a_{n -i + 1}$,描述输入多项式求导后第 $i -1$ 次项 $x^(i -1)$ 的系数。由于系数可能很大,请对每个 $a_i$ 取模 $998244353$。 第一组样例的多项式为 $f (x) = x^5 + 2 x^4 + 3 x^3 + 4 x^2 + 5 x^1 + 6$,它的一阶导数为 $f ' (x) = 5 x^4 + 8 x^3 + 9 x^2 + 8 x^1 + 5$。 ## Input 输入共两行,第一行输入两个正整数 $n$ 和 $k " "(1 <= n, k <= 100)$,分别表示输入的多项式次数 $n$,和程序需要对该多项式进行求导运算的阶数 $k$。第二行输入 $n + 1$ 个非负整数 $a_n, \\\\cdots, a_1, a_0$ 由空格间隔开,其中第 $i$ 个整数为 $a_{n -i + 1} " "(0 <= a_{n -i + 1} <= 100)$,描述输入多项式第 $i -1$ 次项 $x^(i -1)$ 的系数。 ## Output 请输出一行,包含 $n + 1$ 个非负整数 $a_n, \\\\cdots, a_1, a_0$ 由空格间隔开,其中第 $i$ 个整数为 $a_{n -i + 1}$,描述输入多项式求导后第 $i -1$ 次项 $x^(i -1)$ 的系数。由于系数可能很大,请对每个 $a_i$ 取模 $998244353$。 [samples] ## Note 第一组样例的多项式为 $f (x) = x^5 + 2 x^4 + 3 x^3 + 4 x^2 + 5 x^1 + 6$,它的一阶导数为 $f ' (x) = 5 x^4 + 8 x^3 + 9 x^2 + 8 x^1 + 5$。
**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n, k \leq 100 $. Let $ P(x) = \sum_{i=0}^{n} a_i x^i $ be a polynomial of degree $ n $, where $ a_i \in \mathbb{Z}_{\geq 0} $ and $ 0 \leq a_i \leq 100 $. Let $ P^{(k)}(x) $ denote the $ k $-th derivative of $ P(x) $. **Constraints** 1. $ 1 \leq n, k \leq 100 $ 2. $ 0 \leq a_i \leq 100 $ for all $ i \in \{0, 1, \dots, n\} $ 3. Input coefficients are given in order $ a_n, a_{n-1}, \dots, a_0 $ (i.e., descending powers of $ x $). 4. Output coefficients must be computed modulo $ 998244353 $. **Objective** Compute the coefficients of $ P^{(k)}(x) $, expressed as a polynomial of degree $ \max(n - k, 0) $, with coefficients $ b_0, b_1, \dots, b_{n-k} $ corresponding to $ x^0, x^1, \dots, x^{n-k} $, such that: $$ b_j = \begin{cases} \displaystyle \frac{(j + k)!}{j!} \cdot a_{j + k} \mod 998244353 & \text{if } j + k \leq n \\ 0 & \text{otherwise} \end{cases} $$ Output the coefficients $ b_0, b_1, \dots, b_{n-k} $ in order (i.e., ascending powers of $ x $), padded with trailing zeros to make $ n+1 $ total coefficients if $ k = 0 $, otherwise output only $ n - k + 1 $ coefficients (as per problem’s output format requirement: $ n+1 $ integers, but note: after $ k $ derivatives, degree is $ n-k $, so coefficients for $ x^{n-k+1} $ to $ x^n $ are zero — but problem says output $ n+1 $ coefficients, implying zero-padding to original length). **Clarification from problem output format**: Output $ n+1 $ integers: the $ i $-th integer (1-indexed) is the coefficient of $ x^{i-1} $ in the $ k $-th derivative. Thus, for $ j = 0 $ to $ n $, output coefficient of $ x^j $ in $ P^{(k)}(x) $, which is zero if $ j > n - k $, and $ \frac{(j + k)!}{j!} a_{j+k} \mod 998244353 $ if $ j \leq n - k $. So define: For $ j = 0, 1, \dots, n $: $$ b_j = \begin{cases} \displaystyle \left( \prod_{t=1}^{k} (j + t) \right) \cdot a_{j + k} \mod 998244353 & \text{if } j + k \leq n \\ 0 & \text{otherwise} \end{cases} $$ Output: $ b_0, b_1, \dots, b_n $
API Response (JSON)
{
  "problem": {
    "name": "K. 多项式求导",
    "description": {
      "content": "一元多项式形如 $a_n x^n + a_{n -1} x^(n -1) +...... + a_2 x^2 + a_1 x + a_0 ​$,它是代数学研究的基本对象之一。求导是数学计算中的一个计算方法,它的表示当自变量的增量趋于零时因变量的增量与自变量的增量之商的极限。 早在高中学习导数的时候,天天就觉得给一元多次多项式求导是个简单到浪费脑细胞的工作。于是他在课间使用 C 语言写了一个给多项",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10217K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一元多项式形如 $a_n x^n + a_{n -1} x^(n -1) +...... + a_2 x^2 + a_1 x + a_0 ​$,它是代数学研究的基本对象之一。求导是数学计算中的一个计算方法,它的表示当自变量的增量趋于零时因变量的增量与自变量的增量之商的极限。\n\n早在高中学习导数的时候,天天就觉得给一元多次多项式求导是个简单到浪费脑细胞的工作。于是他在课间使用 C 语言写了一个给多项...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 100 $.  \nLet $ P(x) = \\sum_{i=0}^{n} a_i x^i $ be a polynomial of degree $ n $, where $ a_i \\in \\mathbb{Z}_{\\geq 0} $ and $ 0 \\l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments