牛客练习赛63 E 题题解

写这份题解之前，还没看见有人写这个题的题解，那么我就来写个吧。~~不排除我眼瞎的可能性~~

首先，我们钦定串 $P$ 为最短的 $f_m$ ，满足 $|f_m| \ge |S|$ ，再钦定 $Q$ 为 $f_{m+1}$ 。

如果 $n < m$ ，则答案一定为 $0$ 。毕竟 $S$ 不可能出现在比它还短的串中。

那么，不难发现，对于 $f_n(n \ge m)$ ， $f_n$ 都能用 $P$ 和 $Q$ 的若干次拼接表示。

然后再经过分析，不难发现，由于 $|S| \leq |P|$ ，且 $|S| \leq |Q|$ ，则 $S$ 在 $f_n$ 中，要么出现在 $P$ 中，要么出现在 $Q$ 中，要么出现在 $P+Q$ 或者 $Q+P$ 或者 $Q+Q$ 的拼接中。

举个栗子，考虑 $P=ab$ ， $Q=aba$ ， $S=ba$ ， $f_{m+4} = P+Q+Q+P+Q=a\underline{ba}\underline{ba}a\underline{ba}a\underline{ba}\underline{ba}$ （此处下划线为标记 $S$ 的匹配位置）。

不难发现， $S$ 只在 $P$ 中出现 $0$ 次，在 $Q$ 中出现 $1$ 次，在 $Q+Q$ 中出现 $0$ 次（这里我们认为，只有 $S$ 在字符串拼接的匹配中，匹配位置包含了前一个串的非空后缀以及后一个串的非空前缀，这个时候 $S$ 才在这个字符串的拼接中出现了），在 $P+Q$ 中出现 $1$ 次，在 $Q+P$ 中出现 $0$ 次。

然后在 $f_{m+4}$ 中， $P$ 、 $Q$ 、 $Q+Q$ 、 $P+Q$ 、 $Q+P$ 的出现次数分别为 $2$ 、 $3$ 、 $1$ 、 $2$ 、 $1$ 次，则将上面的出现次数分别对应相乘，就可以知道 $S$ 在 $f_{m+4}$ 中出现了 $2*0+3*1+1*0+2*1+1*0=5$ 次。结果很正确。

那么，这个计算方式就给了我们一个做法：

分别计算 $P$ 、 $Q$ 、 $Q+Q$ 、 $P+Q$ 、 $Q+P$ 中 $S$ 的出现次数。
分别计算 $P$ 、 $Q$ 、 $Q+Q$ 、 $P+Q$ 、 $Q+P$ 在 $f_n$ 的出现次数。

对于第一步，显然可以使用 $\rm KMP$ 计算匹配数。

对于第二步，有一个简单的 $O(n)$ 递推：分别记录 $f_i$ 中五种串的出现次数，以及当前这个串的开头是 $P$ 还是 $Q$ ，结尾是 $P$ 还是 $Q$ 。然后递推的时候每种串的出现次数都用斐波那契数列的递推公式计算，然后特别对拼接位置多出来的一个拼接是 $P+Q$ 、 $Q+P$ 还是 $Q+Q$ 加一下就行了。

但是 $O(n)$ 的复杂度显然不能接受。由于斐波那契数列可以用矩阵优化转移，这个递推本质上也是一个改造的斐波那契数列，所以也可以用矩阵加速。

upd:

看到有人问矩阵咋构造的，那我就再就这个东西讲一讲吧。

假如不考虑拼接的时候新产生的 $P+Q$ 、 $Q+P$ 、 $Q+Q$ ，那么我们就有这样的转移：

$f_{i, P} = f_{i-1,P}+f_{i-2,P}$

$f_{i, Q} = f_{i-1,Q}+f_{i-2,Q}$

$f_{i, P+Q} = f_{i-1,P+Q}+f_{i-2,P+Q}$

$f_{i, Q+P} = f_{i-1,Q+P}+f_{i-2,Q+P}$

$f_{i, Q+Q} = f_{i-1,Q+Q}+f_{i-2,Q+Q}$

若令：

$F_i= \left\{ \begin{matrix} f_{i,P}\\ f_{i,Q}\\ f_{i,P+Q}\\ f_{i,Q+P}\\ f_{i,Q+Q}\\ f_{i+1,P}\\ f_{i+1,Q}\\ f_{i+1,P+Q}\\ f_{i+1,Q+P}\\ f_{i+1,Q+Q}\\ \end{matrix} \right\}$

且设有转移矩阵 $A$ 满足： $F_i = A \times F_{i-1}$

则可以构造一个 $10 \times 10$ 的矩阵优化上面那个假的转移：

$A= \left\{ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1\\ \end{matrix} \right\}$

然后我们再考虑，怎么将拼接中间的状态考虑进来。

可以发现，除了 $f_{m}$ 这个串是以 $P$ 结尾之外， $f_{m+k}(k>0)$ 的结尾一定都是 $Q$ 。

这也就意味着，除了 $f_{m+2}$ 的拼接中会产生 $P+Q$ 之外，其他的 $f_{m+k}(k>2)$ 的拼接中只可能产生 $Q+P$ 或者 $Q+Q$ 。

那么，特判掉 $n=m$ 的情况之后就能矩阵加速了。

然后，我们就可以考虑两种做法：

在 $F$ 矩阵中加入四行，分别表示 $f_{i}/f_{i+1}$ 的开头/结尾是 $P$ 还是 $Q$ 。如果分别用 $\frac{1}{2}$ ， $-\frac{1}{2}$ 表示是 $P$ 还是 $Q$ 的话，那么就可以在 $A$ 的对应位置中用 $1/-1$ 构造出一个判断。（其实就是单位根反演）
注意到 $P+Q$ 和 $Q+Q$ 的拼接是交替进行的，则可以加入两行分别表示 $f_{i}$ 的拼接是 $Q+P$ 还是 $Q+Q$ 。由于 $f_{i+2}$ 的拼接和 $f_{i}$ 的拼接是一样的（也就是中间拼接的段同为 $Q+P$ 或者 $Q+Q$ ），则可以直接在转移矩阵中加上对应值。

我的代码实现的是第二种方法。则复杂度就是 $O(SZ^3\log_{2}n)$ 。方法二中 $SZ=12$ 。

方法二中，最后转移的 $A$ 矩阵长这样：

$A= \left\{ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ \end{matrix} \right\}$

$F_{i}$ 长这样：

$F_i= \left\{ \begin{matrix} f_{i,P}\\ f_{i,Q}\\ f_{i,P+Q}\\ f_{i,Q+P}\\ f_{i,Q+Q}\\ f_{i+1,P}\\ f_{i+1,Q}\\ f_{i+1,P+Q}\\ f_{i+1,Q+P}\\ f_{i+1,Q+Q}\\ [f_{i}\text{的拼接}=Q+P]\\ [f_{i}\text{的拼接}=Q+Q]\\ \end{matrix} \right\}$

以下贴出我的代码给大家作为参考。

/********************************************************************************

    Code by a weak man who named CYJian, and he hopes the code could get more points.

    Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
    char ch, t = 0; x = 0;
    while(!isdigit(ch = ge)) t |= ch == '-';
    while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
    x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

const int MAXN = 2000010;
const int mod = 1e9 + 7;

char A[MAXN];
char B[MAXN];
char S[MAXN];
char T[MAXN];
int la, lb, ls;

struct Matrix {
    int a[12][12];
    int n, m;

    friend Matrix operator * (Matrix a, Matrix b) {
        Matrix c; c.n = a.n, c.m = b.m;
        memset(c.a, 0, sizeof(c.a));
        for(int i = 0; i < a.n; i++)
            for(int j = 0; j < b.m; j++)
                for(int k = 0; k < a.m; k++)
                    c.a[i][j] = (1LL * a.a[i][k] * b.a[k][j] + c.a[i][j]) % mod;
        return c;
    }
}a;

inline Matrix fsp(Matrix a, ll k) {
    Matrix s; s.n = 12, s.m = 1;
    memset(s.a, 0, sizeof(s.a));
    if(k == 0) {
        s.a[0][0] = 1;
        s.a[6][0] = 1;
        return s;
    }
    --k;
    s.a[1][0] = 1;
    s.a[5][0] = 1;
    s.a[6][0] = 1;
    s.a[7][0] = 1;
    s.a[10][0] = 1;
    while(k) {
        if(k & 1) s = a * s;
        a = a * a, k >>= 1;
    } return s;
}

inline void Add() {
    int l = 0;
    for(int i = 1; i <= la; i++) T[++l] = A[i];
    for(int i = 1; i <= lb; i++) T[++l] = B[i];
    la = lb;
    for(int i = 1; i <= la; i++) A[i] = B[i];
    lb = l;
    for(int i = 1; i <= lb; i++) B[i] = T[i];
}

int fail[MAXN];

inline void Kmp(int n) {
    for(int i = 2; i <= n; i++) {
        int j = fail[i - 1];
        while(j && S[i] != S[j + 1]) j = fail[j];
        j += S[i] == S[j + 1], fail[i] = j;
    }
}

inline int Calc(int n) {
    int cnt = 0;
    for(int i = 1, j = 0; i <= n; i++) {
        while(j && S[j + 1] != T[i]) j = fail[j];
        j += T[i] == S[j + 1];
        if(j == ls) j = fail[j], ++cnt;
    } return cnt;
}

int main() {
#ifdef LOCAL
    FILE("");
#endif

    ll n;
    scanf("%lld%s%s%s", &n, A + 1, B + 1, S + 1);
    --n;

    la = strlen(A + 1);
    lb = strlen(B + 1);
    ls = strlen(S + 1);

    while(n && (la < ls || lb < ls)) Add(), --n;

    int len;

    Kmp(ls);

    len = 0;
    for(int i = 1; i <= la; i++) T[++len] = A[i];
    int len_A = Calc(len);

    len = 0;
    for(int i = 1; i <= lb; i++) T[++len] = B[i];
    int len_B = Calc(len);

    len = 0;
    for(int i = 1; i <= la; i++) T[++len] = A[i];
    for(int i = 1; i <= lb; i++) T[++len] = B[i];
    int len_AB = Calc(len) - len_A - len_B;

    len = 0;
    for(int i = 1; i <= lb; i++) T[++len] = B[i];
    for(int i = 1; i <= la; i++) T[++len] = A[i];
    int len_BA = Calc(len) - len_A - len_B;

    len = 0;
    for(int i = 1; i <= lb; i++) T[++len] = B[i];
    for(int i = 1; i <= lb; i++) T[++len] = B[i];
    int len_BB = Calc(len) - len_B - len_B;

    a.n = a.m = 12;
    a.a[0][5] = 1;
    a.a[1][6] = 1;
    a.a[2][7] = 1;
    a.a[3][8] = 1;
    a.a[4][9] = 1;
    a.a[5][0] = a.a[5][5] = 1;
    a.a[6][1] = a.a[6][6] = 1;
    a.a[7][2] = a.a[7][7] = 1;
    a.a[8][3] = a.a[8][8] = a.a[8][10] = 1;
    a.a[9][4] = a.a[9][9] = a.a[9][11] = 1;
    a.a[10][11] = a.a[11][10] = 1;

    Matrix f = fsp(a, n);

    int res = (1LL * len_A * f.a[0][0] + 1LL * len_B * f.a[1][0] + 1LL * len_AB * f.a[2][0] + 1LL * len_BA * f.a[3][0] + 1LL * len_BB * f.a[4][0]) % mod;

    cout << res << endl;
    return 0;
}