trang chủ / đề bài / icpc25_mb_h

Biểu thức

Đề bài

Mô tả

Cho một danh sách gồm n số phân biệt, Jack muốn tạo các biểu thức chỉ dùng các số trong danh sách cùng với phép cộng, phép nhân và dấu ngoặc (mỗi số có thể được dùng nhiều lần). Jack định nghĩa quan hệ "~" giữa hai biểu thức như sau:

  • a~(a)
  • a+b~b+a và a×b~b×a
  • a+(b+c)~(a+b)+c~a+b+c và a×(b×c)~(a×b)×c~a×b×c
  • 1×a~a
  • Nếu a~b và b~c thì a~c

Hai biểu thức a và b được coi là giống nhau khi và chỉ khi a~b.

Hãy đếm số biểu thức khác nhau có giá trị bằng m.

Dữ liệu vào

Dòng đầu tiên chứa T (T≥1) là số bộ dữ liệu. Mỗi bộ dữ liệu có dạng sau:

  • Dòng đầu tiên chứa hai số n,m (1≤n≤m≤5×105).
  • Dòng thứ hai chứa n số 1≤a1<a2<⋯<an≤m là các số trong danh sách.

Dữ liệu đảm bảo tổng m của tất cả các bộ dữ liệu không vượt quá 5×105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in đáp án trên một dòng. Vì đáp án có thể rất lớn, hãy in nó theo modulo 998244353.

Ràng buộc

  • T≥1.
  • 1≤n≤m≤5×105, 1≤a1<a2<⋯<an≤m.
  • Tổng m của tất cả các bộ dữ liệu không vượt quá 5×105.

Ví dụ

Input Output Giải thích
5
1 1
1
1 99
2
5 5
1 2 3 4 5
1 10
1
8 5000
2 3 5 7 11 13 17 19
1
0
10
10
299891645
Ở bộ thứ ba, 5 có thể biểu diễn bằng 1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 1+4, 1+2×2, 1+(1+1)×2, 1+(1+1)×(1+1), 2+3, 5. Ở bộ thứ tư, 10 có thể biểu diễn bằng 1+1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+(1+1)×(1+1), 1+1+1+1+(1+1+1)×(1+1), 1+1+(1+1)×(1+1+1+1), 1+1+(1+1)×(1+1)×(1+1), 1+1+(1+1)×(1+1)+(1+1)×(1+1), 1+(1+1+1)×(1+1+1), (1+1)×(1+1+1+1+1), (1+1)×(1+(1+1)×(1+1)), (1+1)×(1+1)+(1+1)×(1+1+1).
2
1 4
2
2 6
2 3
2
4
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: 2+2 và 2×2. Bộ thứ hai: 2+2+2, 2+2×2, 3+3 và 2×3.

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