icontofig | 发布于 2019-07-21 20:34:56 | 阅读量 393 | KMP
发布于 2019-07-21 20:34:56 | 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

Sample Input

3
3
ab
ab
4
acd
ca
5
ab
aaa

Sample Output

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

题目大意

给你一个集合Q,里面为可以使用的字符元素,然后给一个串S,求用集合Q中的字符元素组成的长为n的不包含子串S的串有多少个。

题解

说实话一看到n范围到1e9立马就知道应该是个带logn级别的算法。

所以我们怎么想的呢……我们用dp[i][j]表示,当模式串S匹配到第i个字符时,下一个匹配到第j个字符的方案数(此题明显就是方案数啊所以肯定是DP)。

所以我们最终要求的是n次转移以后的Σlens-1i = 0 dp[0][i],因为我们一开始组这个字符的时候是没有匹配到任何一个字符的。

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

但是这个模式串长度好小啊……

我们考虑是否能够用什么优化我们的DP……

这里我们说一下,矩阵非常适合做以下经典题:

给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值
把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要二分求出A^k即可。

这个DP形式和含义也非常像矩阵能做到的事情。

妥了,经典的矩阵快速幂优化!

剩下的就没了QAQ,看代码吧。

代码

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

 


内容更新于: 2019-07-21 20:34:56
链接地址: http://blog.leanote.com/post/icontofig/331a208cabcd

上一篇: Educational Codeforces Round 69 D Yet Another Subarray Problem 思维题

下一篇: Light OJ 1258 Making Huge Palindromes KMP构造回文串

393 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航