问题分析

给定生成公式：

• $c_i = 0$ 当且仅当 $(a \cdot i + b) \bmod n < p$
• 模式串 $w$ 长度为 $m$

需要在长度为 $n$ 的序列 $c_0, c_1, \ldots, c_{n-1}$ 中统计模式串 $w$ 的出现次数。

关键约束：

• $n \leq 10^9$，不能直接生成序列
• $m \leq 10^6$，模式串较长
• $a$ 与 $n$ 互质，保证 $(a \cdot i + b) \bmod n$ 遍历所有余数

核心思想：数学转化 + 区间统计

1. 模式匹配条件

模式串 $w$ 在位置 $i$ 匹配，需要满足： 对于每个 $j = 0, 1, \ldots, m-1$： [ c_{i+j} = w_j ] 即： [ [(a(i+j) + b) \bmod n < p] \text{ 当且仅当 } w_j = 0 ]

2. 转化为模不等式

设 $x = (a \cdot i + b) \bmod n$

对于位置 $j$： [ c_{i+j} = 0 \iff (a(i+j) + b) \bmod n < p ] [ \iff (x + a \cdot j) \bmod n < p ]

因此，对于固定的 $x$，模式串匹配的条件是： 对于每个 $j$：

• 如果 $w_j = 0$，则 $(x + a \cdot j) \bmod n < p$
• 如果 $w_j = 1$，则 $(x + a \cdot j) \bmod n \geq p$

算法详解

数据结构

map<int, int> mp;                // 差分数组
vector<pair<int, int>> vec;      // 有效区间
int n, a, b, p, m;
string str;

算法步骤

步骤1：对每个模式字符建立约束

for (int i = 1; i <= m; i++) {
    int l, r;
    int x = (str[i - 1] - '0');
    
    if (x == 1) {  // w_j = 1，要求 (x + a*j) mod n ≥ p
        l = (p - 1LL * (i - 1) * a % n + n) % n;
        r = (n - 1 - 1LL * (i - 1) * a % n + n) % n;
    } else {       // w_j = 0，要求 (x + a*j) mod n < p
        l = (-1LL * (i - 1) * a % n + n) % n;
        r = (p - 1 - 1LL * (i - 1) * a % n + n) % n;
    }
    
    if (l <= r) {
        mp[l]++;      // 区间[l, r]加1
        mp[r + 1]--;  // 差分标记
    } else {
        // 环形区间：[l, n-1] ∪ [0, r]
        mp[l]++; mp[n]--;
        mp[0]++; mp[r + 1]--;
    }
}

推导过程： 设 $d_j = a \cdot j \bmod n$，则 $d_j$ 是已知常数。

• 如果 $w_j = 0$：要求 $(x + d_j) \bmod n < p$

  • 即 $x \in [-d_j, p-1-d_j] \pmod n$
  • $l = (-d_j) \bmod n$，$r = (p-1-d_j) \bmod n$

• 如果 $w_j = 1$：要求 $(x + d_j) \bmod n \geq p$

  • 即 $x \in [p-d_j, n-1-d_j] \pmod n$
  • $l = (p-d_j) \bmod n$，$r = (n-1-d_j) \bmod n$

步骤2：计算满足所有约束的x区间

int cur = 0, ans = 0;
for (auto iter = mp.begin(); iter != mp.end(); iter++) {
    auto pr = *iter;
    
    if (pr.first == n) break;  // 忽略n处的差分
    
    cur += pr.second;  // 当前覆盖次数
    auto nxt = iter; nxt++;
    
    if (cur == m) {  // 被所有m个区间覆盖
        vec.push_back(make_pair(iter->first, nxt->first - 1));
        ans += nxt->first - iter->first;  // 区间长度
    }
}

解释：

• 使用差分数组统计每个x值被多少个约束区间覆盖
• 如果某个x被所有m个区间覆盖（cur == m），则满足所有模式字符条件
• vec 存储所有满足条件的连续区间

步骤3：排除非法起始位置

for (int i = n - m + 1; i < n; i++) {
    int x = (1LL * a * i + b) % n;
    auto iter = upper_bound(vec.begin(), vec.end(), make_pair(x, INF));
    
    if (iter == vec.begin()) continue;
    
    iter--;
    
    if (iter->first <= x && iter->second >= x) {
        --ans;  // 这个起始位置超出范围
    }
}

为什么需要这一步？

• 起始位置 $i$ 必须满足 $0 \leq i \leq n-m$
• 但我们的约束是基于 $x = (a \cdot i + b) \bmod n$ 的
• 当 $i \geq n-m+1$ 时，匹配会"绕回"到序列开头，不符合正常的字符串匹配定义
• 需要排除这些非法的起始位置

正确性证明

定理1：约束等价性

模式串在位置 $i$ 匹配 ⇔ $x = (a \cdot i + b) \bmod n$ 满足所有约束

证明：

• 对于每个 $j$，$c_{i+j} = 0 ⇔ (x + a \cdot j) \bmod n < p$
• 这与 $w_j$ 的值比较，得到对应的约束区间
• 所有 $j$ 的约束交集即为合法 $x$ 的集合

定理2：计数正确性

• 每个合法的 $x$ 对应一个起始位置 $i$
• 由于 $a$ 与 $n$ 互质，$i = a^{-1} \cdot (x - b) \bmod n$ 唯一确定
• 排除 $i \geq n-m+1$ 的情况得到最终答案

复杂度分析

时间复杂度

1. 建立约束：$O(m \log m)$

   • 每个字符生成一个区间
   • 使用 map 插入，$O(\log m)$ 每次

2. 计算区间：$O(m \log m)$

   • 遍历差分数组

3. 排除非法位置：$O(m \log m)$

   • 最多检查 $m-1$ 个位置
   • 每个位置二分查找 $O(\log m)$

总复杂度：$O(m \log m)$

空间复杂度

• $O(m)$ 存储差分数组和区间
• 满足 $m \leq 10^6$ 的限制

示例分析

样例

n=9, a=5, b=6, p=4, m=3
w = "101"

执行过程：

1. 为每个字符建立约束：

   • j=0 (w=1): l=(4-0)%9=4, r=(8-0)%9=8
   • j=1 (w=0): l=(-5)%9=4, r=(3-5)%9=7
   • j=2 (w=1): l=(4-10)%9=3, r=(8-10)%9=7

2. 计算交集：

   • 区间[3,7]被覆盖3次
   • 长度5，初始ans=5

3. 排除非法起始位置：

   • i=7: x=(5*7+6)%9=5，在区间[3,7]内，ans=4
   • i=8: x=(5*8+6)%9=1，不在区间内
   • 最终ans=3

算法优势

1. 高效：$O(m \log m)$ 处理百万级模式串
2. 数学优美：利用模运算性质转化为区间问题
3. 空间优化：不需要存储整个长序列
4. 正确性高：基于严格的数学推导

边界情况处理

环形区间

当 $l > r$ 时，表示区间跨越模 $n$ 的边界： [ [l, n-1] \cup [0, r] ] 使用差分数组的两个部分处理。

大数运算

使用 1LL 确保乘法不溢出：

1LL * (i - 1) * a % n

总结

本题的核心技巧：

1. 变量代换：令 $x = (a \cdot i + b) \bmod n$，简化问题
2. 约束转化：将模式匹配条件转化为模不等式
3. 区间求交：使用差分数组高效计算满足所有约束的 $x$ 值
4. 边界排除：二分查找排除非法起始位置

通过巧妙的数学转化，将字符串匹配问题转化为区间求交问题，实现了 $O(m \log m)$ 的高效算法，可以处理 $n=10^9$ 的超大序列。