← 返回题目列表

AtCoder · abc396_f

I. 旋转反转

中文机器翻译题面 查看原题

分数: 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