hướng dẫn em bài #1355. TRICOUNT - Đếm số tam giác với ạ

eouheo 2021-12-01 20:27:47

Tổng cộng 2 trả lời

eouheo

Em cảm ơn anh nhiều ạ.

Trùm CUỐI

Bạn hỏi bài 1355. TRICOUNT - Đếm số tam giác nhỉ? Mình hướng dẫn qua cách tính thế này:

  • Nếu ta coi không có 2 đường nào song song (hoặc trùng nhau) thì sẽ có tất cả C^3_n=\frac{n\times (n-1) \times (n-2)}{6} tam giác.
  • Giờ ta tính những nhóm đường song song (hoặc trùng nhau): Mỗi nhóm k đường song song (hoặc trùng nhau) sẽ giảm đi số tam giác là C^3_k+C^2_k \times (n-k) tam giác.

Việc tính toán theo module 10^9+7 , do có chia cho 6 và chia cho 2 nên sẽ phải dùng định lý Fermat nhỏ hoặc nếu các bạn tính khéo léo một chút thì sẽ không cần dùng đến định lý này.