ivplay's blog

By ivplay, 11 years ago, In English

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 Output for Sample Input 3 3 ab ab 4 acd ca 5 ab aaa Case 1: 4 Case 2: 55 Case 3: 24 //http://www.lightoj.com/volume_showproblem.php?problem=1268

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
11 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Try to construct all possible strings letter by letter. The only information you should know about already constructed strings is c[i] — number of strings with suffixes of length i equal to first i characters of string S. To add one letter to all strings we can just multiply vector c by some matrix.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You have a mistake in constraints: n <= 10 ^ 9

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n≤109

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yup, sorry , I just copied the entire description and pasted it! anyway thanx for help. I think I am getting close to this problem.