题解 P5337 【[TJOI2019]甲苯先生的字符串】

· · 题解

有点思维含量的题啊。

虽然作为省选题太套路了。

很显然是dp

设f[i][j]表示长度为i,末位为字符j的方案数

很显然的转移式

f[i][j]+=f[i-1][k]\ (kj\ \text{不为s1的子串})

但是n很大，怎么办呢？

发现是否可以转移的情况是固定的

可以考虑使用矩阵来判断是否可以转移。

如果字符串ij不为s1的子串，那么矩阵X中X[i][j]=1，否则X[i][j]=0。

一次转移就是做一次矩阵乘法 $\begin{bmatrix}f[1] & f[2] & ... &f[26]\end{bmatrix}\times X

为什么呢？

因为f[i][j]+=f[i-1][k]\ (kj\ \text{不为s1的子串})

也就是f[i][j]+=f[i-1][k]\times X[k][j]

就是

f[j]=\sum_{k=1}^{26}f[k]\times X[k][j]

正好是矩阵的形式。

由于初始条件下f[1]=f[2]=...=1，所以我们只要求出X^{n-1}矩阵中所有数的和就好了。矩阵快速幂做到时间复杂度O(26^3log_2n)

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ljc 1000000007
using namespace std;
long long n,m,pr,nf,x;
char s[1000001];
struct matrix{
    long long x[27][27];long long sz;   
    inline void clear(){
        for (int i=1;i<=26;i++){
            for (int j=1;j<=26;j++){
                x[i][j]=0;
            }
        }
    }
}a,one;
inline matrix mul(matrix a,matrix b){
    matrix c;
    c.clear();c.sz=a.sz;
    for (int i=1;i<=26;i++){
        for (int j=1;j<=26;j++){
            for (int k=1;k<=26;k++){
                c.x[i][j]=(c.x[i][j]%ljc+a.x[i][k]%ljc*b.x[k][j]%ljc)%ljc;
            }
        }
    }
    return c;
}
inline matrix fast_pow(matrix a,long long b){
    matrix t=one;
    while (b){
        if (b&1LL) t=mul(t,a);
        a=mul(a,a);b/=2LL;
    }
    return t;
}
inline void init_one(){
    one.sz=a.sz;
    for (int i=1;i<=26;i++){
        one.x[i][i]=1;
    }
}
int main(){
    scanf("%lld",&n);
    init_one();
    for (int i=1;i<=26;i++){
        for (int j=1;j<=26;j++){
            a.x[i][j]=1;
        }
    }
    scanf("%s",s+1);
    int len=strlen(s+1);
    for (int i=2;i<=len;i++){
        a.x[s[i-1]-'a'+1][s[i]-'a'+1]=0;
    }
    a=fast_pow(a,n-1);
    long long ans=0;
    for (int i=1;i<=26;i++){
        for (int j=1;j<=26;j++){
            ans=(ans+a.x[i][j])%ljc;
        }
    }
    cout<<ans;
}