3852: Coefficient
内存限制：128 MB
时间限制：14.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Given a function f(x)=bc+eax+d, where a≢0(mod998244353).
Denote x0 as the smallest real solution of the equation: ax+d=0, and note that the solution always exists.
Output the coefficient of the item (x−x0)n in the Taylor series of f(x) at x=x0. The answer may be very large, so you just need to output the answer modulo 998244353.
Note that for the given n, your task is to answer q queries which share the same parameter n.
Note that it is not guaranteed that the answer could be represented as rational fraction pq where gcd(p,q)=1, or q has no multiplicative inverse element modulo 998244353. If it can, print it as pq−1 modulo 998244353 which is not negative. Otherwise just print −1.
If you knew little about gcd in mathematic, please refer to https://en.wikipedia.org/wiki/Greatest_common_divisor
If you knew little about Taylor_series in mathematic, please refer to https://en.wikipedia.org/wiki/Taylor_series
Denote x0 as the smallest real solution of the equation: ax+d=0, and note that the solution always exists.
Output the coefficient of the item (x−x0)n in the Taylor series of f(x) at x=x0. The answer may be very large, so you just need to output the answer modulo 998244353.
Note that for the given n, your task is to answer q queries which share the same parameter n.
Note that it is not guaranteed that the answer could be represented as rational fraction pq where gcd(p,q)=1, or q has no multiplicative inverse element modulo 998244353. If it can, print it as pq−1 modulo 998244353 which is not negative. Otherwise just print −1.
If you knew little about gcd in mathematic, please refer to https://en.wikipedia.org/wiki/Greatest_common_divisor
If you knew little about Taylor_series in mathematic, please refer to https://en.wikipedia.org/wiki/Taylor_series
输入
There are multiple test cases.
Each case starts with a line containing two integers n and q seperated by a space.
Next q lines in every test case will include four integers a, b, c, d per line, seperated by 3 spaces.
It is guaranteed that ∀t∈{a,b,c,d},|t|≤109 and n,q∈[0,5×104].
It is guaranteed that the sum of n and the sum of q in all test cases are both no larger than 3×105.
Each case starts with a line containing two integers n and q seperated by a space.
Next q lines in every test case will include four integers a, b, c, d per line, seperated by 3 spaces.
It is guaranteed that ∀t∈{a,b,c,d},|t|≤109 and n,q∈[0,5×104].
It is guaranteed that the sum of n and the sum of q in all test cases are both no larger than 3×105.
输出
For each query in each test case, output the only line containing just one integer denoting the answer if there would be, or −1 otherwise.
样例输入 复制
0 1
1 1 1 1样例输出 复制
499122177