1655_拉格朗日插值

这是一道模板题。

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

• 1 x  y：向点集中添加点 (x,y)。保证点集中 x 互不相同。

• 2 k：输出 f(k) mod 998244353 的值，其中 f(k) 是一个次数不超过 |S|-1 次的函数，且经过 S 中所有的点。

第一行，一个整数 n，表示操作个数。 1 ≤ n ≤ 3000

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

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

1 ≤ x, y, k < 988244353 , 所有 x 互不相同

只有一行，一个整数，表示 f(k) mod 998244353 的值。

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

3
9
12

初始时点集 S=Φ。

第一个操作 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² - 4x + 7，因此 f(5)=12。