trang chủ / đề bài / icpc26_mt_n

Đèn hoa đăng trên sông Hương

Đề bài

Mô tả

Trong dịp Festival Huế, một dãy gồm n vị trí được chuẩn bị dọc bờ sông Hương. Các vị trí được đánh số từ 1 đến n từ trái sang phải. Mỗi vị trí hoặc có đúng một chiếc đèn hoa đăng, hoặc để trống, được mô tả bởi xâu s độ dài n: ký tự thứ i của s là 1 nếu vị trí i có đèn, và là 0 nếu vị trí i trống.

Dòng nước đẩy mỗi chiếc đèn đi đúng hai vị trí một lần. Một bước di chuyển đưa một chiếc đèn từ vị trí i sang vị trí j, với j=i−2 hoặc j=i+2. Bước di chuyển chỉ được phép khi vị trí j thuộc dãy, tức là 1≤j≤n, và khi cả vị trí j lẫn vị trí nằm giữa i và j đều đang trống.

Mọi chiếc đèn trông giống hệt nhau, nên một cách sắp xếp chỉ được xác định bởi tập các vị trí có đèn. Có thể thực hiện bao nhiêu bước di chuyển cũng được, theo thứ tự bất kỳ.

Ban tổ chức kiểm tra q đoạn của dãy. Với một đoạn được mô tả bởi hai số nguyên l và r, xét các vị trí l,l+1,…,r cùng với các chiếc đèn mà các vị trí đó có lúc ban đầu, và coi chúng là một dãy riêng: trong khi kiểm tra đoạn này, đèn chỉ được di chuyển giữa các vị trí từ l đến r, phần còn lại của dòng sông được bỏ qua.

Với mỗi đoạn, hãy xác định có bao nhiêu cách sắp xếp khác nhau của đoạn đó có thể thu được. Cách sắp xếp ban đầu của đoạn cũng được tính. Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo 998244353.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q (1≤n≤2·105, 1≤q≤2·105): số vị trí và số đoạn cần kiểm tra.
  • Dòng thứ hai chứa xâu s độ dài n, chỉ gồm các ký tự 0 và 1.
  • Mỗi dòng trong q dòng tiếp theo chứa hai số nguyên l và r (1≤l≤r≤n), mô tả một đoạn của dãy.

Dữ liệu ra

In ra q dòng. Dòng thứ i chứa số cách sắp xếp khác nhau có thể thu được trong đoạn thứ i, lấy theo modulo 998244353.

Ràng buộc

  • 1≤n≤2·105, 1≤q≤2·105.
  • s có độ dài n và chỉ gồm các ký tự 0 và 1.
  • 1≤l≤r≤n.

Ví dụ

Input Output Giải thích
7 6
1001010
1 7
2 7
2 4
4 6
3 3
2 5
4
3
2
1
1
2
Ở đoạn thứ hai, các vị trí từ 2 đến 7 lúc đầu là 001010, và thu được đúng ba cách sắp xếp: 001010, 100010 và 101000. Ở đoạn thứ ba, các vị trí từ 2 đến 4 lúc đầu là 001, chiếc đèn có thể trôi sang trái hai vị trí, cho hai cách 001 và 100. Chiếc đèn này nằm ở vị trí 4 của dòng sông nhưng ở vị trí thứ ba của đoạn, và chính vị trí trong đoạn quyết định nó đi được đến đâu. Ở đoạn thứ tư, các vị trí từ 4 đến 6 lúc đầu là 101 và không có bước di chuyển nào, vì mỗi chiếc đèn bị chiếc kia chặn. Ở đoạn thứ năm, vị trí 3 không có đèn, nên cách sắp xếp rỗng là cách duy nhất.
6 4
110011
1 6
2 5
3 6
1 1
5
3
3
1
Ví dụ bổ sung (không có trong đề gốc). Đoạn thứ nhất thu được 110011, 111001, 111100, 100111 và 001111. Đoạn thứ hai (1001) thu được 1001, 1100 và 0011. Đoạn thứ ba (0011) thu được 0011, 1001 và 1100. Đoạn thứ tư chỉ có một chiếc đèn ở vị trí duy nhất.

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