题意:求一个长度为n的数字字符串 (n <= 1e9)

   不出现子串s的方案数

题解:用f i,j表示长度为i匹配到在子串j的答案

   用kmp的失配函数预处理一下 然后这个转移每一个都是一样的 所以可以用矩阵加速

#include <bits/stdc++.h>
using namespace std; int n, m, mod;
char s[];
int fail[]; struct node {
int c[][];
}a, re; node mul(node x, node y) {
node res;
memset(res.c, , sizeof(res.c)); for(int i = ; i < m; i++)
for(int j = ; j < m; j++)
for(int k = ; k < m; k++)
res.c[i][j] = (res.c[i][j] + x.c[i][k] * y.c[k][j] % mod) % mod;
return res;
} node pow_mod(node x, int y) {
node res;
memset(res.c, , sizeof(res.c));
for(int i = ; i < m; i++) res.c[i][i] = ; while(y) {
if(y & ) res = mul(res, x);
x = mul(x, x);
y >>= ;
}
return res;
} int main() {
scanf("%d%d%d", &n, &m, &mod);
scanf("%s", s + ); fail[] = fail[] = ;
for(int i = ; i <= m; i++) {
int j = fail[i - ];
while(j && s[i] != s[j + ]) j = fail[j];
fail[i] = s[i] == s[j + ] ? j + : ;
} for(int i = ; i < m; i++) {
for(int j = ; j < ; j++) {
int k = i;
while(k && (s[k + ] - '') != j) k = fail[k];
if(s[k + ] - '' == j) k++;
if(k != m) a.c[i][k] = (a.c[i][k] + ) % mod;
}
} re = pow_mod(a, n);
int ans = ;
for(int i = ; i < m; i++) ans = (ans + re.c[][i]) % mod; printf("%d\n", ans);
return ;
}

最新文章

  1. JS转换HTML转义符
  2. SQL Server安全(9/11):透明数据加密(Transparent Data Encryption)
  3. HDOJ-三部曲一(搜索、数学)-1005-Dungeon Master
  4. phpwind数据同步本地之后板块排版乱
  5. 刘汝佳 算法竞赛-入门经典 第二部分 算法篇 第五章 1(String)
  6. 【leetcode】com/problems/surrounded-regions/
  7. CLOSE-UP FORMALWEAR_意大利进口_2015秋冬_男装发布会_西装图片系列_男装西装设计资料_WeArTrends时尚资讯网_国内最专业的服装设计资讯网站
  8. ActionResult派生类
  9. Tomcat的错误 之 java.lang.IllegalArgumentException: Document base * does not exist
  10. linux笔记2.19
  11. 模块化开发之sea.js实现原理总结
  12. KoaHub.JS用于Node.js的cron作业调度程序代码
  13. C#执行PowserShell 脚本
  14. js前端对后台数据的获取,如果是汉字则需要添上引号
  15. sql统计总和和各状态数
  16. android的Drawable详解
  17. [RESTful] RESTful是什么,为什么要使用它
  18. js刷新小知识点
  19. python的数据结构之数字和字符串(四)
  20. HDU.2516 取石子游戏 (博弈论 斐波那契博弈)

热门文章

  1. css3 display:box 属性
  2. Codeforces Round #269 (Div. 2) A,B,C,D
  3. Lightoj1081【500棵线段树维护】
  4. E. Similarity of Subtrees【hash】
  5. spring boot 使用Schedule创建轻量级定时任务
  6. mysql ERROR 2003 (HY000): Can&#39;t connect to MySQL server on &#39;&#39; (10060
  7. MongoDB 删除数据
  8. 关于maven+springmvc+mybits搭建的框架clean,build后错误:org.apache.ibatis.binding.BindingException的处理
  9. HDU6441(费马大定理)
  10. c#学习系列之静态类,静态构造函数,静态成员,静态方法(总之各种静态)