trang chủ / đề bài / icpc22_reg_b

Gán nhị phân

Đề bài

Mô tả

Vương là một trong những nhà toán học vĩ đại nhất mọi thời đại! Sở thích của anh là tìm ra các tính chất toán học của mọi thứ, đôi khi của cả những thứ không tồn tại! Vào ngày sinh nhật, người bạn lập trình viên tặng anh một xâu nhị phân S độ dài n. Sau một lúc, anh tìm ra hai tính chất rất thú vị của S:

  • X(S): độ dài của xâu ngắn nhất không phải là dãy con của S.
  • Y(S): số xâu độ dài X(S) không phải là dãy con của S.

Thấy Vương thích thú tìm ra hai tính chất này, người bạn lập trình viên nghĩ rằng sẽ thật tuyệt nếu thay đổi xâu S một chút. Anh lần lượt thực hiện q thao tác thay đổi xâu S. Mỗi thao tác thuộc một trong các loại sau:

  • 0 l r: gán Sl,Sl+1,…,Sr bằng 0.
  • 1 l r: gán Sl,Sl+1,…,Sr bằng 1.
  • F l r: lật Sl,Sl+1,…,Sr, tức là với mọi l≤i≤r, nếu Si bằng 0 thì đổi thành 1, ngược lại đổi thành 0.

Và tất nhiên, với mỗi phiên bản đã thay đổi của S, Vương cũng vui vẻ tìm X(S) và Y(S), vì hôm nay là sinh nhật anh!

Nhưng một câu đố thì không thể thiếu đáp án. Cho xâu S và danh sách q thao tác thay đổi, hãy giúp người bạn lập trình viên tìm X(S) và Y(S) sau mỗi thao tác, để anh có thể đối chiếu với kết quả của Vương. Vì đáp án có thể rất lớn, hãy in Y(S) theo modulo 109+7.

Xâu a là dãy con của xâu b nếu có thể nhận được a từ b bằng cách xóa đi một số (có thể không xóa, hoặc xóa hết) ký tự. Ví dụ, "bd", "acd", "b" là dãy con của "abcd", còn "da" thì không.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và q (1≤n,q≤100000) là độ dài xâu S và số thao tác.
  • Dòng thứ hai chứa xâu nhị phân S độ dài n.
  • Dòng thứ i trong q dòng tiếp theo mô tả thao tác thứ i ở một trong các dạng sau:
    • 0 l r (1≤l≤r≤n): gán Sl,Sl+1,…,Sr bằng 0.
    • 1 l r (1≤l≤r≤n): gán Sl,Sl+1,…,Sr bằng 1.
    • F l r (1≤l≤r≤n): lật Sl,Sl+1,…,Sr.

Dữ liệu ra

Sau mỗi thao tác, in ra một dòng gồm hai số nguyên X(S) và Y(S) modulo 109+7.

Ràng buộc

  • 1≤n,q≤100000
  • 1≤l≤r≤n

Ví dụ

Input Output Giải thích
4 3
0110
0 2 3
1 3 4
F 2 3
1 1
2 1
3 4
Ban đầu S=0110 (với X(S)=3, Y(S)=5: các xâu 000,001,100,101,111, nhưng không cần in). Sau thao tác 1, S=0000: chỉ có xâu 1 độ dài 1 không là dãy con. Sau thao tác 2, S=0011: xâu 10 là xâu duy nhất độ dài 2 không là dãy con. Sau thao tác 3, S=0101: các xâu ngắn nhất không là dãy con là 000,100,110,111.
2 4
01
F 1 2
F 1 1
0 2 2
1 1 2
2 3
1 1
1 1
1 1
Lần lượt S=10 (các xâu 00,01,11), S=00, S=00, S=11. Ví dụ bổ sung (không có trong đề gốc).

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