题目内容

塔子哥对于一个字符串的权值定义为一个字符串中 "tzzt" 的子串的数量。例如，"tzzt" 的权值为$1$，"tzztzzt" 的权值为 $2$，"tzzzt" 的权值为 $0$ 。

现在，塔子哥给你一个仅由 't' 和 'z' 构成的字符串，问你这个字符串的所有子串的权值之和。

思路: 思维

考虑字符串中每个 tzzt 对答案的贡献。

下标从 $0$ 开始。假设是 s[i, i+3] = "tzzt"，那么这个 tzzt 对于答案的贡献为：所有 $l <= i, r >= i+3$ 的字符串。

这样的字符串一共有 $(l+1) \times (n-r)$ 个。