题目描述
给你两个正整数 a,b,求 ⌊a/b⌋。
为了卡掉一些乱搞做法,你需要对答案进行如下处理:
设答案为 r,构造一个多项式 F(x):
$$F(x) = \sum\limits_{i=0}^{\lfloor \lg r \rfloor} (\lfloor 10^{-i}r \rfloor \bmod 10) \cdot x^i
$$
简单地说,就是从 r 的低位到高位,每一位对应 F(x) 一项的系数。
设 F(x) 的最高非零次数为 n,你需要求出一个 n 次多项式 G(x),使得:
F(x)⋅G(x)≡1(modxn+1)
将 G(x) 的系数对 998244353 取模,然后升幂输出 G(x) 的系数即可。
保证满足条件的 G(x) 存在。
输入格式
两行,每行一个正整数,分别为 a 和 b。
输出格式
输出一行 n+1 个整数,为 G(x) 的系数
19260817
114514
873463809 93585408 943652865
提示
【样例解释】
$\left\lfloor \dfrac{19260817}{114514} \right\rfloor = 168$。
由此构造出的多项式 F(x)=x2+6x+8
求出来对应的 G(x) 就是 943652865x2+93585408x+873463809。
【数据范围】
对于 100% 的数据,1≤b≤a≤10200000。