No.2537 Multiple Implication
Problem Statement
You are given $2$ positive integers $N, B$ and a sequence $A$ of length $N$ whose elements are all positive integers not exceeding $N$.
For each positive integer $j$ not exceeding $N$, $A_j$ denotes the $j$-th element of $A$.
Here, a propositional variable means a string consisting of $P$ with a positive integer subscript. For example, $P_1$ is a propositional variable, but $P$ and $Q_2$ are not.
For each pair of integers $\ell, r$ satisfying $1 \leq \ell \leq r \leq N$, define the proposition $X_A(\ell,r)$ by the following recurrence:
$\displaystyle X_A(\ell,r) = \left\{ \begin{array}{ll} \displaystyle P_{A_{\ell}} &\displaystyle (\ell = r) \\ \displaystyle P_{A_{\ell}} \Rightarrow X_A(\ell+1,r) &\displaystyle (\ell < r) \end{array} \right. $
Here, $\Rightarrow$ is the logical operator representing implication (if ... then ...). In short, the recurrence above constructs a new proposition by combining with $\Rightarrow$ from the right.
For example, when $N \geq 4$, $X_A(3,4)$ is the proposition $P_{A_3} \Rightarrow P_{A_4}$, and $X_A(2,4)$ is $P_{A_2} \Rightarrow X_A(3,4)$, that is, $P_{A_2} \Rightarrow (P_{A_3} \Rightarrow P_{A_4})$.
For each positive integer $r$ not exceeding $N$, answer the following problem:
- Find the number, modulo $B$, of truth assignments of $P_i$ for each positive integer $i$ not exceeding $N$ such that $X_A(1,r)$ is true.
Here is an explanation for those unfamiliar with truth assignments of propositional variables. (Click to expand)
A truth assignment of $P_i$ for each positive integer $i$ not exceeding $N$ is, roughly speaking, a correspondence that determines, for each positive integer $i$, whether $P_i$ is true or false.
More formally, it is a map from the set of all positive integers not exceeding $N$ to $\{0,1\}$, but anyone comfortable with that formulation does not need this note, so we keep to the rough explanation.
Input
The input is given from standard input in $2$ lines in the following format:
- The $1$st line contains $N, B$ separated by a single-byte space.
- The $2$nd line contains the elements of $A$ separated by single-byte spaces.
$N$ $B$ $A_1$ $\cdots$ $A_N$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$.
- $B$ is an integer satisfying $1 \leq B \leq 10^9$.
- For each positive integer $j$ not exceeding $N$, $A_j$ is an integer satisfying $1 \leq A_j \leq N$.
Output
For each positive integer $r$ not exceeding $N$, output on the $r$-th line the number, modulo $B$, of truth assignments of $P_i$ for each positive integer $i$ not exceeding $N$ such that $X_A(1,r)$ is true.
Print a newline at the end.
Sample
Sample 1
Input
1 1 1
Output
0
$A$ is the sequence of positive integers $(1)$ of length $N = 1$.
$X_A(1,1)$ is $P_{A_1}$, that is, $P_1$. There are $2$ truth assignments of $P_i$ for each positive integer $i$ not exceeding $N = 1$, depending on whether $P_1$ is assigned true or false:
- If $P_1$ is assigned true, $X_A(1,1)$ is true.
- If $P_1$ is assigned false, $X_A(1,1)$ is false.
Therefore, the number of truth assignments such that $X_A(1,1)$ is true is $1$. The remainder when $1$ is divided by $B = 1$ is $0$.
Sample 2
Input
2 2 2 1
Output
0 1
$A$ is the sequence of positive integers $(2,1)$ of length $N = 2$.
First, $X_A(1,1)$ is $P_{A_1}$, that is, $P_2$. There are $4$ truth assignments of $P_i$ for each positive integer $i$ not exceeding $N = 2$, depending on whether each of $P_1, P_2$ is assigned true or false:
- If $P_1$ is assigned true and $P_2$ is assigned true, $X_A(1,1)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned true, $X_A(1,1)$ is true.
- If $P_1$ is assigned true and $P_2$ is assigned false, $X_A(1,1)$ is false.
- If $P_1$ is assigned false and $P_2$ is assigned false, $X_A(1,1)$ is false.
Therefore, the number of truth assignments such that $X_A(1,1)$ is true is $2$. The remainder when $2$ is divided by $B = 2$ is $0$.
Next, $X_A(1,2)$ is $P_{A_1} \Rightarrow P_{A_2}$, that is, $P_2 \Rightarrow P_1$. There are $4$ truth assignments of $P_i$ for each positive integer $i$ not exceeding $N = 2$, depending on whether each of $P_1, P_2$ is assigned true or false:
- If $P_1$ is assigned true and $P_2$ is assigned true, $X_A(1,2)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned true, $X_A(1,2)$ is false.
- If $P_1$ is assigned true and $P_2$ is assigned false, $X_A(1,2)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned false, $X_A(1,2)$ is true.
Therefore, the number of truth assignments such that $X_A(1,2)$ is true is $3$. The remainder when $3$ is divided by $B = 2$ is $1$.
Sample 3
Input
2 3 1 1
As shown here, $A_1 = A_2$ may hold.
Output
2 1
$A$ is the sequence of positive integers $(1,1)$ of length $N = 2$.
First, $X_A(1,1)$ is $P_{A_1}$, that is, $P_1$. There are $4$ truth assignments of $P_i$ for each positive integer $i$ not exceeding $N = 2$, depending on whether each of $P_1, P_2$ is assigned true or false:
- If $P_1$ is assigned true and $P_2$ is assigned true, $X_A(1,1)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned true, $X_A(1,1)$ is false.
- If $P_1$ is assigned true and $P_2$ is assigned false, $X_A(1,1)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned false, $X_A(1,1)$ is false.
Therefore, the number of truth assignments such that $X_A(1,1)$ is true is $2$. The remainder when $2$ is divided by $B = 3$ is $2$.
Next, $X_A(1,2)$ is $P_{A_1} \Rightarrow P_{A_2}$, that is, $P_1 \Rightarrow P_1$. There are $4$ truth assignments of $P_i$ for each positive integer $i$ not exceeding $N = 2$, depending on whether each of $P_1, P_2$ is assigned true or false:
- If $P_1$ is assigned true and $P_2$ is assigned true, $X_A(1,2)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned true, $X_A(1,2)$ is true.
- If $P_1$ is assigned true and $P_2$ is assigned false, $X_A(1,2)$ is true.
- If $P_1$ is assigned false and $P_2$ is assigned false, $X_A(1,2)$ is true.
Therefore, the number of truth assignments such that $X_A(1,2)$ is true is $4$. The remainder when $4$ is divided by $B = 3$ is $1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。