Brainstuck | Topcoder Archive

Problem Statement

You've invented a new programming language called Brainstuck. A Brainstuck program consists of a sequence of characters. The allowed characters are +, -, [, and ]. There is a single memory cell. This cell can hold a single integer of arbitrary size. Initially the cellâs value is 0. The Brainstuck interpreter processes each character in sequence using an instruction pointer. At the beginning of the execution of the program, the instruction pointer points to the first character of the program. After processing a character, the instruction pointer moves forward by one character. Each character corresponds to a command:

+ increases the value of the memory cell by 1.
- decreases the value of the memory cell by 1.
[ looks at the value of the memory cell. If it is zero, the instruction pointer moves to the matching ] command.
] looks at the value of the memory cell. If it is non-zero, the instruction pointer moves to the matching [ command.

The [ which matches a ] is decided according to the usual way of matching nested brackets. See the Notes for a formal definition. The program terminates when the instruction pointer moves past the last character.

A Brainstuck program is valid if and only if:

There are no unmatched [ or ] characters.
The execution of the program terminates after a finite number of steps.

Please count the number of valid Brainstuck programs that consist of exactly N characters and return this value modulo M.

Definition

Class:: Brainstuck
Method:: countPrograms
Parameters:: int, int
Returns:: int
Method signature:: int countPrograms(int N, int M)
(be sure your method is public)

Notes

The ] character which matches a [ character at index i in the string s is at the smallest index j such that j > i and s[i..j] contains an equal number of [ and ] characters.

Constraints

N will be between 1 and 100, inclusive.
M will be between 2 and 1,000,000,000, inclusive.

Examples

```
2
```
```
1000000000
```
```
Returns: 5
```
The valid programs are ++, -+, +-, --, []. Note that the execution of the program "[]" consists only of a single step: The instruction pointer points to the [ and the value of the memory cell is zero, so during the execution of this command the interpreter moves the instruction pointer to the matching ]. Then, after the command is executed, the interpreter increments the instruction pointer, which moves it past the last character of the program.
```
3
```
```
1000000000
```
```
Returns: 12
```
The valid programs are: +++ -++ +-+ --+ []+ ++- -+- +-- --- []- [+] [-]
```
5
```
```
1000000000
```
```
Returns: 92
```
```
16
```
```
1000000000
```
```
Returns: 55450070
```
```
13
```
```
163
```
```
Returns: 64
```
```
100
```
```
1000000000
```
```
Returns: 875563034
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.