疯狂的馒头
题目描述
CQF 把 N 个白馒头排成一列,从 1 到 N 编号。然后按顺序进行 M 次染色,每次把连续的一段馒头改为同一种颜色。
给定两个正整数 p,q。第 i 次操作的两个端点为
li=(ip+q)modN+1,ri=(iq+p)modN+1.
把这两个端点之间的全部馒头染成颜色 i,包括两个端点。较早的颜色会被覆盖,始终未染色的馒头颜色为 0。求所有操作完成后每个馒头的颜色。
输入格式
一行四个正整数 N,M,p,q。
输出格式
输出 N 行,第 i 行是第 i 个馒头的最终颜色。
4 3 2 4
2
2
3
0
数据范围
| 数据比例 |
N 的上限 |
M 的上限 |
| 20% |
1000 |
10000 |
| 40% |
10000 |
100000 |
| 60% |
50000 |
500000 |
| 80% |
300000 |
3000000 |
| 100% |
1000000 |
10000000 |
保证 1≤Mp+q≤231−1,1≤Mq+p≤231−1。