Đường đi Palindrome (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Cho lưới $N \times N$ ( $1 \leq N \leq 500$ ), mỗi ô chứa một chữ cái in hoa từ A–Z. Bessie đi từ góc trên-trái đến góc dưới-phải, chỉ được di chuyển sang phải hoặc xuống dưới.

Mỗi đường đi tạo thành một chuỗi $2 N - 1$ ký tự. Đếm số đường đi tạo thành chuỗi palindrome, lấy modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu: số nguyên $N$
$N$ dòng tiếp theo: mỗi dòng $N$ ký tự in hoa mô tả lưới

Dữ liệu ra

Số đường đi palindrome modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 500$

Ví dụ

Input	Output	Giải thích
4 ABCD BXZX CDXB WCBA	12	Có 4 chuỗi palindrome phân biệt: "ABCDCBA" (1 cách), "ABCWCBA" (1 cách), "ABXZXBA" (6 cách), "ABXDXBA" (4 cách). Tổng = 12 đường đi.

Bình luận

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