首先明确题目核心要求构造长度为n的字符串仅由A、B、C、D组成且A出现偶数次包括 0 次、C出现偶数次包括 0 次B、D无限制。第一步定义 4 个核心状态关键我们不直接求最终结果先定义 4 个互斥且覆盖所有情况的状态方便递推设字符串长度为n时a[n]A偶次、C偶次这就是我们最终要求的结果b[n]A偶次、C奇次c[n]A奇次、C偶次d[n]A奇次、C奇次所有长度为n的字符串总数 a[n] b[n] c[n] d[n] 4^n每个位置有 4 种选择没错。第二步分析状态转移从 n-1 推导 n长度为n的字符串是在长度为n-1的字符串末尾 ** 添加一个字符A/B/C/D** 得到的我们逐个分析每个状态如何从前面的状态转移而来。先明确核心逻辑添加字符会改变对应字母的奇偶性偶→奇、奇→偶不相关字母的奇偶性不变。1. 推导a[n]目标状态A 偶、C 偶要得到长度为n的「A 偶、C 偶」有 4 种添加字符的可能对应从n-1的 4 个状态转移原状态a[n-1]A 偶、C 偶添加B 或 D不改变 A、C 的奇偶性共 2 种选择原状态b[n-1]A 偶、C 奇添加C把 C 的奇次变为偶次A 保持偶次共 1 种选择原状态c[n-1]A 奇、C 偶添加A把 A 的奇次变为偶次C 保持偶次共 1 种选择原状态d[n-1]A 奇、C 奇添加AC不行添加一个字符无法同时改变两个字母的奇偶性共 0 种选择因此a[n] 2*a[n-1] b[n-1] c[n-1]2. 推导b[n]A 偶、C 奇同理要得到「A 偶、C 奇」原状态a[n-1]A 偶、C 偶添加C1 种选择原状态b[n-1]A 偶、C 奇添加B 或 D2 种选择原状态c[n-1]A 奇、C 偶添加AC不行0 种选择原状态d[n-1]A 奇、C 奇添加A1 种选择因此b[n] a[n-1] 2*b[n-1] d[n-1]3. 推导c[n]A 奇、C 偶和b[n]是对称的A 和 C 地位等价原状态a[n-1]添加A1 种选择原状态b[n-1]添加AC不行0 种选择原状态c[n-1]添加B 或 D2 种选择原状态d[n-1]添加C1 种选择因此c[n] a[n-1] 2*c[n-1] d[n-1]4. 推导d[n]A 奇、C 奇要得到「A 奇、C 奇」原状态a[n-1]添加AC不行0 种选择原状态b[n-1]添加A1 种选择原状态c[n-1]添加C1 种选择原状态d[n-1]添加B 或 D2 种选择因此d[n] b[n-1] c[n-1] 2*d[n-1]第三步简化递推公式消去无关状态我们的目标是a[n]现在有 4 个方程需要消去b[n]、c[n]、d[n]简化成只关于a[n]的递推式。步骤 1利用对称性简化因为 A 和 C 地位完全相同所以b[n] c[n]偶 A 奇 C 和 奇 A 偶 C 的数量相等这个结论能大幅简化计算。步骤 2求a[n] d[n]和b[n] c[n]先计算两个组合状态方便消元a[n] d[n] [2a(n-1)b(n-1)c(n-1)] [b(n-1)c(n-1)2d(n-1)]整理得a[n] d[n] 2[a(n-1)b(n-1)c(n-1)d(n-1)] 2*4^{n-1} 2^n因为abcd4^nb[n] c[n] [a(n-1)2b(n-1)d(n-1)] [a(n-1)2c(n-1)d(n-1)]代入b(n-1)c(n-1)整理得b[n] c[n] 2[a(n-1)d(n-1)] 4b(n-1)又因为a(n-1)d(n-1)2^{n-1}且b[n]c[n]2b[n]最终简化得b[n] c[n] 2*4^{n-1} 2^n和a[n]d[n]相等这是对称结果步骤 3推导a[n]的单变量递推式我们已经知道a[n] 2a(n-1) b(n-1) c(n-1)而b(n-1) c(n-1) 2^{n-1}由步骤 2 的结论同时a(n-1) d(n-1) 2^{n-1}可以不用管再结合初始条件先求n1时的各状态值长度为 1 的字符串a[1]A 偶、C 偶只能是 B、D → 共 2 个 →a[1]2b[1]A 偶、C 奇只能是 C → 共 1 个 →b[1]1c[1]A 奇、C 偶只能是 A → 共 1 个 →c[1]1d[1]A 奇、C 奇不存在 →d[1]0现在代入递推先验证前几项再推导通用公式a[1] 2a[2] 2a[1] b[1]c[1] 2*2 2 6a[3] 2a[2] b[2]c[2] 2*6 4 16a[4] 2a[3] b[3]c[3] 2*16 8 40不对这里换一种更简单的方式直接推导通项公式步骤 4推导最终通项公式从前面的组合状态我们知道a[n] d[n] 2^nb[n] c[n] 2^n同时原递推式a[n] 2a(n-1) b(n-1) c(n-1)代入b(n-1)c(n-1)2^{n-1}得到a[n] 2a(n-1) 2^{n-1}这是一个线性递推方程我们可以通过变形求通项两边同时除以2^n得到a[n]/2^n a(n-1)/2^{n-1} 1/2设g[n] a[n]/2^n则g[n] - g[n-1] 1/2这是一个等差数列公差为 1/2初始条件g[1] a[1]/2^1 2/2 1等差数列通项g[n] g[1] (n-1)*(1/2) 1 (n-1)/2 (n1)/2还原a[n]a[n] g[n] * 2^n (n1)/2 * 2^n (n1)*2^{n-1}不对这是因为我们前面的组合状态简化有疏漏换一种更直观的通项推导从题目样例反推 验证第四步更简单的通项公式实用化从题目样例和递推规律我们可以直接得到最终的简洁通项公式无需复杂消元考试 / 刷题时可直接使用最终结果a[n] (4^n 2^{n1}) / 4化简后为4^{n-1} 2^{n-1}验证样例n1(4^1 2^2)/4 (44)/4 2✅n2(16 8)/4 6✅n4(256 32)/4 288/4 72✅和题目样例一致这个公式的本质是利用容斥原理直接计算避免复杂的状态转移刷题时记住即可。总结两个基础结论恒成立后续全程复用第二步推导状态转移方程从 n-1 推 n核心步骤长度为n的字符串可由长度为 n-1 的字符串末尾添加 1 个字符A/B/C/D得到。核心规律添加某字符仅改变该字符的奇偶性偶→奇、奇→偶不影响其他字符的奇偶性。逐一推导 4 个状态的转移方程明确添加的字符类型 可选数量。转移 1推导目标状态a[n]A 偶、C 偶要得到n时的 A 偶、C 偶需从n-1的状态出发添加字符后最终 A、C 均为偶次结合对称性b[n-1]c[n-1]得转移方程a[n]2a[n−1]b[n−1]c[n−1]2a[n−1]2b[n−1]转移 2推导b[n]A 偶、C 奇要得到n时的 A 偶、C 奇同理分析添加字符的选择得转移方程b[n]a[n−1]2b[n−1]d[n−1]转移 3推导d[n]A 奇、C 奇要得到n时的 A 奇、C 奇同理分析添加字符的选择结合对称性b[n-1]c[n-1]得转移方程d[n]b[n−1]c[n−1]2d[n−1]2b[n−1]2d[n−1]第三步核心化简消去冗余状态得到a[n]单变量递推式目标消去b[n]、d[n]仅保留目标状态a[n]推导可直接计算的单变量递推公式。化简 1推导a[n]d[n]与b[n]的关系关键关系式将目标状态a[n]和状态d[n]的转移方程相加展开并整理第 1 式 ×2n−2第 2 式 ×2n−3…第 n-1 式 ×20得到两个基础结论恒成立后续全程复用第二步推导状态转移方程从 n-1 推 n核心步骤长度为n的字符串可由长度为 n-1 的字符串末尾添加 1 个字符A/B/C/D得到。核心规律添加某字符仅改变该字符的奇偶性偶→奇、奇→偶不影响其他字符的奇偶性。逐一推导 4 个状态的转移方程明确添加的字符类型 可选数量。转移 1推导目标状态a[n]A 偶、C 偶要得到n时的 A 偶、C 偶需从n-1的状态出发添加字符后最终 A、C 均为偶次结合对称性b[n-1]c[n-1]得转移方程a[n]2a[n−1]b[n−1]c[n−1]2a[n−1]2b[n−1]转移 2推导b[n]A 偶、C 奇要得到n时的 A 偶、C 奇同理分析添加字符的选择得转移方程b[n]a[n−1]2b[n−1]d[n−1]转移 3推导d[n]A 奇、C 奇要得到n时的 A 奇、C 奇同理分析添加字符的选择结合对称性b[n-1]c[n-1]得转移方程d[n]b[n−1]c[n−1]2d[n−1]2b[n−1]2d[n−1]第三步核心化简消去冗余状态得到a[n]单变量递推式目标消去b[n]、d[n]仅保留目标状态a[n]推导可直接计算的单变量递推公式。化简 1推导a[n]d[n]与b[n]的关系关键关系式将目标状态a[n]和状态d[n]的转移方程相加展开并整理a[n]d[n]​[2a[n−1]2b[n−1]][2b[n−1]2d[n−1]]2a[n−1]4b[n−1]2d[n−1]2[a[n−1]2b[n−1]d[n−1]]​此时观察b[n]的转移方程我们能发现括号内的部分正好等于b[n]即b[n]a[n−1]2b[n−1]d[n−1]。将这个关系代入上式可得到一个关键的简化关系式a[n]d[n]2b[n]同时这个关系式对n-1也成立只需将所有n替换为n-1即a[n−1]d[n−1]2b[n−1]化简 2结合总个数结论消去d[n]由总个数结论a[n]b[n]c[n]d[n]4n结合两个已知条件右侧​2n−2⋅222n−3⋅24...20⋅22(n−1)2n2n1...22n−2​该等比数列首项2n公比 2项数 n-1用等比数列和公式Sa1​⋅q−1qm−1​计算右侧2n⋅2−12n−1−1​22n−1−2n步骤 4代入初始条件得到通项将初始条件a[1]2代入整理得a[n]−2n−1⋅2a[n]−2na[n]​22n−1−2n22n−1−2n22n−1−2n−1​刷题通用化简版通项直接套代码将通项公式转化为底数 4 和 2 的形式更适合快速幂计算a[n]​24n​−22n​24n−2n​4n−12n−1​✅最终刷题通用公式a[n]4n−12n−1代码中用快速幂分别计算4n−1%100和2n−1%100相加后再模 100 即可。第五步验证正确性代入小 n 值手动核对最终核心结论一目了然直接对应代码总结将这两个条件代入总个数公式展开整理a[n]2b[n]d[n]a[n](a[n]d[n])d[n]2a[n]2d[n]a[n]d[n]​4n4n4n2⋅4n−1​同理这个结论对n-1也成立即a[n−1]d[n−1]2⋅4n−2化简 3得到a[n]的单变量递推式从化简 1 的结论中我们知道2b[n-1] a[n-1] d[n-1]再结合化简 2 中n-1的结论a[n−1]d[n−1]2⋅4n−2将两者联立替换可得2b[n−1]2⋅4n−2⟹b[n−1]4n−2将这个结果代入目标状态a[n]的转移方程最终得到无冗余的单变量递推式a[n]​2a[n−1]2⋅4n−22a[n−1]4n−1​初始条件n1 时满足条件的字符串为 B、D共 2 个 → a[1]2。第四步推导a[n]的通项公式直接计算无需递推从单变量递推式a[n]2a[n−1]4n−1a[1]2出发用累加法推导通项全程无跳步。步骤 1展开递推式k≥2a[2]−2a[1]a[3]−2a[2]a[4]−2a[3]⋮a[n]−2a[n−1]​4142434n−1​步骤 2乘系数消去中间项第 1 式 ×2n−2第 2 式 ×2n−3…第 n-1 式 ×20得到2n−2a[2]−2n−1a[1]2n−3a[3]−2n−2a[2]⋮20a[n]−21a[n−1]​2n−2⋅412n−3⋅4220⋅4n−1​将所有式子相加中间项全部抵消仅剩首项和末项a[n]−2n−1a[1]2n−2⋅412n−3⋅42...20⋅4n−1步骤 3计算右侧等比数列和将右侧统一底数为 24k22k整理为等比数列核心是定义 4 个互斥状态通过「添加字符改变奇偶性」推导状态转移方程。利用 A 和 C 的对称性可以大幅简化递推过程消去无关状态。最终实用通项公式为a[n] 4^{n-1} 2^{n-1}直接代入计算即可无需复杂递推。因为n可能很大需要用快速幂计算幂次并取模 100得到最后两位结果。#include cstdio typedef long long LL; // 关键修改指数 b 改为 LL 类型适配超大 N避免溢出 // a 仍为 int2、4 都很小无需 LLp 仍为 int100 很小 LL qmi(int a, LL b, int p) { LL res 1 % p; // res 为 LL保证乘法不溢出 a % p; // 先对底数取模a 始终在 0~99 之间无溢出 // 循环条件b 是 LL即使超大也能正确判断不会死循环 while (b) { if (b 1) { // 位运算对 LL 同样有效判断奇偶无问题 res res * a % p; // 结果始终 %100res 不会超过 99 } // a*a 最大 99*999801转 LL 更稳妥无溢出 a a * (LL)a % p; b 1; // LL 类型的右移不会溢出效率依然很高 } return res; } int main() { int T; // scanf 输入效率最优避免 IO 超时 while (scanf(%d, T) 1 T ! 0) { for (int case_num 1; case_num T; case_num) { LL N; // 用 LL 存储 N适配超大数值 scanf(%lld, N); // 输入 LL 用 %lld LL ans 0; if (N ! 0) { // 关键N-1 是 LL 类型传入 qmi 的第二个参数LL b无溢出 LL term1 qmi(4, N - 1, 100); LL term2 qmi(2, N - 1, 100); ans (term1 term2) % 100; // 最终结果仍 %100保证范围 0~99 } // 输出 ans 转为 int用 %d 更兼容无格式问题 printf(Case %d: %d\n, case_num, (int)ans); } printf(\n); // 每组输出后空行符合题目格式 } return 0; }