题目分析
本题要求统计满足特定复杂度策略的密码数量，密码长度范围 $[L, R]$ 可达 $10^9$，需要高效算法。

---

算法思路

核心思想：动态规划 + 矩阵快速幂 + Berlekamp-Massey 算法

问题分解：

1. 生成不含连续 $A$ 个重复字符、不含连续 $B$ 个上升/下降序列的密码数量
2. 排除不含数字或不含字母的情况
3. 处理长度范围 $[L, R]$ 的求和

---

算法流程详解

1. 基础计数生成

gen(f, 10);    // 仅数字的合法密码数
gen(g, 26);    // 仅字母的合法密码数
mix(g, g, g);  // 大小写字母混合
mix(f, g, h);  // 数字+字母混合

gen(arr, s) 函数使用动态规划计算长度为 $n$、字符集大小为 $s$ 的合法密码数：

• 状态 dp[i][j] 表示以字符 $i$ 结尾，且具有特定模式长度 $j$ 的密码数量
• 模式分类：
  • $j < A$：当前重复字符数
  • $A \leq j < A+B$：当前上升序列长度
  • $A+B \leq j$：当前下降序列长度

2. 容斥原理

for (int n = 0; n < THRES; ++n) {
    sub(h[n], f[n]);  // 减去全数字
    sub(h[n], g[n]);  // 减去全字母
}

最终 h[n] 表示长度为 $n$ 且包含至少一个数字和一个字母的合法密码数。

3. 前缀和与线性递推

for (int n = 1; n < THRES; ++n)
    add(h[n], h[n - 1]);  // 计算前缀和

h[n] 现在表示长度 $\leq n$ 的合法密码总数。

4. Berlekamp-Massey 算法

d = BM::euclid(THRES / 2, h);

找到序列 h 的最小线性递推式，将问题转化为矩阵快速幂。

5. 矩阵快速幂求解

vector<int> X = pw(ini, R), Y = pw(ini, L - 1);
int ans = 0;
for (int i = 0; i < d; ++i) {
    sub(X[i], Y[i]);
    fam(ans, X[i], h[i]);
}

计算 $H(R) - H(L-1)$，其中 $H(n)$ 是长度 $\leq n$ 的密码总数。

---

关键技术与优化

1. 状态压缩DP

• 将重复、上升、下降模式统一编码
• 使用滚动数组优化空间

2. 线性递推发现

• 利用 BM 算法自动发现递推关系
• 避免手动推导复杂公式

3. 多项式快速幂

vector<int> pw(vector<int> v, int n) {
    if (n == 0) return id;
    auto ret = pw(mul(v, v), n / 2);
    if (n & 1) ret = mul(ret, v);
    return ret;
}

在模 $x^d$ 下进行多项式快速幂，高效计算递推项。

4. 模运算优化

使用 Barrett 约减等技巧加速模 $10^9+7$ 运算。

---

复杂度分析

• 预处理：$O(THRES^2)$，$THRES = 2000$
• BM算法：$O(THRES^2)$
• 快速幂：$O(d^2 \log R)$，$d \leq 500$
• 总复杂度：$O(d^2 \log R)$，对 $R \leq 10^9$ 完全可行

---

样例验证

样例1：$L=2, R=2, A=2, B=2$

• 字符集：10数字 + 52字母 = 62字符
• 排除全数字(100种)和全字母(2704种)
• 合法密码：$62^2 - 100 - 2704 = 1040$

样例2、3

通过递推和快速幂计算大规模结果，验证算法正确性。

---

算法优势

1. 自动化：BM算法自动发现递推关系，避免复杂推导
2. 高效性：矩阵快速幂处理 $10^9$ 规模
3. 通用性：适用于各种 $A, B$ 参数
4. 数值稳定：全程模运算保证正确性

该算法通过组合数学、自动递推发现和多项式技术，高效解决了超大规模密码计数问题。