CCO '13 P6 - Repetitivity

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 4.5s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2013 Stage 2, Day 2, Problem 3

Any string of length n has 2^n subsequences, which are the strings obtained by deleting some subset of the characters. But these subsequences may not all be distinct. For example, the string zoo has only 6 distinct subsequences:

  • the subsequences z, oo, and zoo appear only once,
  • the empty subsequence appears only once,
  • and the subsequences o and zo each appear twice.

Suppose a string S has k distinct subsequences, and that the i-th one appears f_i times. Then the repetitivity of S is defined as \displaystyle\sum_{i=1}^k f_i^2

For example, the repetivity of zoo is

\displaystyle  1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12

Input Specification

Each test case contains a line containing the string S (with length at most 10\,000), followed by a line containing a single integer M (2 \le M \le 10^9). You may assume that S only contains characters with ASCII codes between 33 and 126 inclusive (these are all printable, non-whitespace characters).

For test cases worth 20\% of the points, you may assume that S will be at most 20 characters long.

Output Specification

The output should consist of a single line, containing the repetitivity of S, modulo M.

Sample Input 1

zoo
10

Output for Sample Input 1

2

Sample Input 2

@#$%
1000000

Output for Sample Input 2

16

Comments


  • -1
    zys5945  commented on May 6, 2016, 3:33 p.m.

    Is it a special privilage for Java?


  • 1
    fifiman  commented on March 4, 2015, 7:47 p.m.

    whoever wrote up this problem forgot to define M, the original version states: "The output should consist of a single line, containing the repetitivity of S, modulo M"