← 返回题目列表

AtCoder · pakencamp_2024_day3_1_d

D. 凸

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

配点 : 100 点

問題文

正整数 N,M 和 xy 平面上的一点是 给出了 N 。 第i 点是 (X_i,Y_i) 。然而, 3 点 (X_i,Y_i),(X_j,Y_j),(X_k,Y_k) (1 \leq i < j < k \leq N) 保证不共线。 请解决以下有关 k=1,2,\dots,N 的问题。

\{1,2,\dots,k \} 的大小是 3 的子集 对于 S= \{ s_1,s_2,\dots,s_{|S|} \} ,点集 \{ (X_{s_1},Y_{s_1}),(X_{s_2},Y_{s_2}),\dots,(X_{s_{|S|}},Y_{s_{|S|}}) \} 的凸包面积 2 次 可以证明 f(S) 。f(S) 总是一个整数,所以

\displaystyle\sum_{S \subseteq \{ 1,2,\dots,k \} ,|S| \geq 3} f(S)

的 M 求余数。

制約

  • 3 \leq N \leq 1000
  • 2 \leq M \leq 10^9+9
  • 0 \leq X_i,Y_i \leq 10^9 (1 \leq i \leq N)
  • 3 点 (X_i,Y_i),(X_j,Y_j),(X_k,Y_k) 不共线 如果正确答案是满足 (1 \leq i < j < k \leq N)
  • 所有输入均为整数

部分点

  • N \leq 100 的数据集,30 给予积分。
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 打印 70 给予积分。

入力

输入是按以下格式从标准输入给出的。

N M
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

i (1 \leq i \leq N) 在行中 k=i 的答案。


入力例 1

3 998244353
0 2
2 0
2 2

出力例 1

0
0
4

入力例 2

4 100
1 3
3 1
4 4
7 1

出力例 2

0
0
8
60

入力例 3

5 17
1 8
10 11
21 5
73 99
3 17

出力例 3

0
0
2
5
0