← CSES Better

Periodic Strings

INOI · 2015 · Indian National Olympiad in Informatics · INOI1502

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

strings · number-theory · counting

The organizer’s problem statement is available at the official source link.

periodic word

A periodic word repeats a shorter root

Count binary strings of length N that cannot be formed by repeating a shorter block two or more times, modulo M.

root word length d | Nrepeat rootstring length N
  1. 1

    Count all strings

    There are 2^N binary strings of length N.
  2. 2

    Identify periodic strings

    A periodic string repeats a shorter block whose length divides N. Count such strings without double-counting strings with multiple periods.
  3. 3

    Subtract and reduce

    Subtract the periodic-string count from 2^N, then report the result modulo M.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.