M_sea

洛谷5337 [TJOI2019]甲苯先生的字符串
LuoguBZOJLOJ分析DP+矩阵快速幂。设 $f[i][j]$ 表示前 $i$ 个字符,第 $i$ 个字符是...
扫描右侧二维码阅读全文
05
2019/05

洛谷5337 [TJOI2019]甲苯先生的字符串

Luogu

BZOJ

LOJ

分析

DP+矩阵快速幂。

设 $f[i][j]$ 表示前 $i$ 个字符,第 $i$ 个字符是 $j$ 的方案数。

转移比较简单: $f[i][j]=\sum f[i-1][k]\ (kj\text{不为}s_1\text{的子串})$

然后拿矩阵快速幂优化一下转移就行了。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int mod=1e9+7;

char a[100010];
int ban[30][30];

struct Matrix {
    int n,m;
    int s[30][30];

    Matrix() { n=m=0; memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} A,G;

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

inline Matrix qpow(Matrix a,ll b) {
    Matrix c; c.n=a.n,c.m=a.m;
    for (re int i=1;i<=c.n;++i) c[i][i]=1;
    for (;b;b>>=1,a=a*a)
        if (b&1) c=c*a;
    return c;
}

int main() {
    ll n; scanf("%lld",&n);
    scanf("%s",a+1); int l=strlen(a+1);
    for (re int i=1;i<l;++i) ban[a[i]-'a'+1][a[i+1]-'a'+1]=1;

    A.n=1,A.m=26;
    for (re int i=1;i<=26;++i) A[1][i]=1;
    G.n=G.m=26;
    for (re int i=1;i<=26;++i)
        for (re int j=1;j<=26;++j) {
            if (!ban[i][j]) G[i][j]=1;
            else G[i][j]=0;
        }

    A=A*qpow(G,n-1);
    int ans=0;
    for (re int i=1;i<=26;++i) ans=(ans+A[1][i])%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 05 PM

发表评论