# Can't understand INOI problem "Periodic Strings"

See title, here is the problem statement. Specifically I don’t understand what is meant my “Output Format - the number of non-periodic strings of length N , modulo M” bit. Could someone give me an example to explain the output format?

Here is the problem https://www.codechef.com/IOIPRAC/problems/INOI1502

I am also pasting this here in case someone doesn’t want to click the link.

A string is any nonempty sequence of 0s and 1s. Examples of strings are 00, 101, 111000,
1, 0, 01. The length of a string is the number of symbols in it. For example, the length of
111000 is 6. If u and v are strings, then uv is the string obtained by concatenating u and v.
For example if u = 110 and v = 0010 then uv = 1100010.
A string w is periodic if there exists a string v such that w = v
n = vv · · · v (n times),
for some n ≥ 2. Note that in this case the length of v is strictly less than that of w. For
example, 110110 is periodic, because it is vv for v = 110.
Given a positive integer N, find the number of strings of length N which are not periodic.
Report the answer modulo M. The non-periodic strings of length 2 are 10 and 01. The nonperiodic
strings of length 3 are 001, 010, 011, 100, 101, and 110.

Input format:
A single line, with two space-separated integers, N and M.

Output format:
A single integer, the number of non-periodic strings of length N, modulo M.

Test Data

In all subtasks, 2 ≤ M ≤ 108

The testdata is grouped into 4 subtasks.

Subtask 1 (10 marks) 1 ≤ N ≤ 4000. N is the product of two distinct prime numbers.

Subtask 2 (20 marks) 1 ≤ N ≤ 4000. N is a power of a prime number.

Subtask 3 (35 marks) 1 ≤ N ≤ 4000.

Subtask 4 (35 marks) 1 ≤ N ≤ 150000.

Non-Periodic means the strings which cannot be broken down into some recurring sub-string.

Lets take an example with N = 4

All possible periodic strings are:

0000, 0101, 1010, 1111

each with periodic sub-string ‘0’,‘01’,‘10’,‘1’ respectively.

Lets take an example of a non-periodic string 1110. You cannot have a sub-string of it which you can repeat 2 or more times to get original string.

So for N=4 your output should be 12%M. As there are 12 strings of length 4 which are non-periodic

2 Likes

it is impossible this problem. Gave a string from length N there are 2^N possible strings, which I have subtract the periodics one.
But I can’t compute 2^150000. Nobody can do it. There is something wrong. May be the problem requires the periodic one.

Rather than vote down, please explain your point of view. This is math.

Not fully accomplishing. The problems require (2^N - k)%M and not 2^N%M -k . For example N=3 : 2^3 =8 - 2(periodic)=6 Than compute modulo for 6. How can get ride of it?

//