trang chủ / đề bài / icpc24_reg_i

Vương quốc Inversland

Đề bài

Mô tả

Vương quốc Inversland phát hành n mệnh giá tiền, mệnh giá thứ i có giá trị 1pi đô la. Để việc đổi tiền càng thêm rắc rối, tất cả các giá trị pi đều là các số nguyên tố đôi một phân biệt.

Một nhược điểm của bộ mệnh giá này là trong một số trường hợp, để trả một khoản tiền nhất định, người trả và người nhận buộc phải trao đổi tiền qua lại. Ví dụ, với n=2 và p={3,5}, để trả 715 đô la, người trả có thể đưa hai tờ 13 và nhận lại một tờ 15 tiền thối. Có thể chứng minh rằng không có cách nào trả 715 đô la mà người nhận không phải thối lại tiền. Ngược lại, để trả 815 đô la, người trả có thể đưa một tờ 13 và một tờ 15 mà không cần nhận tiền thối.

Để đánh giá mức độ nghiêm trọng của nhược điểm này, chính phủ muốn đếm số khoản tiền thỏa mãn đồng thời hai điều kiện:

  • có thể trả khoản tiền đó bằng các mệnh giá hiện có, và
  • không thể trả khoản tiền đó mà người nhận không phải thối lại tiền.

Cho n mệnh giá, chính phủ nhờ bạn, một đội lập trình đã giành quyền thi khu vực, đếm số khoản tiền như vậy và in ra kết quả theo modulo 998244353. Nếu có vô số khoản tiền như vậy, hãy thông báo điều đó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤10000): số bộ test. Mỗi bộ test gồm:

  • Dòng đầu tiên chứa số nguyên n (2≤n≤200000): số mệnh giá.
  • Dòng thứ hai chứa n số nguyên tố phân biệt p1,p2,…,pn (2≤pi<998244353) mô tả bộ mệnh giá.

Tổng n trên tất cả các bộ test không vượt quá 200000.

Dữ liệu ra

Với mỗi bộ test, nếu có vô số khoản tiền thỏa mãn, in ra infinity. Ngược lại, in ra số khoản tiền thỏa mãn theo modulo 998244353.

Ràng buộc

  • 1≤t≤10000
  • 2≤n≤200000, tổng n không vượt quá 200000
  • 2≤pi<998244353, các pi là số nguyên tố đôi một phân biệt

Ví dụ

Input Output Giải thích
2
2
3 5
10
941 947 953 967 971 977 983 991 997 998244341
4
679849251
Bộ test thứ nhất: mọi khoản tiền dạng x15 với x nguyên dương đều trả được bằng các tờ 13 và 15. Trong đó các khoản 115,215,415,715 không thể trả mà không cần thối tiền.
2
3
2 3 5
2
2 7
15
3
Bộ test thứ hai: các khoản cần thối tiền là 114,314,514.

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