[TYVJ1319]count

题目大概就是说，让你根据下面规则，生成字符串\(S_n\)，然后求出一个模式串在\(S_n\)中出现次数：

\[ \begin{eqnarray*} S_0 &=& 0\\ S_1 &=& 1\\ S_n &=& S_{n-2} S_{n-1} \end{eqnarray*} \]

这题好像是吴翼出的NOIP模拟题，十分的厉害（真心不是NOIP难度啊）。一眼看到这题和这题的数据范围，我就冒出了矩阵和KMP这两个想法，但是看到模式串长度\(M \leq 10000\)，完全不懂得如何写递推式了……

后来Orz了一下xietutu的题解，发现这题有个非常巧妙的转化。

设\(F_n\)为\(S_n\)中模式串出现的次数，显然有\(F_n=F_{n-2}+F_{n-1}+C_n\)，其中\(C_n\)就是拼接产生的匹配。这个还是很显然的，大家都想得到，但是这个\(C_n\)如何搞到还真是一个问题。

要搞到\(C_n\)还是得利用KMP。我们在对\(S_n\)这个串做KMP的时候，可以发现，如果在\(i\)这个位置匹配是\(S_{n-2} S_{n-1}\)拼接产生的匹配，那么\(i-M+1 \leq len(S_{n-2}) < i\)。这样我们就利用了KMP求出了\(C_n\)。

最神的地方在于：存在一个正整数\(\alpha\)，使得对任意\(2n\geq\alpha\)，都有\(C_{2n} = C_\alpha\)和\(C_{2n+1} = C_{\alpha+1}\)成立。更形象的说，就是当串\(S_n\)的长度达到一定程度的时候，那么拼接产生的匹配的次数将只由\(n\)的奇偶决定，分别为一个定值。这个还是非常好理解的。

那么分奇偶如何能矩阵乱搞呢？注意到

\[ \begin{eqnarray*} F_n &=& F_{n-2} + F_{n-1} + t_1\\ F_{n-1} &=& F_{n-3} + F_{n-2} + t_2 \end{eqnarray*} \]

那么我们两个式子相加一下，就可以得到

\[ F_n = F_{n-3} + 2F_{n-2} + t_1 + t_2 \]

我们分奇偶求出了\(t_1\)和\(t_2\)之后，就可以构造出如下矩阵了：

\[ \begin{bmatrix} F_n\\ F_{n-1}\\ F_{n-2}\\ t_1 + t_2 \end{bmatrix} = \begin{bmatrix} 0 & 2 & 1 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ F_{n-3}\\ t_1 + t_2 \end{bmatrix}\\ = \begin{bmatrix} 0 & 2 & 1 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}^{n-\alpha} \begin{bmatrix} F_{\alpha}\\ F_{\alpha-1}\\ F_{\alpha-2}\\ t_1 + t_2 \end{bmatrix} \]

然后我们就对\(\alpha\)以内的暴力求出来，后面再矩阵快速幂。

代码

count 
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <cstdio>
#include <cstring>
#include <algorithm>

int N, M, P, l[24], p[80000];
long long f[24], t[24];
char a[80000], s[3][80000];
struct Matrix
{
  int m[4][4];
  Matrix(): m() { }
} I;
inline Matrix operator*(const Matrix& a, const Matrix& b)
{
  Matrix c;
  for (int k = 0; k < 4; ++k)
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j)
        c.m[i][j] = (c.m[i][j] + static_cast<long long>(a.m[i][k])*b.m[k][j]) % P;
  return c;
}
inline Matrix power(Matrix base, int k)
{
  Matrix res(I);
  for (; k; k >>= 1)
  {
    if (k & 1) res = res*base;
    base = base*base;
  }
  return res;
}
int kmp(const char *s, const int n, const int last, long long& mid)
{
  int cnt = 0;
  for (int i = 0, j = -1; i < n; ++i)
  {
    while (j > -1 && a[j+1] != s[i]) j = p[j];
    if (a[j+1] == s[i]) ++j;
    if (j == M-1)
    {
      ++cnt;
      if (i >= last && last > i-M) ++mid;
      j = p[j];
    }
  }
  return cnt;
}
int main()
{
  freopen("count.in", "r", stdin);
  freopen("count.out", "w", stdout);

  I.m[0][0] = I.m[1][1] = I.m[2][2] = I.m[3][3] = 1;
  scanf("%d%d%d%s", &N, &M, &P, a);
  p[0] = -1;
  for (int i = 1, j = -1; i < M; ++i)
  {
    while (j > -1 && a[j+1] != a[i]) j = p[j];
    if (a[j+1] == a[i]) ++j;
    p[i] = j;
  }
  s[0][0] = '0', l[0] = 1;
  s[1][0] = '1', l[1] = 1;
  for (int i = 2, now = 2; i < 24; ++i, now = (now+1)%3)
  {
    strcpy(s[now], s[(now+1)%3]);
    strcpy(s[now]+l[i-2], s[(now+2)%3]);
    f[i] = kmp(s[now], l[i] = l[i-1]+l[i-2], l[i-2], t[i]);
  }
  if (N < 24)
  {
    printf("%d", static_cast<int>(f[N] % P));
    fclose(stdin);fclose(stdout);
    return 0;
  }
  Matrix mat;
  mat.m[0][0] = 0, mat.m[0][1] = 2, mat.m[0][2] = 1, mat.m[0][3] = 1;
  mat.m[1][0] = 1, mat.m[1][1] = 0, mat.m[1][2] = 0, mat.m[1][3] = 0;
  mat.m[2][0] = 0, mat.m[2][1] = 1, mat.m[2][2] = 0, mat.m[2][3] = 0;
  mat.m[3][0] = 0, mat.m[3][1] = 0, mat.m[3][2] = 0, mat.m[3][3] = 1;
  const Matrix res = power(mat, N-23);
  printf("%d", static_cast<int>((res.m[0][0]*f[23]+res.m[0][1]*f[22]+res.m[0][2]*f[21]+res.m[0][3]*(t[23]+t[22]))%P));

  fclose(stdin);fclose(stdout);
}

Comments