思路：思维题

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

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

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

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

时间复杂度为$O(26N)$

代码

C++

AC

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long

void solve() {
    string s;
    cin >> s;  // 输入字符串 s
    const int mod = 998244353;  // 定义常数 mod
    ll ans = 0;  // 初始化答案 ans

    // 遍历字母表的每个字母
    for (int i = 0; i < 26; i++) {
        ll pre = 0;  // 初始化前缀和 pre
        for (int j = 1; j < s.size(); j++) {
            pre *= 2;  // 左移一位，相当于乘以 2
            pre %= mod;  // 对前缀和取模
            if (s[j - 1] - 'a' == i) pre++;  // 如果前一个字符是当前字母，增加前缀和
            if (s[j] - 'a' == i) ans += pre;  // 如果当前字符是当前字母，增加答案 ans
            ans %= mod;  // 对答案取模
        }
    }
    
    ans += s.size();  // 最后加上字符串长度
    ans %= mod;  // 对答案再次取模
    cout << ans << endl;  // 输出答案
}

int main(void) {
    solve();  // 调用解决函数

    return 0;
}

python

def solve():
    s = input()  # 输入字符串 s
    mod = 998244353  # 定义常数 mod
    ans = 0  # 初始化答案 ans

    # 遍历字母表的每个字母
    for i in range(26):
        pre = 0  # 初始化前缀和 pre
        for j in range(1, len(s)):
            pre = (pre * 2) % mod  # 左移一位，相当于乘以 2，然后对前缀和取模
            if ord(s[j - 1]) - ord('a') == i:
                pre += 1  # 如果前一个字符是当前字母，增加前缀和
            if ord(s[j]) - ord('a') == i:
                ans += pre  # 如果当前字符是当前字母，增加答案 ans
            ans %= mod  # 对答案取模

    ans += len(s)  # 最后加上字符串长度
    ans %= mod  # 对答案再次取模
    print(ans)  # 输出答案

if __name__ == "__main__":
    solve()  # 调用解决函数

Java

import java.util.Scanner;

public class Main {
    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();  // 输入字符串 s
        final int mod = 998244353;  // 定义常数 mod
        long ans = 0;  // 初始化答案 ans

        // 遍历字母表的每个字母
        for (int i = 0; i < 26; i++) {
            long pre = 0;  // 初始化前缀和 pre
            for (int j = 1; j < s.length(); j++) {
                pre *= 2;  // 左移一位，相当于乘以 2
                pre %= mod;  // 对前缀和取模
                if (s.charAt(j - 1) - 'a' == i) pre++;  // 如果前一个字符是当前字母，增加前缀和
                if (s.charAt(j) - 'a' == i) ans += pre;  // 如果当前字符是当前字母，增加答案 ans
                ans %= mod;  // 对答案取模
            }
        }

        ans += s.length();  // 最后加上字符串长度
        ans %= mod;  // 对答案再次取模
        System.out.println(ans);  // 输出答案
    }

    public static void main(String[] args) {
        solve();  // 调用解决函数
    }
}

题目描述

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

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

注：子序列可以不连续，但是需要保证在原串中的顺序。

输入描述

一个字符串，仅由小写字母组成，字符串长度不大于$100000。$

输出描述

满足条件的子序列的数量。由于答案过大，请将答案对于$998244353$取模

样例

输入

abca

输出

8

说明

长度为$1$的子序列均符合要求，共$4$个。

长度为$2$的子序列，有"ab","ac","aa","bc","ba","ca"，符合条件的有"aa"。

长度为$3$的子序列，有"abc","aba","aca","bca"，符合条件的有"aba","aca"。

长度为$4$的子序列，有"abca"，符合条件的有"abca"。

答案为$4 + 1+2+1=8$