本文涉及知识点

C++前后缀分解

本题同解

【动态规划】2484. 统计回文子序列数目|2223

LeetCode2484. 统计回文子序列数目

给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。
提示：
如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。
子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。
示例 1：
输入：s = “103301”
输出：2
解释：
总共有 6 长度为 5 的子序列：“10330” ，“10331” ，“10301” ，“10301” ，“13301” ，“03301” 。
它们中有两个（都是 “10301”）是回文的。
示例 2：
输入：s = “0000000”
输出：21
解释：所有 21 个长度为 5 的子序列都是 “00000” ，都是回文的。
示例 3：
输入：s = “9999900000”
输出：2
解释：仅有的两个回文子序列是 “99999” 和 “00000” 。
提示：
1 <= s.length <= 10⁴
s 只包含数字字符。

前后缀分解

n = s.length
分别枚举第一个字符和第二个字符，不失一般性以01为例。
preSum[i]记录nums长度为i的前缀中子序列01的数量。
suff[i]记录nums长度为i的后缀中子序列10的数量，即nums转置数组中01的数量。
以nums[i]为中间字符的数量为：preSum[i] * suff[n-i-1]。
preSum[i] = preSum[i-1]+ 以nums[i-1]结尾的01数量cnt1
{ c n t 1 = n u m s [ 0... i − 2 ] 中 0 的数量 n u m s [ i − 1 ] 是 1 c n t 1 = 0 o t h e r \begin{cases} cnt1 = nums[0...i-2]中0的数量 && nums[i-1]是1 \\ cnt1= 0 && other \end{cases} {cnt1=nums[0...i−2]中0的数量cnt1=0​​nums[i−1]是1other​

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this /= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};

class Solution {
		public:
			int countPalindromes(string s) {
				m_iN = s.length();
				C1097Int<> ret;
				for(int ch1 = '0'; ch1 <= '9';ch1++)
					for (int ch2 = '0'; ch2 <= '9'; ch2++)
					{
						ret += Do(s, ch1, ch2);
					}
				return ret.ToInt();
			}
			C1097Int<> Do(const string& s, const char ch1, const char ch2) {
				auto PreSum = [&](const string& str) {
					int cnt0 = 0;
					vector<C1097Int<>> ret(1);
					for (int i = 0; i < m_iN; i++) {
						const int cnt1 = (ch2 == str[i]) ? cnt0 : 0;
						ret.emplace_back(ret.back()+cnt1);
						cnt0 += (ch1 == str[i]);
					}
					return ret;
				};
				auto pre = PreSum(s);
				auto suff = PreSum(string(s.rbegin(), s.rend()));
				C1097Int<> ret;
				for (int i = 0; i < s.length(); i++) {
					ret += pre[i] * suff[m_iN - 1 - i];
				}
				return ret;
			}
			int m_iN;
		};

单元测试

	string s;
		TEST_METHOD(TestMethod1)
		{
			s = "00000";
			auto res = Solution().countPalindromes(s);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod11)
		{
			s = "103301";
			auto res = Solution().countPalindromes(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "0000000";
			auto res = Solution().countPalindromes(s);
			AssertEx(21, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "9999900000";
			auto res = Solution().countPalindromes(s);
			AssertEx(2, res);
		}