题目描述

小红最近做了很多字符串的题目，普通的字符串题已经难不倒他了！

但是这次他遇到了一个难题：给定一个字符串，有多少子序列满足首尾字符是相同的？

思路：思维题

给定一个字符串，求其有多少子序列满足首尾字符相同。

长度为1的子序列显然满足，当长度大于等于2时呢？

我们来看一个例子：abca。当长度大于等于2时，首先要确保首尾字符相同，这时，其中间的字符就可以任意选了。根据数学知识我们知道，当中间字符数为 $x$ 时，选取任意个的方法有 $2^x$ 种。

所以我们就只要找到两个相同字符后，直接计算答案即可。

In following contests: