题解 GT考试
2024-10-19 13:45:35
题目大意
给出\(n,m,k\),以及一个长度为\(m\)的数字串\(s_{1,2,...,m}\),求有多少个长度为\(n\)的数字串\(X\)满足\(s\)不出现在其中的个数模\(k\)的答案。
思路
看\(\texttt{command-block}\)的博客看到这道题了,果然还是不会做,看了一下题解,确实自己技不如人。。。
我们可以设\(f[i][j]\)表示考虑到第\(i\)个数,匹配到\(s\)的第\(j\)位的方案数。可以得到一个非常显然的转移式:
\[f[i][j]=\sum_{k=0}^{m-1} f[i][k]g[k][j]
\]
\]
其中\(g[k][j]\)表示\(s\)匹配到第\(k\)位,加一个数字匹配到第\(j\)位的方案数。
不难看出最后的答案就是:
\[\sum_{i=0}^{m-1}f[n][i]
\]
\]
于是,我们的问题就是如何求出\(g\)了。我们发现这个可以\(\texttt{KMP}\)暴艹出来。于是,我们就可以用矩阵加速求出\(f\)了。
时间复杂度为\(\Theta(m^3\log n)\)。
\(\texttt{Code}\)
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 25
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,mod,fail[MAXN];char s[MAXN];
int mul (int a,int b){return a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
struct Matrix{
int val[MAXN][MAXN];
Matrix(){memset (val,0,sizeof (val));}
int* operator [] (int x){return val[x];}
Matrix operator * (const Matrix &p)const{
Matrix New;
for (Int i = 0;i < m;++ i) for (Int k = 0;k < m;++ k) for (Int j = 0;j < m;++ j) New[i][j] = add (New[i][j],mul (val[i][k],p.val[k][j]));
return New;
}
Matrix operator ^ (int b){
Matrix res,a = *this;
for (Int i = 0;i < m;++ i) res[i][i] = 1;
for (;b;b >>= 1,a = a * a) if (b & 1) res = res * a;
return res;
}
}A;
signed main(){
read (n,m,mod),scanf ("%s",s + 1);
for (Int i = 2,j = 0;i <= m;++ i){
while (j && s[j + 1] != s[i]) j = fail[j];
if (s[j + 1] == s[i]) ++ j;
fail[i] = j;
}
for (Int i = 0;i < m;++ i)
for (char c = '0';c <= '9';++ c){
int j = i;
while (j && s[j + 1] != c) j = fail[j];
if (s[j + 1] == c) ++ j;
++ A[i][j];
}
A = A ^ n;int sum = 0;
for (Int i = 0;i < m;++ i) sum = add (sum,A[0][i]);
write (sum),putchar ('\n');
return 0;
}
最新文章
- Android Studio 小提示,新建Activity
- 给Android程序员的六个建议
- Linux FTP服务器搭建与使用
- BZOJ 1076 奖励关
- 支持向量机之Hinge Loss 解释
- Linq语法
- Apache Commons 工具类介绍及简单使用
- Android通过类对象的方式实现JSON数据的解析
- ODBC操作excel
- 【数论】洛谷P1313计算系数
- 微信小程序hidden
- 将String转换为其表示的路径画到屏幕上
- 聊聊Spring Cloud版本的那些事儿
- c语言判断闰年作业
- Go开发之路 -- strings以及strconv的使用
- LOJ#2353 货币兑换
- 如何使用jpegtran 压缩JPG图片
- http mimetype为multipart/x-mixed-replace报文
- 2018.08.19 NOIP模拟 change(简单模拟)
- javac编译单文件、多文件引入jar包、-cp解决无法加载主类问题