【bzoj1009】[HNOI2008]GT考试（矩阵快速幂优化dp+kmp）

时间：2023-03-09 10:02:36
【bzoj1009】[HNOI2008]GT考试（矩阵快速幂优化dp+kmp）

　　题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1009

　　这道题一看数据范围：$ n<=10^9 $，显然不是数学题就是矩乘快速幂优化dp。

　　我们设$ f[i][j] $表示前$ i $位匹配不吉利数字$ j $位时的方案数，因为每一位的转移方式都是相同的，于是用kmp预处理出转移矩阵，直接矩乘快速幂就能过了。

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define ll long long

#define ull unsigned long long

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

#define lowbit(x) (x& -x)

#define inf 0x3f3f3f3f

#define eps 1e-18

#define maxn 100010

inline ll read(){ll tmp=; char c=getchar(),f=; for(;c<''||''<c;c=getchar())if(c=='-')f=-; for(;''<=c&&c<='';c=getchar())tmp=(tmp<<)+(tmp<<)+c-''; return tmp*f;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void swap(int &a,int &b){int tmp=a; a=b; b=tmp;}

using namespace std;

struct matrix{

    int size;

    int num[][];

}ans;

int nxt[];

char s[];

int n,m,mod;

matrix mul(matrix a,matrix b)

{

    matrix c; memset(&c,,sizeof(c));

    c.size=a.size;

    for(int i=;i<=a.size;i++)

        for(int j=;j<=a.size;j++)

            for(int k=;k<=a.size;k++)

                c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%mod;

    return c;

}

matrix power(matrix a,ll b)

{

    matrix ans; memset(&ans,,sizeof(ans));

    ans.size=a.size;

    for(int i=;i<=ans.size;i++)ans.num[i][i]=;

    for(;b;b>>=){

        if(b&)ans=mul(ans,a);

        a=mul(a,a);

    }

    return ans;

}

int main()

{

    n=read(); m=read(); mod=read();

    scanf("%s",s);

    nxt[]=; int tmp=;

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

        while(tmp&&s[i]!=s[tmp])tmp=nxt[tmp];

        if(s[i]==s[tmp])++tmp;

        nxt[i+]=tmp;

    }

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

        for(int j='';j<='';j++){

            int tmp=i;

            while(tmp&&j!=s[tmp])tmp=nxt[tmp];

            if(j==s[tmp])++tmp;

            if(tmp<m)++ans.num[i+][tmp+];

        }

    ans.size=m;

    ans=power(ans,n);

    int tot=;

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

        tot+=ans.num[][i];

    printf("%d\n",tot%mod);

}

bzoj1009

相关文章