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

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 ;
}

最新文章

  1. TclError: no display name and no $DISPLAY environment variable
  2. yum安装rz和sz
  3. rails provide与content_for的区别
  4. ISO9126软件质量模型
  5. Rstudio安装
  6. Tomcat原理 分类: 原理 2015-06-28 19:26 5人阅读 评论(0) 收藏
  7. js点击图片显示在左边大图
  8. 工作日志2014-06-10(实现C语言解析XML获得查询关键字)
  9. 浅谈卷积神经网络及matlab实现
  10. RTLinux编程总结
  11. oracle修改密码为永久不过期
  12. mac新手使用
  13. ajax 请求被终止 chrome查询发现请求状态status为canceled
  14. 对于Servlet、Servlet容器以及一个Servlet容器-Tomcat
  15. Solidity合约:玉米生产溯源
  16. 发送统计邮件shell脚本
  17. 代码提示级别设置 inspection
  18. python学习笔记——多进程一 基础概念
  19. Hibernate 4.3 SessionFactory
  20. JavaScript里的循环方法之forEach,for-in,for-of

热门文章

  1. hdu 5290 Bombing plan
  2. 2018年9月28日CCPC秦皇岛站参赛总结
  3. django2.0 官方中文文档地址
  4. [百度地图] 用于类似 DWZ UI 框架的 百度地图 功能封装类 [MultiZMap.js] 实例源码
  5. TED_Topic10:The case for engineering our food
  6. HDU 4506 小明系列故事——师兄帮帮忙(二分快速幂)
  7. linux usb枚举过程分析之守护进程及其唤醒【转】
  8. 清理电脑文件夹中的Thumbs.db文件
  9. like语句防止SQL注入
  10. mybatis SQL构造器