神奇的数论 + 模型转化。

Table of Contents

  1. Description
  2. Solution

Description

给定$n,a,b,p$，其中$n,a$互质。定义一个长度为$n$的01串$c[0\ldots n-1]$，其中$c[i]=0$当且仅当$(ai+b)\, mod \,n < p$。

给定一个长为$m$的小01串，求出小串在大串中出现了几次。

Solution

这个题好神的说……

首先直接匹配肯定是不行啦, 我们要找一点性质.

注意到$n, a$ 互质, 也就是每一位的值会遍历剩余系且两两不同.

这样我们就不必局限在具体的位置上, 只要找到哪些值是可以作为起点的就好了.

但是求起点还是不好求, 因为会计算出重复的区间, 所以我们求不能作为起点的区间, 取个并, 再容斥一下就是答案.

注意最后$m - 1$个位置的值也不能用.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int Max_n = 3e+6 + 5;

typedef long long Int64;

struct Segment
{
  int l, r;
  Segment(int l_ = 0, int r_ = 0):l(l_),r(r_){}
  bool operator < (const Segment &Rhs) const {
    return (l == Rhs.l) ? (r < Rhs.r) : (l < Rhs.l);
  }
}s[Max_n];
char Mode[Max_n];
int ptr, n, a, b, p, m;


inline void add(int l1, int l2, int r1, int r2) {
  if (l1) s[++ptr] = Segment(0, l1);
  if (l2 < r1) s[++ptr] = Segment(l2, r1);
  if (r2 < n) s[++ptr] = Segment(r2, n);
}

int main() {
  scanf("%d%d%d%d%d", &n, &a, &b, &p, &m);
  scanf("%s", Mode);
  for (int i = 0, t = b; i < m; ++i, t = (t + a) % n) {
    if (Mode[i] == '0') add(0, max(p - t, 0), n - t, min(n - t + p, n));
    else add(max(p - t, 0), n - t, min(n - t + p, n), n);
  }
  for (int i = n - 1, t = n - a; i > n - m; --i, t = (t - a + n) % n) s[++ptr] = Segment(t, t + 1);
  s[++ptr] = Segment(n, n + 1);
  sort(s + 1, s + 1 + ptr);
  int lst = 0, ans = 0;
  for (int i = 1; i <= ptr; ++i) {
    if (s[i].l > lst) ans += s[i].l - lst, lst = s[i].r;
    else lst = max(lst, s[i].r);
  }
  printf("%d\n", ans);
  return 0;
}

虽然过了但还是觉得有点奇怪, 放一个更好懂的思路.

对于$m_i = 0$, 可行区间为 $0 \le f + a \times i < p \,(mod\,n)$, 转化为不可行区间讨论一下.$m_i = 1$就取相反情况. 最后枚举$a \times i + b \,(mod\,n),\,n - m+1 \le i \le n-1$.

这样也很好实现, 而且也是对的.