分数: 500 点
问题陈述
给你整数 N, M 和一个长度-N 非负整数序列 A = (A_1, A_2, \ldots, A_N).
对于 k = 0, 1, \ldots, M-1,解决以下问题:
定义一个整数序列 B = (B_1, B_2, \ldots, B_N) 这样 B_i 是余数 A_i + k 除以 M。找到反转数 B.
反转数是多少?
序列的反转数 (A_1, A_2, \dots, A_N) 是整数对的数量 (i, j) 满意 1 \le i < j \le N 和 A_i > A_j.约束
- 1 \le N,M \le 2\times 10^5
- 0 \le A_i < M
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_N
输出
打印 M 行。
的 i第行 (1 \le i \le M) 应包含案例的答案 k = i-1.
示例输入 1
3 3 2 1 0
示例输出 1
3 1 1
- 对于 k=0: B=(2, 1, 0)。反转数为 3.
- 对于 k=1: B=(0, 2, 1)。反转数为 1.
- 对于 k=2: B=(1, 0, 2)。反转数为 1.
示例输入 2
5 6 5 3 5 0 1
示例输出 2
7 3 3 1 1 5
示例输入 3
7 7 0 1 2 3 4 5 6
示例输出 3
0 6 10 12 12 10 6