No.2537 多重含意
タグ : / 解いたユーザー数 47
作問者 : 👑
p-adic
/ テスター :
遭難者
hiro1729
問題文
入力に $2$ 個の正整数 $N, B$ と、$N$ 以下の正整数のみを成分に持つ長さ $N$ の数列 $A$ が与えられます。
$N$ 以下の各正整数 $j$ に対し、$A_j$ で $A$ の $j$ 個目の成分を表します。
ここでは命題変数と言ったら $P$ に正整数の添字をつけた文字列を表します。例えば $P_1$ は命題変数ですが、$P$ や $Q_2$ は命題変数ではありません。
$1 \leq \ell \leq r \leq N$ を満たす各整数 $\ell, r$ に対し、命題 $X_A(\ell,r)$ を次の再帰式で定めます：
$\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. $
ただし $\Rightarrow$ は含意（ならば）を表す論理演算子です。上の再帰式は要するに $\Rightarrow$ を右から結合していくことで新たな命題を構成しています。
例えば $N \geq 4$ の時、$X_A(3,4)$ は命題 $P_{A_3} \Rightarrow P_{A_4}$ であり、$X_A(2,4)$ は $P_{A_2} \Rightarrow X_A(3,4)$ すなわち $P_{A_2} \Rightarrow (P_{A_3} \Rightarrow P_{A_4})$ となります。
$N$ 以下の各正整数 $r$ に対し、次の問題に答えてください：
- $N$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当てであって $X_A(1,r)$ が真となるようなものの総数を $B$ で割った余りを求めてください。
命題変数の真理値割り当てについて知らない人向けの説明はこちらです。（クリックで開く）
$N$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当てとは、大雑把には各正整数 $i$ に対し $P_i$ が真であるか偽であるかを決める対応のことです。
より形式的には $N$ 以下の正整数全体の集合から $\{0,1\}$ への写像のことですが、その定式化に納得できる人はこの補足が不要なので大雑把な説明に留めます。
入力
入力は以下の形式で標準入力から $2$ 行で与えられます：
- $1$ 行目に $N, B$ が半角空白区切りで与えられます。
- $2$ 行目に $A$ の各成分が半角空白区切りで与えられます。
$N$ $B$ $A_1$ $\cdots$ $A_N$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^9$ を満たす整数である。
- $N$ 以下の各正整数 $j$ に対し、$A_j$ は $1 \leq A_j \leq N$ を満たす整数である。
出力
$N$ 以下の各正整数 $r$ に対し、$N$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当てであって $X_A(1,r)$ が真となるようなものの総数を $B$ で割った余りを $r$ 行目に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1
出力
0
$A$ は長さ $N = 1$ の正整数列 $(1)$ です。
$X_A(1,1)$ は $P_{A_1}$ すなわち $P_1$ です。$N = 1$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当ては $P_1$ に真偽のどちらを割り当てるかの $2$ 通りがあり、
- $P_1$ に真を割り当てると、$X_A(1,1)$ は真となります。
- $P_1$ に偽を割り当てると、$X_A(1,1)$ は偽となります。
以上より、$X_A(1,1)$ が真となる真理値割り当ての総数は $1$ となります。$1$ を $B = 1$ で割った余りは $0$ です。
サンプル2
入力
2 2 2 1
出力
0 1
$A$ は長さ $N = 2$ の正整数列 $(2,1)$ です。
まず $X_A(1,1)$ は $P_{A_1}$ すなわち $P_2$ です。$N = 2$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当ては $P_1, P_2$ のそれぞれに真偽のどちらを割り当てるかの $4$ 通りがあり、
- $P_1$ に真を割り当て $P_2$ に真を割り当てると、$X_A(1,1)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に真を割り当てると、$X_A(1,1)$ は真となります。
- $P_1$ に真を割り当て $P_2$ に偽を割り当てると、$X_A(1,1)$ は偽となります。
- $P_1$ に偽を割り当て $P_2$ に偽を割り当てると、$X_A(1,1)$ は偽となります。
以上より、$X_A(1,1)$ が真となる真理値割り当ての総数は $2$ となります。$2$ を $B = 2$ で割った余りは $0$ です。
次に $X_A(1,2)$ は $P_{A_1} \Rightarrow P_{A_2}$ すなわち $P_2 \Rightarrow P_1$ です。$N = 2$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当ては $P_1, P_2$ のそれぞれに真偽のどちらを割り当てるかの $4$ 通りがあり、
- $P_1$ に真を割り当て $P_2$ に真を割り当てると、$X_A(1,2)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に真を割り当てると、$X_A(1,2)$ は偽となります。
- $P_1$ に真を割り当て $P_2$ に偽を割り当てると、$X_A(1,2)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に偽を割り当てると、$X_A(1,2)$ は真となります。
以上より、$X_A(1,2)$ が真となる真理値割り当ての総数は $3$ となります。$3$ を $B = 2$ で割った余りは $1$ です。
サンプル3
入力
2 3 1 1
このように $A_1 = A_2$ となることもあります。
出力
2 1
$A$ は長さ $N = 2$ の正整数列 $(1,1)$ です。
まず $X_A(1,1)$ は $P_{A_1}$ すなわち $P_1$ です。$N = 2$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当ては $P_1, P_2$ のそれぞれに真偽のどちらを割り当てるかの $4$ 通りがあり、
- $P_1$ に真を割り当て $P_2$ に真を割り当てると、$X_A(1,1)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に真を割り当てると、$X_A(1,1)$ は偽となります。
- $P_1$ に真を割り当て $P_2$ に偽を割り当てると、$X_A(1,1)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に偽を割り当てると、$X_A(1,1)$ は偽となります。
以上より、$X_A(1,1)$ が真となる真理値割り当ての総数は $2$ となります。$2$ を $B = 3$ で割った余りは $2$ です。
次に $X_A(1,2)$ は $P_{A_1} \Rightarrow P_{A_2}$ すなわち $P_1 \Rightarrow P_1$ です。$N = 2$ 以下の各正整数 $i$ に対する $P_i$ の真理値割り当ては $P_1, P_2$ のそれぞれに真偽のどちらを割り当てるかの $4$ 通りがあり、
- $P_1$ に真を割り当て $P_2$ に真を割り当てると、$X_A(1,2)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に真を割り当てると、$X_A(1,2)$ は真となります。
- $P_1$ に真を割り当て $P_2$ に偽を割り当てると、$X_A(1,2)$ は真となります。
- $P_1$ に偽を割り当て $P_2$ に偽を割り当てると、$X_A(1,2)$ は真となります。
以上より、$X_A(1,2)$ が真となる真理値割り当ての総数は $4$ となります。$4$ を $B = 3$ で割った余りは $1$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。