P4893 GodFly’s Differentiation Tool.

“Only by finding derivatives of derivatives can you become the best.” As a stubborn tough guy, GodFly is no longer satisfied with simple differentiation.

To prove how stubborn he is, GodFly decided to take on a challenge: compute the $k$-th derivative of an $n$-th degree polynomial function with big integer coefficients. Now he hopes that smart you can… sit there quietly and watch him differentiate. After all, he is a man who can rival Shenwei - TaihuLight. As GodFly’s friend, xhx hopes you can help him write a program to compute the derivative function and derivative values together with GodFly. If your program can beat his manual calculation, xhx will knock on GodFly’s iron head. *Some rules for derivatives: If $f(x)=ax^n$, then $f'(x)=anx^{n-1}$. If $F(x)=f(x)+g(x)$, then $F'(x)=f'(x)+g'(x)$. Here, $f'(x)$, $g'(x)$, and $F'(x)$ denote the derivative functions of $f(x)$, $g(x)$, and $F(x)$, respectively. **Do not be scared by derivatives. This problem is not testing that.** **Let $g(x)=ax^3+bx^2+c$, then $g(x_0)=ax_0^3+bx_0^2+c$.** **The $k$-th derivative means differentiating $k$ times.** **New samples: https://pan.baidu.com/s/1w64WmnnGtKyAluxrX3PkNg; testdata has been updated.**

The first line contains two integers $n,k$, with meanings as described in the statement. The next line contains a string representing the function, in the form $f(x)=a_{n}x^n+a_{n-1}x^{n-1}+....+a_0x^0$. For any $i$, the term $a_ix^i$ may be absent, or may appear multiple times. All $a_i$ are positive integers, but if a term has coefficient $1$, then $a_i$ is not given; only $x^i$ is written. The next line contains a number $m$, the number of queries. The next $m$ lines each contain a number **$x_0$**, meaning: compute the value of the $k$-th derivative of $f(x)$ at $x_0$. In other words, suppose $g(x)$ is the $k$-th derivative function of $f(x)$, find $g(x_0)$. There are no extra spaces or blank lines.

Output $m$ lines, each containing one number, the required derivative value.

**Constraints** For $30\%$ of the data: $n\le5$, $a_i\le100$, $x_0\le100$, and for any $0\le i\le n$, the term $a_ix^i$ appears exactly once, and the input is guaranteed to be sorted in decreasing order by $i$. Another $10\%$ of the data: $k=0$. Another $10\%$ of the data: $k=1$. Another $10\%$ of the data: $n=k$. For $100\%$ of the data: $n\le100$, $k\le n$, $m\le10$, $a_i\le10^5$, $x_0\le10^5$. **Sample Explanation** Differentiate $f(x)$. The first derivative is $f'(x)=3x^2+4x+1$. Differentiate again to get the second derivative: $f''(x)=6x+4$. Therefore, the required values are $f(0)=6*0+4=4$ and $f(1)=6*1+4=10$. **Notes** PS: Worried that everyone will complain about too much code (the setter is lazy), this version has been simplified a lot compared to the original problem. If you get an early AC, you may want to read a duel between two “iron-head” tough guys: “Director Feng Differentiates Zheng Babang to Death with Three Derivatives” Director Feng······ with just one derivative, differentiated right on the fraction, making Zheng Bang dizzy and confused, parameters skewed to one side. It was as if he had opened a table of elementary functions: squares, roots, everything ticked off and differentiated out. Zheng Iron-Head could not keep up, tossed the answer aside, and only shouted, “Good differentiation!” Director Feng scolded, “Iron-head brat! You still dare to talk back!” He picked up the pen and differentiated the numerator again, sparks flying, heads cracking and bleeding, as if he had opened a binomial theorem: cubic, quartic, quintic terms all burst out. The people watching on both sides feared Director Feng. Who would dare step forward to stop him. Zheng Bang could not differentiate it, and begged for mercy. Director Feng shouted, “Ha! You iron-head brat! If you only had the guts to do full case analysis with me, I might spare you! But now you beg me for mercy, and I insist on separating the parameters!” He differentiated once more. On the new function it went straight, like working from a common derivative table: exponentials, logarithms, numerator and denominator ringing together. When the director looked, he saw Zheng Bang collapsed on the ground, only exhaling, not inhaling, unable to move. Director Feng pretended, “You bastard, playing dead. I will differentiate again!” Then his head gradually disappeared. The director thought, “I only meant to make him pay for one meal. I did not expect three derivatives would really differentiate him to death. I will get points deducted, and there are no more problems to do. Better to leave early.” He walked away, turned back and pointed at the paper, “This useless problem, I skip it!” While calculating, he strode away in big steps. Translated by ChatGPT 5