【GDOI2016模拟3.9】暴走的图灵机-程序员宅基地

技术标签: 字符串  矩阵乘法  题解  

题目

这里写图片描述

分析

我们发现当两个字符串合并时,a0a1表示左右两个字符串中有多少个TC表示合并处新增的T的个数,那么
a0=a1
a1=a0+a1+C
s0s1表示左右手两个字符串,那么每一次操作后左右手字符串分别为:

操作次数             左手  右手
  0                  s0   s1
  1                  s1   s0s1
  2                s0s1   s1s0s1
  3              s1s0s1   s0s1s1s0s1
  4          s0s1s1s0s1   s1s0s1s0s1s1s0s1
  5    s1s0s1s0s1s1s0s1   s0s1s1s0s1s1s0s1s0s1s1s0s1
  ···

然后我们发现,从第1次操作以后,每次合并处是以s1s1s1s0为一个循环。也就是说当|s0|>=m-1时,我们用KMP处理出a0a1以及s1s1s1s0合并时新增T的个数,然后O(N)递推一遍就可以了。
但是n<=10^9,只能拿60分。
因为递推时有循环,所以就可以构造矩阵,打个矩阵快速幂O(logN)。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
using namespace std;
char s[30000],s1[30000],s2[30000],t[30000];
long long n,m,tot,ans,mo,next[30000],f[2][5],lens=1,lens1=1,nn,nnn;
long long jz[5][5]=
{
{
   0,0,0,0,0},
{
   0,1,1,0,0},
{
   0,1,2,0,0},
{
   0,1,1,1,0},
{
   0,0,1,0,1} 
},b[5][5];
long long getnext()
{
    long long i,j,k;
    j=0;
    for(i=2;i<=m;i++)
    {
        while(j>0 && t[j+1]!=t[i]) j=next[j];
        if(t[j+1]==t[i]) j++;
        next[i]=j;
    }
}
long long kmp()
{
    long long i,j,k;
    getnext();
    j=0;
    for(i=1;i<=lens;i++)
    {
        while(j>0 && t[j+1]!=s[i]) j=next[j];
        if(t[j+1]==s[i]) j++;
        if(j==m) f[0][1]++;
    }
    j=0;
    for(i=1;i<=lens1;i++)
    {
        while(j>0 && t[j+1]!=s1[i]) j=next[j];
        if(t[j+1]==s1[i]) j++;
        if(j==m) f[0][2]++;
    }
}
long long kmp1()
{
    long long i,j,k;
    k=0;
    for(i=lens-m+2;i<=lens;i++)
        s2[++k]=s[i];
    for(i=1;i<=m-1;i++)
        s2[++k]=s1[i];
    j=0;
    for(i=1;i<=m+m-2;i++)
    {
        while(j>0 && t[j+1]!=s2[i]) j=next[j];
        if(t[j+1]==s2[i]) j++;
        if(j==m) f[0][0]++;
    }
    k=0;
    for(i=lens1-m+2;i<=lens1;i++)
        s2[++k]=s1[i];
    for(i=1;i<=m-1;i++)
        s2[++k]=s[i];
    j=0;
    for(i=1;i<=m+m-2;i++)
    {
        while(j>0 && t[j+1]!=s2[i]) j=next[j];
        if(t[j+1]==s2[i]) j++;
        if(j==m) f[0][3]++;
    }
    k=0;
    for(i=lens1-m+2;i<=lens1;i++)
        s2[++k]=s1[i];
    for(i=1;i<=m-1;i++)
        s2[++k]=s1[i];
    j=0;
    for(i=1;i<=m+m-2;i++)
    {
        while(j>0 && t[j+1]!=s2[i]) j=next[j];
        if(t[j+1]==s2[i]) j++;
        if(j==m) f[0][4]++;
    }
}
long long mi()
{
    long long x=0,y=1,i,j,k;
    while(nn>0)
    {
        if(nn&1==1)
        {   
            for(i=1;i<=4;i++)
            {
                f[x][i]=0;
                for(j=1;j<=4;j++)
                    f[x][i]=(f[x][i]+(f[y][j]*jz[j][i])%mo)%mo;
            }
            x=y;
            y=1-y;
        }
        for(i=1;i<=4;i++)
            for(j=1;j<=4;j++)
            {
                b[i][j]=0;
                for(k=1;k<=4;k++)
                {
                    b[i][j]=(b[i][j]+(jz[i][k]*jz[k][j])%mo)%mo;
                }
            }
        for(i=1;i<=4;i++)
            for(j=1;j<=4;j++)
            {
                jz[i][j]=b[i][j];
            }
        nn/=2;
    }
    return y;
}
int main()
{
    scanf("%d%d%d",&n,&m,&mo);
    scanf("%s",t+1);
    s[1]='0';
    s1[1]='1';
    long long i,j,k,l,x,y;
    for(j=1;j<=n;j++)
    {
        for(i=1;i<=lens1;i++)
            s2[i]=s1[i];
        for(i=1;i<=lens;i++)
            s1[i]=s[i];
        for(i=1;i<=lens1;i++)
        {
            s1[lens+i]=s2[i];
        }
        for(i=1;i<=lens1;i++)
            s[i]=s2[i];
        x=lens1;
        lens1+=lens;
        lens=x;
        y=j;
        if(lens>=m)
            break;
    }
    kmp();
    if(n==y)
    {
        printf("%d\n",f[0][1]%mo);
        return 0;
    }
    kmp1();
    f[1][1]=(f[0][2])%mo;
    f[1][2]=(f[0][1]+f[0][2]+f[0][0])%mo;
    f[1][3]=(f[0][3])%mo;
    f[1][4]=(f[0][4])%mo;
    n-=y+1;
    x=1;
    y=0;
    y=f[1][3];
    n-=0;
    nnn=n%2;
    nn=n/2;
    x=mi();
    if(nnn==1)
    {
        printf("%d\n",(f[x][2])%mo);
        return 0;
    }
    else
        printf("%d\n",f[x][1]%mo);
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/chen1352/article/details/51146189

智能推荐

matlab中fliter函数,用C语言实现MATLAB中Filter()函数-程序员宅基地

文章浏览阅读445次。#include#define Width 3 //滤波器门宽#define Inputlength 20//输入信号的个数void myfilter(int, float *, float *, int, float *, float *);int main() {int j,k;float a[3] = { 1,-1.5,0.25 };//分母系数向量,可自行设置float b[3] = { ..._用之前的乘积和减去分母系数与过去输出函数的乘积差

编程书籍分享(持续更新....)-程序员宅基地

文章浏览阅读665次,点赞4次,收藏7次。本页面分享IT技术书籍,所有的书籍均是完整的pdf,所有书籍都有看过(大部分没看完),都是我认为非常不错的书籍,分享给大家,放在csdn下载。下载积分都设置为1(csdn现在没办法设置成不用积分下载),但如果下载人数太多,csdn会自动把积分调高,如果没有积分的可以在下方留email,我会尽快发给你。课程书籍编程开发C++Linux编程Windows编程汇编PythonJa...

Linux内核笔记(驱动篇)之 【MMC里的轮询机制】_linux mmc驱动-程序员宅基地

文章浏览阅读208次。最近遇到客户提的一个问题,大概意思是他们的SDIO Wi-Fi在卸载Wi-Fi驱动后再加载就检测不到Wi-Fi设备了。从他的问题看大概是热插拔有问题。_linux mmc驱动

android入门之Activity Recents screen-程序员宅基地

文章浏览阅读252次。文档:https://developer.android.com/guide/components/activities/recents1.简介最近的屏幕是一个系统级 UI,也称为概览屏幕、最近的任务列表或最近的应用程序列出了最近访问的活动和任务。用户可以在列表中导航并选择恢复任务,或者从列表中移除。最近屏幕使用以文档为中心的模型(在 Android 5.0 中引入)其中包含不同文档的同一活动的多个实例可能在最近屏幕中显示为任务。Google Drive 可能对每一个文档都有_recents screen

ERROR: cannot launch node of type [map_server/map_server]: map_server_[error] [1688396936.736257295]: map_server excepti-程序员宅基地

文章浏览阅读2.2k次。如上图所示,版本号为:noetic根据ros版本号,进行安装:sudo apt-get install ros-noetic-map-server 将noetic换成你的版本号_[error] [1688396936.736257295]: map_server exception: operator[] call on a s

mariadb用户群体mysql_mysql(mariadb)新建用户及用户授权管理-程序员宅基地

文章浏览阅读54次。仅新建一个newuser用户方法一:MariaDB [(none)]> create user newuser@localhost identified by ‘123456’;Query OK, 0 rows affected (0.22 sec)MariaDB [(none)]> select user from mysql.user;+———+| user |+———+| ..._mariadb [(none)]> grant all privileges on *.* to root@'%' identified by '123

随便推点

外网电脑访问内网linux服务器(设置路由端口映射)_校外如何访问linux服务器-程序员宅基地

文章浏览阅读1.6w次。在日常工作中,我们往往遇到这种情况:我们在外网的一个客户端需要远程控制一个内网的linux服务器。要实现合格功能很简单。1,局域网内客户端登陆linux服务器 只需在客户端下载一个putty软件,打开putty后,在Host Name(or IP Address)处输入服务器的名字或者局域网内为服务器分配的IP地址即可(端口号为22,连接类型为SSH)。_校外如何访问linux服务器

地震信号分析与处理系统设计(matlab/simulink/labview)_地震信号检测与处理-程序员宅基地

文章浏览阅读1.3k次。地震信号分析总体方案设计;查阅资料,分析地震勘探原始地震信号的特点,绘制出其时域波形并加以分析;地震信号的频谱分析:查阅资料,分析不同类型的地震信号的频域特征,对地震信号做谱分析,绘制频域波形图;设计相应的滤波器去除地震信号的噪声:根据地震信号的频域特征,设计相应滤波器去除噪声;地震信号处理系统的时频分析:采用短时傅里叶变换对地震信号进行时频分析;地震信号处理系统GUI用户界面设计:针对设计的地震信号分析系统,利用GUI设计图形用户界面,实现系统的相关功能;基于LabView仿真。_地震信号检测与处理

第07课:动手实战基于 ML 的中文短文本聚类-程序员宅基地

文章浏览阅读1k次。关于文本聚类,我曾在 Chat《NLP 中文文本聚类之无监督学习》中介绍过,文本聚类是将一个个文档由原有的自然语言文字信息转化成数学信息,以高维空间点的形式展现出来,通过计算哪些点距离比较近,从而将那些点聚成一个簇,簇的中心叫做簇心。一个好的聚类要保证簇内点的距离尽量的近,但簇与簇之间的点要尽量的远。如下图,以 K、M、N 三个点分别为聚类的簇心,将结果聚为三类,使得簇内点的距离尽量的近,但簇与...

Spring中的BeanFactory与FactoryBean_beanfactory添加bean-程序员宅基地

文章浏览阅读315次。Spring中的BeanFactory与FactoryBean_beanfactory添加bean

android开发边框阴影,Android 卡片边框模糊阴影效果实现-程序员宅基地

文章浏览阅读785次。1. 使用标签内写多个套标签实现android:bottom="2dp"android:left="2dp"android:right="2dp"android:top="0dp" />android:bottom="2dp"android:left="2dp"android:right="2dp"android:top="0dp" />android:bottom="2dp"andr..._android 卡片阴影效果

SQL语句中单引号、双引号和反引号的区分_sql中区分引号吗-程序员宅基地

文章浏览阅读850次。单引号 ’ 和双引号 “在标准 SQL 中,字符串使用的是单引号。如果字符串本身也包括单引号,则使用两个单引号(注意,不是双引号,字符串中的双引号不需要另外转义)。MySQL对 SQL 的扩展,允许使用单引号和双引号两种。反引号 `反引号一般在Esc键的下方,和~在一起。它是为了区分MySQL的保留字与普通字符而引入的符号。 create table desc 报错 create t..._sql中区分引号吗

推荐文章

热门文章

相关标签