考虑平面直角坐标系上的直线 y=ax+bc,作出所有 x=k (k∈Z) 和所有 y=h (h∈Z)。
从左往右扫描这条直线,当遇到该直线与某水平线的交点,则记录一个 U;遇到该直线与某垂直线的交点,则记录一个 R。规定整点时水平线的优先级更高。
我们记录的 U,R 实际上可以是任意幺半群信息,当然相同的字母对应相同的元素。
对于参数 n,a,b,c 和 U,R 执行递归过程 f(n,a,b,c,U,R):表示在 y=ax+bc (x∈(0,n]) 上考虑这个问题。
根据欧几里得过程,考虑讨论:
若 a≥c,考虑如何将 a 取模 c。
事实上这就是 f(n,amodc,b,c,U,U⌊a/c⌋R)。
若 a<c,考虑如何交换 a,c。
记 m=⌊an+bc⌋ 即 U 的个数。
如果 m=0,以 Rn 终止递归。
否则,简单计算得,可以通过在开头补上 R⌊(c−b−1)/a⌋U,结尾补上 Rn−⌊(cm−b−1)/a⌋ 的方式,递归到 f(m−1,c,b,a,R,U)。
以下是我擅自从叉姐代码改出来的的一个板子:
1 |
|
这里是一个 LibreOJ 板子的 AC 代码:
1 |
|