Khoảng Liên Sao

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie tìm thấy một trục số có $N$ điểm ( $2 \leq N \leq 5 \cdot 10^{5}$ ), ban đầu tất cả đều trắng. Cô có thể thực hiện các phép tô, mỗi phép chọn vị trí $i$ và số nguyên dương $x$ , tô đỏ các điểm $[i, i + x - 1]$ và tô xanh các điểm $[i + x, i + 2 x - 1]$ . Tất cả các khoảng phải rời nhau và nằm trong trục số.

Cho xâu ưu tiên $s$ độ dài $N$ với các ký tự R (phải đỏ), B (phải xanh), và X (không ràng buộc), đếm số cách tô hợp lệ modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu: số nguyên $N$ .
Dòng thứ hai: xâu $s$ độ dài $N$ .

Dữ liệu ra

In ra số cách tô hợp lệ modulo $10^{9} + 7$ .

Ràng buộc

Test $4$ : $N \leq 500$
Test $5$ - $6$ : $N \leq 10^{4}$
Test $7$ - $13$ : Có nhiều nhất $100$ ký tự khác X
Test $14$ - $23$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
6 RXXXXB	5	Có 5 cách tô hợp lệ thỏa mãn điểm 1 đỏ và điểm 6 xanh.
6 XXRBXX	6	Có 6 cách tô hợp lệ.
12 XBXXXXRXRBXX	18	Có 18 cách tô hợp lệ.

Bình luận

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