#165. 拉格朗日插值

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cutekibry

题目描述

这是一道模板题。

维护一个点集 S ,初始时点集为空集。下面依次进行 n 个操作,操作有两种:

  • 1 x y:向点集中添加点 (x, y) 。保证点集中 x 互不相同。
  • 2 k:输出 f(k) \bmod 998244353 的值,其中 f(x) 是一个次数不超过 |S| - 1 次的函数,且经过 S 中所有的点。

输入格式

第一行,一个整数 n ,表示操作个数。

接下来 n 行,每行 2 3 个整数,描述操作。

数据保证第一个操作必定为 1 类型操作。

输出格式

多行,第 i 行,一个整数,表示对第 i 2 类型操作要求计算的 f(k) \bmod 998244353 的值。

样例

样例输入

6
1 2 3
2 5
1 4 7
2 5
1 1 4
2 5

样例输出

3
9
12

样例解释

初始时点集 S = \emptyset

第一个操作 1 2 3,向点集中插入点 (2, 3) 。此时点集 S = \{(2, 3)\}

第二个操作 2 5,询问 f(5) 的值。唯一满足次数不超过 0 次且经过点 (2, 3) 的函数为 f(x) = 3 ,因此 f(5) = 3

第三个操作 1 4 5,向点集中插入点 (4, 7) 。此时点集 S = \{(2, 3), (4, 7)\}

第四个操作 2 5,询问 f(5) 的值。唯一满足次数不超过 1 次且经过点 (2, 3), (4, 7) 的函数为 f(x) = 2x - 1 ,因此 f(5) = 9

第五个操作 1 1 4,向点集中插入点 (1, 4) 。此时点集 S = \{(2, 3), (4, 7), (1, 4)\}

第六个操作 2 5,询问 f(5) 的值。唯一满足次数不超过 2 次且经过点 (2, 3), (4, 7), (1, 4) 的函数为 f(x) = x^2 - 4x + 7 ,因此 f(5) = 12

数据范围与提示

对于 100\% 的数据, 1 \leq n \leq 3000, 1 \leq x, y, k < 998244353 ,所有 x 互不相同。

数据有一定梯度。