#P3490. Pa2011 Laser Pool

    ID: 2702 传统题 5000ms 128MiB 尝试: 6 已通过: 5 难度: 9 上传者: 标签>难度分类省选/NOI-多项式与生成函数卷积转化NTT图论功能图线性代数与代数置换循环分解排序与序列处理一维前缀和二分查找位运算位集求并位计数组合数学容斥原理模拟与实现技巧半开区间统一CF2700

Pa2011 Laser Pool

Laser Pool

题目描述

Byteotia 的居民喜欢打激光台球。球桌大小为 n×mn\times m,四周的挡边宽 1/41/4,台球直径为 1/21/2。挡边上有 nn 对产生水平光束的发射器和 mm 对产生竖直光束的发射器,每对发射器可以独立开关。以球桌的一角为原点,第 ii 道水平光束与第 jj 道竖直光束在 (j−12,i−12)(j-\tfrac12,i-\tfrac12) 相交。

为方便表示,将球心和光束的坐标都平移 (12,12)(\tfrac12,\tfrac12)。于是球心可运动的范围是从 (1,1)(1,1) 到 (m,n)(m,n) 的矩形,第 ii 道水平光束位于 y=iy=i,第 jj 道竖直光束位于 x=jx=j。

小球以给定的初速度在无摩擦的桌面上运动。撞到左右边界时,水平速度反向。撞到上下边界时,竖直速度反向。撞到角上时,两项速度都反向。

小球每次遇到至少一道开启的光束就触发一次信号。同一时刻若遇到两道光束,只算一次。给定运动的起点、初速度和时长 tt,统计从开始到结束触发信号的次数。如果起点恰好在开启的光束上,初始时刻也计入。

输入格式

第一行包含两个整数 n,mn,m。

第二行是一个长度为 nn 的 01 串。第 ii 个字符为 1 表示第 ii 道水平光束开启,为 0 表示关闭。

第三行是一个长度为 mm 的 01 串,表示各道竖直光束的状态。

第四行包含询问数 qq。接下来 qq 行,每行包含五个整数 x,y,vx,vy,tx,y,v_x,v_y,t,表示小球从 (x,y)(x,y) 出发、初速度为 (vx,vy)(v_x,v_y)、运动 tt 个时间单位。

输出格式

输出 qq 行,每行一个整数,第 ii 行表示第 ii 次询问的信号次数。

样例 #1

4 6
1010
010110
1
5 2 1 1 8
6

样例中的开启光束、初始球心与反弹轨迹

数据范围

3≤n,m≤1053\le n,m\le 10^5,1≤q≤1041\le q\le 10^4,1≤t≤1091\le t\le 10^9。

1<x<m1<x<m,1<y<n1<y<n,vx,vy∈{−1,1}v_x,v_y\in\{-1,1\}。