Nộp bài
Điểm:
1700 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Trọng số của một xâu s chỉ gồm các chữ cái trong bảng chữ cái tiếng Anh được tính bằng tổng các giá trị i \times v_{s_i}^2 với 1 \le i \le |s|, trong đó |s| là độ dài xâu s, s_i là ký tự thứ i của xâu s, v_{s_i} là vị trí của ký tự s_i trong bảng chữ cái.
Ví dụ, trọng số của xâu s = abca
sẽ được tính như sau:
- Với i = 1, ta có 1 \times v_{s_1}^2 = 1 \times 1^2 = 1.
- Với i = 2, ta có 2 \times v_{s_2}^2 = 2 \times 2^2 = 8.
- Với i = 3, ta có 3 \times v_{s_3}^2 = 3 \times 3^2 = 27.
- Với i = 4, ta có 4 \times v_{s_4}^2 = 4 \times 1^2 = 4.
- Vậy trọng số của xâu s bằng 1 + 8 + 27 + 4 = 40.
Một xâu con của xâu t là xâu t khi xóa đi một số ký tự (có thể không xóa ký tự nào), và giữ nguyên thứ tự của các ký tự còn lại. Ví dụ ab
, bc
, abdc
hay abc
là xâu con của abdc
nhưng acd
hay cb
thì không.
Tính tổng trọng số của tất cả các xâu con của xâu t.
Input, Output và Subtasks
Input: (bàn phím
)
- Một dòng duy nhất gồm xâu t có độ dài không quá 2 \times 10^7.
Output: (màn hình
)
- Một dòng duy nhất là trọng số của các xâu con của xâu t. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra trọng số sau khi đã chia lấy dư cho 10^9 + 7.
Subtasks
- Subtask 1 (30\%): Độ dài xâu t không vượt quá 20.
- Subtask 2 (25\%): Độ dài xâu t không vượt quá 200.
- Subtask 3 (20\%): Độ dài xâu t không vượt quá 2000.
- Subtask 4 (15\%): Độ dài xâu t không vượt quá 2 \times 10^5.
- Subtask 5 (10\%): Độ dài xâu t không vượt quá 2 \times 10^7.
Sample
Input (bàn phím
)
abc
Output (màn hình
)
100
Note
- Các xâu
a
,b
,c
có trọng số lần lượt là 1, 4, 9. - Các xâu
ab
,ac
,bc
có trọng số lần lượt là 9, 19, 22. - Xâu
abc
có trọng số là 36.
Vậy tổng trọng số của các xâu con của xâu abc
là 100.
Bình luận