PSFWORDS - Prefix Square Free Words
A string is called a square string if it can be obtained by concatenating two copies of the same string (i.e. $s=uu$ for some word $u$). For example, "abab", "aa" are square strings, while "aaa", "abba" are not. A string is called prefix-square free if none of its prefixes is a square.
Chiaki would like to know the number of nonempty prefix-square free strings whose length is less than or equal to $n$. The size of the alphabet Chiaki uses is $m$. As this number may be very large, Chiaki is only interested in its remainder modulo $2^{32}$.
Input
There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 100$), indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $m$ ($1 \le n \le 100, 1 \le m \le 10^9$) -- the length of the string and the size of the alphabet.
Output
For each test case, output an integer denoting the answer.
Example
Input:
2 3 2 4 6
Output:
8 1266
Information
There are $5$ input files:
- Input #1: $1 \le T \le 100, 1 \le n \le 10$.
- Input #2: $1 \le T \le 50, 1 \le n \le 30$.
- Input #3: $1 \le T \le 30, 1 \le n \le 60$.
- Input #4: $1 \le T \le 10, 1 \le n \le 80$.
- Input #5: $1 \le T \le 2, 1 \le n \le 100$.
hide comments
:D:
2022-03-19 23:30:05
@subhashs "aaa" and "bbb" are not square strings, but they also not "prefix square free" and that's what we are counting in this problem. |
|
subhashs:
2019-03-20 09:47:24
@zimpha: Quoting from problem statement "For example, "abab", "aa" are square strings, while "aaa", "abba" are not." Then why are "aaa" "bbb" not in the 8 strings you have mentioned for the first test case? Not sure i understand the problem. |
|
zimpha:
2018-01-06 04:16:33
@Shubhojeet Chakraborty For the first test case, there 8 strings: a, b, ab, ba, aba, abb, baa, bab. |
|
Shubhojeet Chakraborty:
2018-01-05 06:48:06
Can someone explain the given test cases.thanks. |
|
zimpha:
2018-01-04 13:03:43
@Min_25 thx, fixed. |
|
Min_25:
2018-01-04 09:15:19
Not "the number of prefix-square free strings of length n", but "the number of prefix-square free strings of length <= n" ? |
Added by: | zimpha |
Date: | 2018-01-02 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |