bzoj 1009 [HNOI2008]GT考试 (KMP+矩阵乘法)_guapisolo的博客-程序员秘密_hnoi2008 gt考试

技术标签: DP优化  矩阵乘法  bzoj  KMP  

题目大意:给定一个由数字构成的字符串A(len<=20),让你选择一个长度为n(n是给定的)字符串X,一个合法的字符串X被定义为,字符串X中不存在任何一段子串与A完全相同,求互不相同的合法的字符串L的数量

第一眼看就没啥思路....瞅了一眼题解,是KMP优化DP,然后再用矩阵优化DP

思路还是不难的,首先用KMP求出原字符串的next数组,再用next转移

定义f[i][j]是当前X串匹配到了第i位,已经匹配到了字符串A的第j位

每次在X串的第j+1位填上一个数c,那么X串现在最长能匹配上A串的位置

就是从第j+1位一直往前跳next,直到碰到一个位置a[k]==a[j]或k==0也匹配不到

int k=i+1;
for(k=i+1;k>0&&a[k]!=c;k=nxt[k])
    ;
pw.mp[k][i]++;
    

这是一个连续的过程,上面是构建矩阵的核心代码(原来的代码太丑了我改了一下)

至于为什么要这么跳呢,这是一个类似于"贪心"的过程,但并不是我们主动去贪心

因为我们要保证每次转移的位置都是正确的

然后发现N<=1e9有点大,矩阵乘法优化一下即可

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long 
#define N 23
#define ui unsigned int
#define inf 0x3f3f3f3f
using namespace std;
//re
int n,len;
ui mod;
char str[N];
int a[N],nxt[N];
struct mtx{
    ui mp[N][N];
    friend mtx operator *(const mtx &s1,const mtx &s2)
    {
        mtx ret;memset(&ret,0,sizeof(ret));
        for(int i=0;i<len;i++)
            for(int j=0;j<len;j++)
                for(int k=0;k<len;k++) 
                    (ret.mp[i][j]+=(s1.mp[i][k]*s2.mp[k][j])%mod)%=mod;
        return ret;
    }
    mtx qpow(mtx &ans,mtx &x,int y)
    {
        while(y){
            if(y&1) ans=x*ans;
            x=x*x;y>>=1;
        }
    }
}M;
void get_kmp()
{
    int i=1,j=0;
    nxt[1]=0;
    while(i<=len)
        if(j==0||a[i]==a[j])
            i++,j++,nxt[i]=j;
        else j=nxt[j];
}

int main()
{
    scanf("%d%d%u",&n,&len,&mod);
    scanf("%s",str+1);
    for(int i=1;i<=len;i++) a[i]=str[i]-'0';
    get_kmp();
    mtx pw;memset(&pw,0,sizeof(pw));
    for(int i=0;i<len;i++)
        for(int c=0;c<=9;c++)
        {
            if(i==len-1&&a[len]==c) continue;
            int k=i+1;
            for(k=i+1;k>0&&a[k]!=c;k=nxt[k]);
            pw.mp[k][i]++;
        }
    mtx ret;memset(&ret,0,sizeof(ret));
    ret.mp[0][0]=1;
    M.qpow(ret,pw,n);
    ui ans=0;
    for(int i=0;i<len;i++)
        (ans+=ret.mp[i][0])%=mod;
    printf("%u\n",ans);
    return 0;
}





 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/guapisolo/article/details/82810469

智能推荐

人物志:一个平庸程序员的想法_醉心编码的博客-程序员秘密_人物志拍摄脚本

前天晚上,老婆和我偎在床上说悄悄话,大致的意思是所有她的同学都有房子了,有些还当上了管理人员,并带着少许调侃说我以后也就这样了,1年10多万,失业就会掉头发。 我今年28,一个C++/Java程序员,跟大多数人一样,天资平平,虽然爱学习,但没有上一个好大学,工作这么几年也没有混上一个管理人员,有时候在自己看来,稍稍有些可悲。因为官本位的残留+农耕文化,在中国搞技术历来就是一个吃力不讨好的事情。搞技

K8S从入门到放弃系列-(7)kubernetes集群之kube-scheduler部署_akfeu48868的博客-程序员秘密

摘要:1、Kube-scheduler作为组件运行在master节点,主要任务是把从kube-apiserver中获取的未被调度的pod通过一系列调度算法找到最适合的node,最终通过向kube-apiserver中写入Binding对象(其中指定了pod名字和调度后的node名字)来完成调度2、kube-scheduler与kube-controller-manager一样,如...

一次永久解决cmd窗口汉字显示乱码_曲小鑫的博客-程序员秘密_cmd 乱码

对于编译出的程序,在 cmd 和 power shell 运行时都不能正确显示汉字。 网上查,可以再命令窗口修改: 1、打开CMD.exe命令行窗口 2、通过 chcp命令改变代码页,UTF-8的代码页为65001 chcp 65001 执行该操作后,代码页就被变成UTF-8了。但是,在窗口中仍旧不能正确显示UTF-8字符。在当前窗口的确可以解决问题,但是重

Intellij idea 出现错误 error:java: 无效的源发行版: 11_士心月月鸟的博客-程序员秘密

一、问题描述: idea在运行spring boot项目时,报错error:java: 无效的源发行版: 11二、解决方案:两个地方同步:1.8 和 8 的版本若还不能解决,建议重新创建项目,选择jdk 8的版本进入...

锂离子电池开路电压与电池容量的对应关系分析_pan0755的博客-程序员秘密_锂离子电池开路电压

锂离子电池开路电压与电池容量的对应关系分析    先给出一个表格:如下,百分比是电池的剩余容量,右侧是对应的电池的开路电压(OCV).  100%----4.20V  90%-----4.06V  80%-----3.98V  70%-----3.92V  60%-----3.87V  50%-----3.82V  40%-----3.79V  30%---

python创建mysql数据库中的表_ACE-Mayer的博客-程序员秘密_python创建mysql用户

import pymysql#参数一:服务器IP#参数二:端口号#参数三:用户名#参数四:用户密码#参数五:数据库名conn = pymysql.connect(host="localhost",port=3306,user="root",password="mysql",db="smy_db")#创建一个cursor对象,由cursor对象执行SQL语句以及获得执行结果cur = conn.cursor()sql_1="drop table if exists table_test

随便推点

node.js 安装_快乐de馒头的博客-程序员秘密

PS: ~ 此篇文章的进阶内容在为《Nodejs初阶之express》  ~ 2014/09/24 更新《Express 4.X 启航指南》  欢迎阅读和评论:)   最近写的文章收到许多朋友的反馈,感谢大家的支持和建议,让我对坚持写博客充满热情,一个月一篇文章确实有点少,所以以后尽力多做分享,做好的分享,希望能对朋友们有用。  到新公司的这段时间学

C++ push方法与push_back方法的使用与区别_杰明学编程的博客-程序员秘密

【摘要】push与push_back是STL中常见的方法,都是向数据结构中添加元素。初识STL,对于添加元素的方法以产生混淆,这里暂对两种方法作出比较分析。此外,本文还将简述push对应的stack与queue系列,常见方法的介绍,以及与push_back相对应的vector系列常见方法介绍。详见下文。list 也是使用 push_back .【正文】push_back 方法介绍vector::void push_back (const value_type&amp; val);vector::

Linux:xshell6终端ls无颜色解决_全员鳄鱼的博客-程序员秘密

前言上次解决了终端名等没有颜色的问题,现在发现ls指令也没有颜色,现在尝试使用ls指令在xshell上也会有颜色修改先cd到用户主目录下cd ~然后vim 修改.profile文件vim .profile添加并保存:if [ -f "$HOME/.bashrc" ];then. "$HOME/.bashrc"fi再修改.bashrc文件vim /.bashrc添加并保存: alias ls='ls --color'最后将重新source一下即可...

只有一个实例运行_zhoxier的博客-程序员秘密

HANDLE hMutex=::CreateMutex(NULL,TRUE,_T("FirstName"));//FirstName可以随便取一个唯一的名字   if   (hMutex!=NULL)   {   if   (GetLastError()==ERROR_ALREADY_EXISTS)   {   AfxMessageBox(_T("已经有一个程序运行."));

【C】利用单链表数据结构实现通讯录,链表的增删改查_yongh701的博客-程序员秘密

C语言中实现链表,是需要利用到C语言中比较难的结构体与指针才能实现。结构体中放一个指向后接节点的指针与每一个结点应该存放的信息。下面做一个命令行的通讯录来说明链表的增删改查这个问题。一开始让用户输入链表,按1可以输出,按3可以删除。可以修改:可以插入。按0则可以退出:代码如下:#include#includetypedef str

GAMS的使用_小皮飞的博客-程序员秘密_gams官网

The General Algebraic Modeling System (GAMS)是一款数学规划和优化的高级建模系统。本文简单通过一个例子简单介绍GAMS的用法。GAMS官方网站:http://www.gams.com/例子:运输问题基本模型代码:sets i canning plants /seattle, san-diego/

推荐文章

热门文章

相关标签