icontofig | 发布于 2019-07-21 20:34:56 | 阅读量 393 | KMP

## Description

Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.

One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.

So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring.

## Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 109). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only.

## Output

For each case, print the case number and the total number of names that don't contain S as substring. As the number can be very large, print the number modulo 232

```3
3
ab
ab
4
acd
ca
5
ab
aaa```

## Sample Output

```Case 1: 4
Case 2: 55
Case 3: 24```

## 题解

dp的初始条件和KMP算法的匹配是有关系的。转移方程也好想，但是一看n的范围，瞬间就傻了，1e9的范围O（n）肯定爆炸。

```#include <bits/stdc++.h>
using namespace std;
struct matrix{
int n;
unsigned mat[55][55];
}ans;
matrix mul(matrix a,matrix b){
matrix ret;
memset(ret.mat,0,sizeof(ret.mat));
ret.n = a.n;
for(int i = 0;i < a.n;++i)
for(int j = 0;j < b.n;++j)
for(int k = 0;k < a.n;++k)
ret.mat[i][j] += a.mat[i][k] * b.mat[k][j];
return ret;
}
matrix matrix_quick_pow(matrix a,int b){
matrix ret;
ret.n = a.n;
for(int i = 0;i < ret.n;++i)
for(int j = 0;j < ret.n;++j)
if(i == j)ret.mat[i][j] = 1;
else ret.mat[i][j] = 0;
while(b){
if(b & 1)
ret = mul(ret,a);
a = mul(a,a);
b >>= 1;
}
return ret;
}
const int maxn = 55;
char s[maxn<<3],ss[maxn];
int nxt[maxn];
void KMP_pre(){
int j = 0;
nxt[1] = 0;
for(int i = 2;i <= strlen(ss+1);++i){
while(j && ss[j+1] != ss[i])j = nxt[j];
if(ss[j+1] == ss[i])j++;
nxt[i] = j;
}
return;
}
int T;
int n;
int main(){
scanf("%d",&T);
for(int cas = 1;cas <= T;++cas){
scanf("%d",&n);
getchar();
scanf("%s",s+1);
scanf("%s",ss+1);
int len1 = strlen(s+1);
int len2 = strlen(ss+1);
KMP_pre();
memset(ans.mat,0,sizeof(ans.mat));
ans.n = len2;
for(int i = 0;i < len2;++i){
for(int j = 1;j <= len1;++j){
int t = i;
while(t && s[j] != ss[t+1])t = nxt[t];
if(s[j] == ss[t+1])t++;
ans.mat[i][t]++;
}
}
ans = matrix_quick_pow(ans,n);
unsigned res = 0;
for(int i = 0;i < len2;++i)
res += ans.mat[0][i];
printf("Case %d: %u\n",cas,res);
}
return 0;
}```

393 人读过

0 条评论