hagu's blog

LightOJ 1268 — Unlucky Strings

By hagu, 10 years ago, In English

I tried this problem using KMP and Matrix exponentiation, but got an WA and i'm unable to find the cases on which my solution fails.

This is the problem Link :- http://lightoj.com/volume_showproblem.php?problem=1268

In short this problem asks you to find out how many strings you can generate of length N that doesn't contain a given string(suppose the string be called "pat") as substring. The allowed characters are also given to you in the form of another string. 1 <= N <= 10^9 and 1 <= length(pat) <= 50.

My approach to the problem is to generate a matrix ans[length(pat)-1][length(pat)-1] in which each entry (i,j) corresponds to number of strings of length N generated if before the start of the string the pie value (pie value as in KMP algo which denotes the longest prefix which is also a suffix) was "i" and after the end of the string the pie value is "j". So by counting the entries in the table ans[0][k] where 0 <= k < length(pat) we can get the final answer.

Now to get the matrix ans we can use matrix exponentiation. we can determine value for each entry (i,j) if N = 1 using KMP and then apply matrix exponentiation to generate final matrix for given N.

This is my solution and it's giving WA http://ideone.com/3PTR9S

Please tell if i'm missing something or if there's a bug in my code . Thanks.

Note :- This problem requires you to compute the answer modulo 2^32.

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

(not an answer, just some nitpicking)

Since the statement asks to:

compute the answer modulo 2^32.

then there is no reason to use % operator at all. Just use unsigned int type (which is formed by 32 bits) and let it overflow. It will be automatically modulo 232.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    Great info, will remember to use it the next time :) Thanks

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

    thanks this trick got me ac. was getting tle using mod

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Actually you dont need kmp at all. Because limits are too small.

Take a look at this. It might help you to find your bug.

→ Reply