Kỳ Vọng Xuất Hiện Xâu Mẫu
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một xâu mẫu $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh viết thường (a đến z).
Một máy phát ký tự ngẫu nhiên liên tục sinh ra từng chữ cái viết thường độc lập và đều (mỗi chữ cái trong a–z có xác suất $\frac{1}{26}$). Máy dừng lại ngay khi xâu $S$ xuất hiện như một xâu con liên tiếp ở cuối dãy ký tự đã sinh.
Hãy tính kỳ vọng số ký tự máy cần sinh ra cho đến khi dừng lại, theo modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa xâu $S$ ($1 \le |S| \le 10^5$, chỉ gồm các ký tự
a..z).
Dữ liệu ra
- In ra một số nguyên duy nhất là kỳ vọng số ký tự cần sinh theo modulo $10^9 + 7$.
Ví dụ
Input
ab
Output
676
Giải thích
Với $S = \text{"ab"}$ và bảng chữ cái $26$ ký tự, kỳ vọng là $26^2 = 676$.
Giới hạn
- $1 \le |S| \le 10^5$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion