Pro.ID1656 Title拉格朗日插值 2 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1656 AC1 Submit5 Ratio20.00% 时间&空间限制描述这是一道模板题。 给出次数不超过 n 的函数 f(x) 在点 0, 1, ..., n 上的取值 f(0), f(1), ..., f(n) ,以及一个整数 m ,请求出 f(m), f(m+1), ..., f(m+n) 的值。 可以证明,该函数必定存在且唯一。 由于答案可能很大,你只需要输出答案 mod 998244353 的值。 输入第一行,两个整数 n, m,表示函数次数不超过 n,以及计算要求。 第二行,n+1 个整数 f(0), f(1), ..., f(n) ,表示函数 f(x) 在点 0, 1, ..., n 上的取值。 1 ≤ n ≤ 100000 , 1 ≤ f(i) ≤ 988244353 , n < m ≤ 108 数据有一定梯度。 输出Description 这是一道模板题。 给出次数不超过 n 的函数 f(x) 在点 0, 1, ..., n 上的取值 f(0), f(1), ..., f(n) ,以及一个整数 m ,请求出 f(m), f(m+1), ..., f(m+n) 的值。 可以证明,该函数必定存在且唯一。 由于答案可能很大,你只需要输出答案 mod 998244353 的值。 Input 第一行,两个整数 n, m,表示函数次数不超过 n,以及计算要求。 第二行,n+1 个整数 f(0), f(1), ..., f(n) ,表示函数 f(x) 在点 0, 1, ..., n 上的取值。 1 ≤ n ≤ 100000 , 1 ≤ f(i) ≤ 988244353 , n < m ≤ 108 数据有一定梯度。 Output 只有一行,n+1 个整数 f(m), f(m+1), ..., f(m+n) ,表示答案。 由于答案可能很大,你只需要输出答案 mod 988244353 的值。 Sample Input Sample #1 Sample Output Sample #1 Hint 样例解释 1 解得函数 f(x) = 3x2 - x + 5 ,因此 f(4)=49, f(5)=75, f(6)=107。 样例解释 2 解得函数 f(x) = - x4 + 6x3 + 3x2 - 10x + 5,因此 f(10)= -3795, f(11)=-6397, f(12)=-10051, f(13)=-14997, f(14)=-21499 。 样例输入Sample #1 样例输出Sample #1 提示样例解释 1 解得函数 f(x) = 3x2 - x + 5 ,因此 f(4)=49, f(5)=75, f(6)=107。 样例解释 2 解得函数 f(x) = - x4 + 6x3 + 3x2 - 10x + 5,因此 f(10)= -3795, f(11)=-6397, f(12)=-10051, f(13)=-14997, f(14)=-21499 。 作者 |