問題一覧 > 教育的問題

No.2537 Multiple Implication

レベル : / AI推定難易度 : 950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : 👑 p-adic / テスター : 👑 qand hiro1729
お気に入りにしたユーザー ProblemId : 9509 / 自分の提出
問題文最終更新日: 2023-09-27 15:57:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 412 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。