BZOJ1009: [HNOI2008]GT考试 (矩阵快速幂 + DP)
2024-10-20 13:30:04
题意:求一个长度为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 ;
}
最新文章
- JS转换HTML转义符
- SQL Server安全(9/11):透明数据加密(Transparent Data Encryption)
- HDOJ-三部曲一(搜索、数学)-1005-Dungeon Master
- phpwind数据同步本地之后板块排版乱
- 刘汝佳 算法竞赛-入门经典 第二部分 算法篇 第五章 1(String)
- 【leetcode】com/problems/surrounded-regions/
- CLOSE-UP FORMALWEAR_意大利进口_2015秋冬_男装发布会_西装图片系列_男装西装设计资料_WeArTrends时尚资讯网_国内最专业的服装设计资讯网站
- ActionResult派生类
- Tomcat的错误 之 java.lang.IllegalArgumentException: Document base * does not exist
- linux笔记2.19
- 模块化开发之sea.js实现原理总结
- KoaHub.JS用于Node.js的cron作业调度程序代码
- C#执行PowserShell 脚本
- js前端对后台数据的获取,如果是汉字则需要添上引号
- sql统计总和和各状态数
- android的Drawable详解
- [RESTful] RESTful是什么,为什么要使用它
- js刷新小知识点
- python的数据结构之数字和字符串(四)
- HDU.2516 取石子游戏 (博弈论 斐波那契博弈)
热门文章
- css3 display:box 属性
- Codeforces Round #269 (Div. 2) A,B,C,D
- Lightoj1081【500棵线段树维护】
- E. Similarity of Subtrees【hash】
- spring boot 使用Schedule创建轻量级定时任务
- mysql ERROR 2003 (HY000): Can&#39;t connect to MySQL server on &#39;&#39; (10060
- MongoDB 删除数据
- 关于maven+springmvc+mybits搭建的框架clean,build后错误:org.apache.ibatis.binding.BindingException的处理
- HDU6441(费马大定理)
- c#学习系列之静态类,静态构造函数,静态成员,静态方法(总之各种静态)