When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Secret.Codes's blog

By Secret.Codes, history, 7 years ago, In English

1268 — Unlucky Strings PDF (English) Statistics Forum Time Limit: 2 second(s) Memory Limit: 32 MB

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

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

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

As far as I can see... Here first check whether S can be constructed from the given permitted characters... now two cases arises. Case 1: Cannot be formed. Then the solution is pretty simple. its ((num of char allowed)^n)%MOD Case 2: Can be formed. Then We need to apply inclusion exclusion.