#1708. 青蛙思直线

    ID: 1708 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1058来源:qoj.ac数据:公开样例递归数学模拟

青蛙思直线

青蛙思直线

题目描述

标题: 青蛙思直线 - Problem - QOJ.ac

#5174. 青蛙思直线

Statistics

The problem was used in the following contests:

题目描述

在寒风呼啸的雾之湖,琪露诺正在追逐一只青蛙。

这只青蛙将依次进行 n 个操作:跳过一条直线,起跳点与着落点关于直线对称;或绕一点旋转跳若干角度。

琪露诺将要施加 q 个魔法。

A 冻符「Perfect Freeze」魔法 询问在某一点放一只青蛙跳过一个区间的直线和点后会在哪里。

B 冰块「Great Crusher」魔法 可以让区间内所有直线和点关于给定直线对称。

C 雹符「Hailstorm」魔法 可以让区间内所有直线和点绕一点旋转若干角度。

琪露诺的数学实在太好了,以至于无法清晰地描述这些操作。所以,她让八云蓝做了一份形式化体面放在后面。

总之,请你预测每个A魔法青蛙最后的位置,因为琪露诺无法理解⑨以上的数字,所以只要对 998244353 取模糊弄她一下就好了。

解析几何中有一些对称和旋转的操作。

为了清楚地描述这两种变换,我们定义函数 f(A,B)。其中 A 为一个二元组表示点的坐标 (x,y),B 为一个三元组或一个五元组。

如果 B 为三元组 (a,b,c) 则 f(A,B) 返回 (x,y) 关于直线 ax+by+c=0 的对称点

如果 B 为五元组 (x0,y0,a,b,c) 则 f(A,B) 返回 (x,y) 绕点 (x0,y0) 逆时针旋转 θ 后的坐标,其中 sinθ=ac,cosθ=bc,保证 a2+b2=c2。

解析几何中还有直线关于直线对称这样的操作。为了描述这种操作,我们定义 g(A,B):

如果 A 为五元组 (x0,y0,a,b,c),则计算 (x′0,y′0)=f((x0,y0),B),并返回新的五元组 (x′0,y′0,a,b,c)。

如果 A 为三元组 (a,b,c),则返回一组 (a′,b′,c′) 满足 {(x,y)|a′x+b′y+c′=0}={f((x,y),B)|ax+by+c=0}。可以证明这样的 a′,b′,c′ 总是存在的。

现在有一个长度为 n 的序列 Ai,每个元素为三元组或五元组。有三种操作:

给定 x,y,l,r,询问 f(f(…f((x,y),Al)…,Ar−1),Ar)。

给定 a,b,c,l,r,把 l≤i≤r 的 Ai 变成 g(Ai,(a,b,c))。

给定 x0,y0,a,b,c,l,r,把 l≤i≤r 的 Ai 变成 g(Ai,(x0,y0,a,b,c))。

由于解析几何总是要求精确解但是计算机有精度限制,你只需要输出对 998244353 取模的结果进行验算即可。

可以证明答案一定是有理数。

输入格式

第一行两个整数 n,q。

接下来 n 行,每行首先有一个整数 op。

如果 op=1,则输入一个三元组 (a,b,c),否则如果 op=2 输入一个五元组 (x0,y0,a,b,c)。

接下来 q 行,每行首先有一个整数 op。

如果 op=1,则输入四个整数 x,y,l,r,如果 op=2,输入一个三元组 (a,b,c) 和两个整数 l,r,否则如果 op=3 则输入一个五元组 (x0,y0,a,b,c) 和两个整数 l,r。

输出格式

对于每个操作1输出最终的点的坐标对 998244353 取模的结果。

样例 #1

样例输入 #1

2 8
1 1 -1 0
2 1 1 3 4 5
1 1 6 1 1
1 1 6 2 2
2 1 0 0 1 2
1 -1 6 1 1
1 -1 6 2 2
3 0 0 1 0 1 1 2
1 -1 4 1 1
1 -1 4 2 2

样例输出 #1

6 1
998244351 5
998244347 1
998244349 5
4 998244352
998244349 3

提示

对于 100% 的数据满足 1≤n,q≤105。

任何三元组 (a,b,c) 满足 −109≤a,b,c≤109,a2+b2≢0(mod998244353)。

任何五元组 (x0,y0,a,b,c) 满足 −109≤x0,y0,a,b,c≤109,c≢0(mod998244353),a2+b2=c2。

子任务编号 分数 n,q≤ 特殊性质 1 10 100 2 103 3 15 105 输入没有五元组 4 输入没有三元组 5 所有询问 op=1 6 35

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 8
1 1 -1 0
2 1 1 3 4 5
1 1 6 1 1
1 1 6 2 2
2 1 0 0 1 2
1 -1 6 1 1
1 -1 6 2 2
3 0 0 1 0 1 1 2
1 -1 4 1 1
1 -1 4 2 2
6 1
998244351 5
998244347 1
998244349 5
4 998244352
998244349 3