trang chủ / đề bài / icpc21_mt_f

Số ký tự duy nhất

Đề bài

Mô tả

Gọi f(X) là số ký tự xuất hiện đúng một lần trong xâu X. Ví dụ: f(a)=1, f(abde)=4, f(abded)=3, f(abba)=0.

Cho xâu S. Hãy tính giá trị của biểu thức sau:

G(S)=∑i=1|S|∑j=i|S|f(S[i..j])

trong đó S[i..j] là xâu con liên tiếp từ vị trí i đến vị trí j của S (đánh chỉ số từ 1).

Dữ liệu vào

  • Dòng đầu tiên chứa số bộ test T (1≤T≤10).
  • Mỗi bộ test gồm một dòng chứa xâu S (1≤|S|≤105) chỉ gồm các chữ cái Latin in thường (a đến z).

Dữ liệu ra

Với mỗi bộ test, in ra giá trị G(S).

Ràng buộc

  • 1≤T≤10.
  • 1≤|S|≤105, S chỉ gồm chữ cái in thường.

Ví dụ

Input Output Giải thích
4
z
icpccentral
abcde
uuuu
1
212
35
4
Với S=abcde, mọi xâu con có các ký tự phân biệt nên G bằng tổng độ dài các xâu con: 5·1+4·2+3·3+2·4+1·5=35. Với S=uuuu, chỉ 4 xâu con độ dài 1 có f=1.
5
a
ab
aba
abab
abcabc
1
4
8
12
36
Ví dụ bổ sung (không có trong đề gốc). Với S=aba: các xâu con a, b, a, ab, ba, aba có f lần lượt là 1,1,1,2,2,1, tổng bằng 8.

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