trang chủ / đề bài / icpc23_mn_i

Đa giác phức tạp

Đề bài

Mô tả

Vào một ngày đẹp trời ở công viên Đầm Sen, anh Đôn cầm một túi que với nhiều độ dài khác nhau. Anh nhận ra rằng với những que này, một số que có thể ghép lại thành những đa giác thú vị, còn một số thì không.

Ví dụ, anh Đôn có ba que trong túi với độ dài lần lượt là 5, 3 và 4. Anh biết rằng với ba que này, anh có thể xếp thành một tam giác đẹp. Tuy nhiên, hôm trước, khi anh Đôn có bốn que với độ dài 5, 3, 4 và 20, anh biết không có cách nào xếp chúng thành một tứ giác hợp lệ.

Nhiệm vụ của bạn: giúp anh Đôn tính số cách khác nhau để chọn các que từ túi tạo thành các đa giác khác nhau. Hai đa giác được coi là khác nhau nếu có ít nhất một que được dùng trong đa giác này mà không có trong đa giác kia, và ngược lại.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n (1≤n≤5000): số que trong túi của anh Đôn.

Dòng thứ hai chứa n số nguyên l1,l2,…,ln (1≤li≤5000): độ dài của n que tương ứng.

Dữ liệu ra

In ra một số nguyên là số đa giác khác nhau có thể tạo được, lấy modulo 109+7.

Ràng buộc

  • 1≤n≤5000
  • 1≤li≤5000

Ví dụ

Input Output Giải thích
4
2 2 2 2
5 Có 4 tam giác với các cạnh {2,2,2} và 1 tứ giác với các cạnh {2,2,2,2}.
5
1 2 3 4 5
9 Có 9 đa giác: {2,3,4}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0