P5240 Derivation

    • 21通过
    • 185提交
  • 题目提供者 rushcheyo
  • 评测方式 云端评测
  • 标签 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小 R 学会微积分中求导这一概念后,他的数学老师要求他开始做一部分导数的练习题加深自己的理解。

    但颖悟绝伦的小 R 对繁复的练习题并不感兴趣。他希望你帮他设计一个程序,计算一个给定函数 $f(x)$ 的导数。

    如果你对导数这一概念并不熟悉,请参阅【说明】中的内容。

    输入输出格式

    输入格式:

    第一行一个正整数 $T$,表示小 R 要完成的练习题数量,亦即测试数据的组数。

    每组测试数据的第一行是一个非空字符串,描述了输入的函数 $f(x)$。设 $p=998244353$。

    字符串中可能包含的元素有:

    1. 系数为 $1$ 的单项式,包括 $x^1,x^2,x^0$ 等,我们保证指数为非负整数(为 $1$ 时不省略)且不超过 $p-1$。所有幂号用 ^ 代替。
    2. 常数,如 $0,19260817$ 等;我们保证一切常数是非负整数且不超过 $p-1$。
    3. 复合函数。将以上两种函数组合的方式可以为加乘幂,括号等。数学中会省略乘号和括号,但我们保证任意情况下都不省略(也不会无意义冗余,即不存在 ((x)),(3)+(4));保证任何指数都是常数,即不存在 $x^{g(x)}$ 的情况。

    经过以上规定,我们发现 $f(x)$ 求导后一定是一个多项式函数。如果你对数据的输入形式仍有不确定,可以观察附加样例文件。

    由于输出这样的函数存在技术困难,为确认你的输出是正确的,测试数据的第二行为两个整数,值在 $[0,p)$ 之间。你需要输出两个整数,表示这些整数代入导函数后的值模 $p$ 的结果。

    注意:本题中认为 $0^0=1$。

    输出格式:

    输出 $T$ 行,每行两个整数,已在【输入格式】中说明它们的意义。

    输入输出样例

    输入样例#1: 复制
    4
    x
    0 1
    9
    0 1
    x*(x^(1*8))
    0 1
    (3*(x^3))+((2*(x^2))+(12*x))
    0 1
    
    输出样例#1: 复制
    1 1
    0 0
    0 9
    12 25
    

    说明

    规定字符串长度不超过 $10^4$,字符串总长不超过 $5 \times 10^5$。

    子任务编号 特殊性质 分值
    1 $T \le 10^4$,字符串长度不超过 $20$,出现的常数不超过 $9$ 20
    2 $T \le 100$,输入是一个化简后的多项式 15
    3 $T \le 100$,出现的常数不超过 $9$ 15
    4 $T \le 100$,不存在多项式求幂 20
    5 $T \le 100$ 30

    我们提供了 5 个附加样例文件,分别满足 5 个子任务的限制。

    链接: https://pan.baidu.com/s/1dVSy8tU3pqGoq1-7CFYtBw 提取码: ya2u

    我们只保证以下定义在本题中适用。

    $f(x)$ 的导数是一个函数 $f'(x)$,满足:

    $$ \displaystyle \lim_{h \to 0} f'(x)=\dfrac{f(x+h)-f(x)}{h} $$

    我们称 $\displaystyle \lim_{x \to a}g(x)=L$ 当且仅当对于任何实数 $\epsilon > 0$ 我们都可以找到一个实数 $\delta > 0$ 使得 $\lvert g(x)-L\rvert < \epsilon$ 若 $0 < \lvert x - a \rvert < \delta$。

    你可能用到以下的求导公式:

    1. $f(x)=C,f'(x)=0$,其中 $C$ 是一常数。
    2. $f(x)=x^n,f'(x)=nx^{n-1}$,其中 $n$ 为非 $0$ 常数。
    3. $(f(x)+g(x))'=f'(x)+g'(x)$
    4. $(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$
    5. $(f(g(x)))'=f'(g(x))g'(x)$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。