本文涉及知识点
组合数学 逆向思考
LeetCode2930. 重新排列后包含指定子字符串的字符串数目
给你一个整数 n 。
如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 “leet” ，那么我们称字符串 s 是一个 好 字符串。
比方说：
字符串 “lteer” 是好字符串，因为重新排列后可以得到 “leetr” 。
“letl” 不是好字符串，因为无法重新排列并得到子字符串 “leet” 。
请你返回长度为 n 的好字符串 总 数目。
由于答案可能很大，将答案对 109 + 7 取余 后返回。
子字符串 是一个字符串中一段连续的字符序列。
示例 1：
输入：n = 4
输出：12
解释：总共有 12 个字符串重新排列后包含子字符串 “leet” ：“eelt” ，“eetl” ，“elet” ，“elte” ，“etel” ，“etle” ，“leet” ，“lete” ，“ltee” ，“teel” ，“tele” 和 “tlee” 。
示例 2：
输入：n = 10
输出：83943898
解释：长度为 10 的字符串重新排列后包含子字符串 “leet” 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。
提示：
1 <= n <= 105
逆向思考
所有可能26n 减去非法情况
以下条件之一非法：
a，没有选择l，每个字符有25种选择，共25n。
b，没有选择t， 每个字符有25种选择，共25n。
c，没有选择e或只选择了一个e，共25n+ n× \times× 25n-1
同时满足两个条件：
a，l和t同时非法： 2 4 n 24^n24n
b,l和e非法。2 4 n + n × 2 4 n − 1 24^n + n \times 24^{n-1}24n+n×24n−1
c，t和e非法。同上。
同时满足三个条件：
23n + n × \times× 23 n-1
代码
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; } 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 stringCount(int n) { if (n < 4) { return 0; } C1097Int<> cnt1[4]; cnt1[1] = C1097Int<>(25).pow(n) * 3 + C1097Int<>(25).pow(n - 1) * n; cnt1[2] = C1097Int<>(24).pow(n) + (C1097Int<>(24).pow(n) + C1097Int<>(24).pow(n - 1) * n) * 2; cnt1[3] = C1097Int<>(23).pow(n) + C1097Int<>(23).pow(n - 1) * n; C1097Int<> biRet = C1097Int<>(26).pow(n) - cnt1[1] + cnt1[2] -cnt1[3]; return biRet.ToInt(); } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
