#P18836. [Croatian CPC2020] Brzi Biljar

[Croatian CPC2020] Brzi Biljar

[Croatian CPC2020] Brzi Biljar

题目描述

在平面直角坐标系中,有一张正方形台球桌,它的四个顶点分别为 (L,L)(L,L)、(L,−L)(L,-L)、(−L,L)(-L,L) 和 (−L,−L)(-L,-L)。

台球初始静止于 (x1,y1)(x_1,y_1),球洞位于 (x2,y2)(x_2,y_2)。这两个位置不同,且都严格位于球桌内部。将台球和球洞均视为点。

击球后,台球沿直线运动。碰到球桌边缘时,台球按入射角等于反射角的规则反弹,然后继续直线运动。台球一旦到达球洞或球桌的任意一个顶点,就立即停止。

已知台球最终进入了球洞,且途中反弹次数不超过 nn。对于每个整数 k=0,1,…,nk=0,1,\ldots,n,求恰好反弹 kk 次后进入球洞的不同运动路径数量。不同路径按台球经过的运动轨迹区分,与运动速度无关。

下图展示了样例 1 中恰好反弹一次的所有可能路径:

反弹一次的三条路径

可以证明,每个答案均为有限整数,且能够用有符号 32 位整数表示。

输入格式

第一行包含两个整数 L,nL,n(2≤L≤1062\le L\le10^6,1≤n≤5001\le n\le500)。

第二行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2(−L<x1,y1,x2,y2<L-L<x_1,y_1,x_2,y_2<L),保证 (x1,y1)≠(x2,y2)(x_1,y_1)\ne(x_2,y_2)。

输出格式

输出一行 n+1n+1 个整数,依次表示 k=0,1,…,nk=0,1,\ldots,n 时的答案。

样例 1

输入

2 1
-1 1 -1 -1

输出

1 3

样例 2

输入

4 3
0 0 1 1

输出

1 4 6 12