BZOJ 1009 HNOI 2008 GT考试 递推+矩乘
2024-10-19 04:23:15
1009: [HNOI2008]GT考试
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3679 Solved: 2254
[Submit][Status][Discuss]
Description
阿申准备报名参加GT考试,准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位,不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为
0
Input
第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000
Output
阿申想知道不出现不吉利数字的号码有多少种,输出模K取余的结果.
Sample Input
4 3 100
111
111
Sample Output
81
Solution
如果n很小的话,可以直接做数位DP,但是现在n很大,需要用到矩乘。
设F[i][j]表示准考证号前i位中匹配到不吉利数串的第j个的方案数。
我们很容易发现,F数组存在一定的转移关系。
转移时考虑当前匹配到不吉利串的第i个,下一个数字填0~9时,转移到匹配到不吉利串的第j个,匹配过程可以KMP,这样就可以构造出转移矩阵。
Code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define mset(a, b) memset(a, b, sizeof(a))
const int maxn = ;
int n, m, MOD;
char s[maxn];
int nxt[maxn];
struct Matrix
{
int mat[maxn][maxn];
Matrix() { mset(mat, ); }
Matrix operator * (const Matrix &AI) const
{
Matrix ret;
REP(i, , m-)
REP(j, , m-)
{
ret.mat[i][j] = ;
REP(k, , m-) (ret.mat[i][j] += mat[i][k]*AI.mat[k][j]) %= MOD;
}
return ret;
}
}A, B; int main()
{
scanf("%d %d %d", &n, &m, &MOD);
scanf("%s", s+);
int j = ; nxt[] = ;
REP(i, , m)
{
while (j > && s[j+] != s[i]) j = nxt[j];
if (s[j+] == s[i]) j ++;
nxt[i] = j;
}
REP(i, , m-)
REP(j, , )
{
int t = i;
while (t > && s[t+]-'' != j) t = nxt[t];
if (s[t+]-'' == j) t ++;
if (t != m) B.mat[t][i] = (B.mat[t][i]+)%MOD;
}
REP(i, , m-) A.mat[i][i] = ;
while (n > )
{
if (n&) A = A*B;
B = B*B;
n >>= ;
}
int ans = ;
REP(i, , m-) ans = (ans+A.mat[i][])%MOD;
printf("%d\n", ans);
return ;
}
最新文章
- TclError: no display name and no $DISPLAY environment variable
- yum安装rz和sz
- rails provide与content_for的区别
- ISO9126软件质量模型
- Rstudio安装
- Tomcat原理 分类: 原理 2015-06-28 19:26 5人阅读 评论(0) 收藏
- js点击图片显示在左边大图
- 工作日志2014-06-10(实现C语言解析XML获得查询关键字)
- 浅谈卷积神经网络及matlab实现
- RTLinux编程总结
- oracle修改密码为永久不过期
- mac新手使用
- ajax 请求被终止 chrome查询发现请求状态status为canceled
- 对于Servlet、Servlet容器以及一个Servlet容器-Tomcat
- Solidity合约:玉米生产溯源
- 发送统计邮件shell脚本
- 代码提示级别设置 inspection
- python学习笔记——多进程一 基础概念
- Hibernate 4.3 SessionFactory
- JavaScript里的循环方法之forEach,for-in,for-of
热门文章
- hdu 5290 Bombing plan
- 2018年9月28日CCPC秦皇岛站参赛总结
- django2.0 官方中文文档地址
- [百度地图] 用于类似 DWZ UI 框架的 百度地图 功能封装类 [MultiZMap.js] 实例源码
- TED_Topic10:The case for engineering our food
- HDU 4506 小明系列故事——师兄帮帮忙(二分快速幂)
- linux usb枚举过程分析之守护进程及其唤醒【转】
- 清理电脑文件夹中的Thumbs.db文件
- like语句防止SQL注入
- mybatis SQL构造器