$bzoj1009-HNOI2008$ $GT$考试 字符串$dp$ 矩阵快速幂

时间：2022-06-20 02:08:39

  • 题面描述

    • 阿申准备报名参加\(GT\)考试，准考证号为\(N\)位数\(x_1,x_2,...,x_n\ (0\leq x_i\leq 9)\)，他不希望准考证号上出现不吉利的数字。

      他的不吉利数字\(a_1,a_2,...,a_m\ (0\leq a_i\leq 9)\)有\(M\)位，不出现是指\(x_1,x_2,...,x_n\)中没有恰好一段等于\(a_1,a_2,...,a_m\)。 \(a_1\)和\(x_1\)可以为\(0\)

  • 输入格式

    • 第一行输入\(N,M,K\)。接下来一行输入\(M\)位的数。 \(N\leq 10^9,M\leq 20,K\leq 1000\)

  • 输出格式

    • 阿申想知道不出现不吉利数字的号码有多少种，输出模\(K\)取余的结果。

  • 题解

    • 首先，看到题意是在一定条件下统计 位数\(\leq N\)的数 的个数，第一反应数位\(dp\)。题目对要统计的数的要求是 这个数不能与模式串（不吉利数字）匹配。我们回忆\(KMP\)过程，当原串与模式串在某一位失配时，我们将模式串指针\(x\)通过\(next_x\)不断回跳，直到能够与原串匹配。

    • 类似的，当我们按照数位\(dp\)的阶段，在后面加上\(0-9\)中的数字\(x\)时，我们同样通过\(next_x\)匹配，再在尾部加上数字\(x\)。

    • 因此我们可以设计出这样的\(dp\)方程。令\(f_{i,j}\)表示前\(i\)位匹配到模式串的第\(j\)位的方案数，令\(pre_{i,0..9}\)表示通过\(next_i\)对于在第\(i\)位后加上数字\(0\leq x\leq 9\)匹配到模式串的第\(pre_{i,x}\)位。

    • \[f_{i,pre_{j,x}}+=f_{i-1,j}\ (0\leq j<m,0\leq x\leq 9)
      \]

    • 这样我们得到了一个时间复杂度为\(O(nm)\)的优秀算法。

    • 再看一眼范围\(n\leq 10^9\)！！这样我们就只能用加速线性递推式的神器矩阵快速幂。将递推式写成矩阵的形式，用矩阵快速幂.....（感觉根本不会讲）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=25;

int n,m,mod;

int a[MAXN];

int nxt[MAXN];

struct rec{

	int a[MAXN][MAXN];

	rec(){

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

			for (int j=0;j<=m;j++) a[i][j]=0;

		}

	}

} A;

rec mul(rec a,rec b){

	rec c;

	for (int k=0;k<=m;k++){

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

			for (int j=0;j<=m;j++){

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

			}

		}

	}

	return c;

}

rec mod_pow(rec a,int n){

	rec ans=a; n--;

	while (n){

		if (n&1) ans=mul(ans,a);

		a=mul(a,a);

		n>>=1;

	}

	return ans;

}

int main(){

	scanf("%d%d%d",&n,&m,&mod);

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

		char c=getchar(); while (c<'0'||c>'9') c=getchar();

		a[i]=c-'0';

	}

//	cout<<"done"<<endl;

	nxt[1]=0;

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

		int pre=nxt[i-1];

		while (pre>0&&a[pre+1]!=a[i]) pre=nxt[pre];

		if (a[pre+1]==a[i]) pre++;

		nxt[i]=pre;

	}

//	cout<<"done"<<endl;

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

		for (int j=0;j<=9;j++){

//			cout<<i<<" "<<j<<endl;

			int pre=i;

			while (pre>0&&a[pre+1]!=j) pre=nxt[pre];

			if (a[pre+1]==j) pre++;

			if (pre!=m) A.a[pre][i]=(A.a[pre][i]+1)%mod;

		}

	}

//	cout<<"done"<<endl;

	A=mod_pow(A,n);

	int ans=0;

	for (int i=0;i<m;i++) ans=(ans+A.a[i][0])%mod;

	printf("%d\n",ans);

	return 0;

}

天助自助者

随机推荐

  1. java发送 get请求

    package com.java.base; import java.io.BufferedReader; import java.io.InputStreamReader; import java. ...

  2. VS2010 win7 QT4&period;8&period;0，实现VS2010编译调试Qt程序，QtCreator静态发布程序

    下载源代码,注意一定是源码压缩包如qt-everywhere-opensource-src-4.8.0.zip, 不是Qt发布的已编译的不同版本的标准库如qt-win-opensource-4.8.0 ...

  3. ASP&period;NET缓存全解析6：数据库缓存依赖 转自网络原文作者李天平

    更多的时候,我们的服务器性能损耗还是在查询数据库的时候,所以对数据库的缓存还是显得特别重要,上面几种方式都可以实现部分数据缓存功能.但问题是我们的数据有时候是在变化的,这样用户可能在缓存期间查询的数据 ...

  4. Cordic 算法的原理介绍

    cordic 算法知道正弦和余弦值,求反正切,即角度. 采用用不断的旋转求出对应的正弦余弦值,是一种近似求解发. 旋转的角度很讲求,每次旋转的角度必须使得 正切值近似等于 1/(2^N).旋转的目的是 ...

  5. vbs脚本实现qq定时发消息（初级）

    vbs脚本实现QQ消息定时发送 目标 批处理又称为批处理脚本,强大的强大功能可以高效得实现很多功能,例如批量更改文件格式,批量进行文件读写,今天我们的目标是用vbs脚本编写可以发送qq消息的脚本,并利 ...

  6. SqlServer数据库链接字符串

    完整链接字符串: 1."DataSourse=.\你的实例;Initial Catalog=yourdatabase;User ID=*;Password=*;Trusted_Connect ...

  7. JavaScript：表单常用验证脚本（整理）

    以下内容根据网上资源整理而来,主要来源是CSDN一个供下载的check.js,源码地址找不到了. 1. 检查输入字符串是否为空或者全部都是空格 /* 检查输入字符串是否为空或者全部都是空格 输入:st ...

  8. 使用selenium前学习HTML介绍

    <!-- HTML 是用来描述网页的一种语言. HTML 指的是超文本标记语言 (Hyper Text Markup Language) HTML 不是一种编程语言,而是一种标记语言 (mark ...

  9. Windows编程中回调函数的使用心得&lpar;MFC篇&rpar;

    回调函数就是一个通过函数指针调用的函数.如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数.回调函数不是由该函数的实现方直接调用,而是在特定 ...

  10. 数据库查询操作（fetchone，fetchall）

    数据库查询操作 Python查询Mysql使用 fetchone() 方法获取单条数据, 使用fetchall() 方法获取多条数据. fetchone(): 该方法获取下一个查询结果集.结果集是一个 ...

相关文章