【做题】CF177G2. Fibonacci Strings—

题意：定义斐波那契字符串为:

$f_1 = $ "a"

$f_2 =$ "b"

$f_n = f_{n-1} + f_{n-2}, \, n > 2$

例如，$f_3 = $ “ba”。

有$m$次询问，第$i$次给出一个字符串$s_i$，问$s_i$在$f_n$中的出现次数。

$m \leq 10^4, \, n \leq 10^{18}, \, \sum|s_i| \leq 10^5$

主要问题在与$f_p$与$f_{p-1}$拼接时，$f_p$的某个后缀与$f_{p-1}$的某个前缀可能恰好拼成$s_i$，即产生额外的出现次数。当$|f_p|$与$|f_{p-1}|$都大于等于$|s_i|$时，这个数值就等于$f_{n}$长度为$|s_i|-1$的后缀与$f_{p-1}$长度为$|s_i|-1$的前缀组成的字符串中$s_i$的出现次数。

我们设$f_{p-1}$长度为$|s_i|-1$的前缀为$a$，长度为$|s_i|-1$的后缀为$b$，$f_{p}$长度为$|s_i|-1$的前缀为$a$，长度为$|s_i|-1$的后缀为$c$。我们观察发现：

| | 长度为$|s_i|-1$的前缀 | 长度为$|s_i|-1$的后缀 | 产生额外贡献的字符串 |

| ------------ | --------------------- | --------------------- | -------------------- |

| $f_{p-1}$ | $a$ | $b$ | |

| $f_p$ | $a$ | $c$ | $ca$ |

| $f_{p+1}$ | $a$ | $b$ | $ba$ |

| $f_{p+2}$ | $a$ | $c$ | $ca$ |

| $f_{p+3}$ | $a$ | $b$ | $ba$ |

| …… | …… | …… | …… |

| $f_{p+2k}$ | $a$ | $c$ | $ca$ |

| $f_{p+2k+1}$ | $a$ | $b$ | $ba$ |

我们设$s_i$在$ca$中的出现次数为$n_c$，在$ba$中的出现次数为$n_b$，$O_n$表示$s_i$在$f_{n+p}$中的出现次数。

那么，容易得到

\[O_n = O_{n-1} + O_{n-2} + \begin{cases} n_c, & \text {if $ n\mod 2 = 0$} \\ n_b, & \text{if $n \mod 2 = 1$}\end{cases}
\]

考虑拆分贡献，即设$A_n$，$B_n$，$C_n$分别表示$f_n$中，$s_i$在$f_p$和$f_{p+1}$中的出现次数，在所有$ba$中的出现次数，在所有$ca$中的出现次数。那么，我们有

$O_n = A_n + B_n \times n_b + C_n \times n_c$
$A_n = A_{n-1} + A_{n-2}$
$B_n = B_{n-1} + B_{n-2} + [n \mod 2 = 1] = B_{n-1} + B_{n-2} + \frac {1 - (-1)^n} {2}$
$C_n = C_{n-1} + C_{n-2} + [n \mod 2 = 0] = C_{n-1} + C_{n-2} + \frac {1 + (-1)^n} {2}$
$B_0 = B_1 = C_0 = C_1 = 0$

其中，$A_n$在我们计算出$A_0$和$A_1$后，用矩阵快速幂得到。故我们只用考虑$B_n$和$C_n$这两个类似的数列。

通过使用OEIS或其他的数列求解方法，我们得到$B_n = F_{n-1} - \frac {1+(-1)^n}{2}$，以及$C_n = F_{n} - \frac{1 - (-1)^n}{2}$。其中，$F_n$为第$n$个斐波那契数。它们同样可以用矩阵快速幂求出。

时间复杂度$O(\sum|s_i| + m \log n )$。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 30010, MAX = 200000, MOD = 1000000007;

string fib[N];

int n,m,len,cnt,lef[N],nex[MAX + 10];

char tmp[MAX + 10];

string a,b,c,tp;

struct matrix {

  int mat[3][3];

  matrix() {

    memset(mat,0,sizeof mat);

  }

  matrix operator * (const matrix& x) const {

    matrix ret = matrix();

    for (int k = 1 ; k <= 2 ; ++ k)

      for (int i = 1 ; i <= 2 ; ++ i)

	for (int j = 1 ; j <= 2 ; ++ j)

	  (ret.mat[i][j] += 1ll * mat[i][k] * x.mat[k][j] % MOD) %= MOD;

    return ret;

  }

};

matrix bas;

matrix power(matrix a,int b) {

  matrix ret = matrix();

  ret.mat[1][1] = ret.mat[2][2] = 1;

  while (b) {

    if (b&1) ret = ret * a;

    a = a * a;

    b >>= 1;

  }

  return ret;

}

int getfib(int x) {

  matrix ret = power(bas,x);

  return ret.mat[1][2];

}

int getnum() {

  int ret = 0;

  for (int i = 0, j = 0 ; i < (int)tp.length() ; ++ i) {

    while (j >= 0 && tmp[j+1] != tp[i])

      j = nex[j];

    ++ j;

    if (j == len) ++ ret, j = nex[j];

  }

  return ret;

}

int solve() {

  nex[0] = -1;

  for (int i = 2, j = 0 ; i <= len ; ++ i) {

    while (j >= 0 && tmp[j+1] != tmp[i])

      j = nex[j];

    nex[i] = ++j;

  }

  int p = lower_bound(lef+1,lef+cnt+1,len) - lef;

  ++ p;

  if (n <= p+1) {

    tp = fib[n];

    return getnum();

  }

  a = fib[p].substr(0,len-1);

  b = fib[p].substr(lef[p] - len+1,len-1);

  c = fib[p+1].substr(lef[p+1] - len+1,len-1);

  int nb, nc, n0, n1, pos = n - p, ret = 0;

  tp = b + a;

  nb = getnum();

  tp = c + a;

  nc = getnum();

  tp = fib[p];

  n0 = getnum();

  tp = fib[p+1];

  n1 = getnum();

  (ret += 1ll * (getfib(pos) - (pos&1)) * nc % MOD) %= MOD;

  (ret += 1ll * (getfib(pos-1) - 1 + (pos&1)) * nb % MOD) %= MOD;

  matrix sta = matrix();

  sta.mat[1][1] = n1;

  sta.mat[1][2] = sta.mat[2][1] = n0;

  sta = sta * power(bas,pos);

  (ret += sta.mat[1][2]) %= MOD;

  ret = (ret % MOD + MOD) % MOD;

  return ret;

}

signed main() {

  fib[1] = "a";

  fib[2] = "b";

  for (int i = 3 ; ; ++ i) {

    fib[i] = fib[i-1] + fib[i-2];

    lef[i] = fib[i].length();

    cnt = i;

    if (lef[i-1] >= MAX) break;

  }

  bas.mat[1][1] = bas.mat[1][2] = bas.mat[2][1] = 1;

  cin >> n >> m;

  for (int i = 1 ; i <= m ; ++ i) {

    scanf("%s",tmp+1);

    len = strlen(tmp+1);

    cout << solve() << endl;

  }

  return 0;

}

小结：用一种不大简单的做法做出了这道题。思考时间过长，并且依赖网站来求解数列，这是做此题时体现出的不足之处。

巴特西

【做题】CF177G2. Fibonacci Strings——思维+数列

最新文章

热门文章