No.1492 01 Strings and Inversions
タグ : / 解いたユーザー数 144
作問者 :
penguinman
/ テスター :
kaage
shotoyoo
Problem Statement
Among strings $S$ consisting only of 0 and 1, we define a good string as one that can be made empty by repeating the following operation.
- Choose an $i$ satisfying $S_i=$
0$,\ S_{i+1}=$1$\ (1\leq i\lt|S|)$, and delete $S_i$ and $S_{i+1}$.
How many good strings of length $2N$ have an inversion number of $K$?
Solve this problem for $K=0,\ 1,\ldots,\ N^2$, and output each answer modulo the given prime $M$.
The inversion number of a 01 string $S$ is the number of pairs $(i,\ j)$ $(1\leq i\lt j\leq |S|)$ satisfying $S_i=$1, $S_j=$0.
Input
\(N\) \(M\)
- $1\leq N\leq 100$
- $10^8\leq M\leq 10^9+7$
- $M$ is a prime
- All inputs are integers
Output
Output over $N^2+1$ lines.
On the $i$-th line, output the answer for $K=i-1$ modulo $M$.
Sample
Sample 1
Input
2 998244353
Output
1 1 0 0 0
The good strings of length $2N$ are the $2$ strings 0011 and 0101. Their inversion numbers are $0,\ 1$ respectively, which gives this output.
Sample 2
Input
4 1000000007
Output
1 1 2 3 3 3 1 0 0 0 0 0 0 0 0 0 0
As an aside, the inversion number of a good string of length $2N$ is always at most $N^2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。