长度为5的回文子序列个数

2022.11.28 2022.11.28 XCPC 444 1 分钟

例题链接

LeetCode 2484. Count Palindromic Subsequences

思路

注意：以下解法允许子序列重复。

首先逆序遍历字符串，统计每个数字出现的次数 $suf[a]$ 和两个数字组合出现的次数 $suf2[a][b]$ ，具体做法为：令当前遍历到的数字为 $a$，则对所有的 $suf2[a][0\cdots9]$ 都需要加上 $suf[0\cdots9]$ ，然后再令 $suf[a]$ 加 $1$ 。

然后顺序遍历字符串枚举回文子序列的中心字符，同样统计每个数字出现的次数 $pre[a]$ 和两个数字组合出现的次数 $pre2[a][b]$ ，对于特定的中心字符 $s[i]$ ，根据乘法原理，枚举不同的数字组合 $a$ 和 $b$ ，答案加上 $s[0\cdots i-1]$ 中的 $pre2[a][b]$ 和 $s[i+1\cdots n-1]$ 中的 $suf2[a][b]$ 的乘积。因为当前需要字符 $s[i]$ 作为中心字符，令对应的数字为 $cur$ ，要在乘法之前将 $suf2[cur][0\cdots9]$ 减去 $suf[0\cdots9]$ 。$pre[a]$ 和 $pre2[a][b]$ 可以在乘法完成后顺便更新。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    const long long MOD = 1e9 + 7;
public:
    int countPalindromes(string s) {
        int n = s.length();
        vector<int> suf(10, 0), pre(10, 0);
        vector<vector<int>> suf2(10, vector<int>(10, 0)), pre2(10, vector<int>(10, 0));

        for (int i = n - 1; i >= 0; i--) {
            int cur = s[i] - '0';
            for (int j = 0; j < 10; j++)
                suf2[cur][j] += suf[j];
            suf[cur]++;
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) {
            int cur = s[i] - '0';
            suf[cur]--;
            for (int j = 0; j < 10; j++)
                suf2[cur][j] -= suf[j];
            for (int j = 0; j < 10; j++)
                for (int k = 0; k < 10; k++)
                    ans = (ans + 1LL * pre2[j][k] * suf2[j][k] % MOD) % MOD;
            for (int j = 0; j < 10; j++)
                pre2[cur][j] += pre[j];
            pre[cur]++;
        }

        return ans;
    }
};

Palindrome