No.2705 L to R Graph (Another ver.)
タグ : / 解いたユーザー数 6
作問者 :
hirayuu_yc
/ テスター :
hamamu
Magentor
注意
この問題は F - L to R Graph から派生した問題ですが、F問題とは独立に解くことが可能です。
問題文
以下のような問題を考えます。ただし、L to R Graphとの重要な相違点を赤字で示しています。
$1$ 以上 $N$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ 、$1\leq L\leq R\leq N$ を満たす $L,R$ 、$1\leq S\leq N,1\leq T\leq N,S\ne T$ を満たす $S,T$ が与えられます。
$F(i)=A_i$ とします。また、$F(i)$ を $k$ 回合成したものを $F^k(i)$ とします。
頂点に $1$ から $N$ までの番号が付いた $N$ 頂点 $0$ 辺の有向グラフがあります。このグラフに以下の操作を行います。
- $1 \leq i \leq N,L \leq k \leq R$ について頂点 $i$ から頂点 $F^k(i)$ への辺を張る。
頂点 $S$ から頂点 $T$ に到達できるか判定してください。
$N$ と素数 $P$ が与えられます。入力としてあり得るものは $N^N\times \frac{N(N+1)}{2}\times N(N-1)$ 通りありますが、そのうち、頂点 $S$ から頂点 $T$ に到達できる入力の個数を $P$ で割った余りを求めてください。
入力
$N\ P$
- $2\leq N\leq 10^5$
- $10^8\leq P\leq 10^9$
- $P$ は素数
- 入力はすべて整数
出力
$1$ 行に、答えを出力してください。
サンプル
サンプル1
入力
2 998244353
出力
10
条件を満たす入力は以下の $10$ 個です。
- $A=(2,2),L=1,R=1,S=1,T=2$
- $A=(2,2),L=1,R=2,S=1,T=2$
- $A=(2,2),L=2,R=2,S=1,T=2$
- $A=(2,1),L=1,R=1,S=1,T=2$
- $A=(2,1),L=1,R=2,S=1,T=2$
- $A=(1,1),L=1,R=1,S=2,T=1$
- $A=(1,1),L=1,R=2,S=2,T=1$
- $A=(1,1),L=2,R=2,S=2,T=1$
- $A=(2,1),L=1,R=1,S=2,T=1$
- $A=(2,1),L=1,R=2,S=2,T=1$
たとえば、$A=(1,2),L=1,R=1,S=1,T=2$ や $A=(2,1),L=2,R=2,S=1,T=2$ などは条件を満たしません。
サンプル2
入力
3 924844033
出力
378
サンプル3
入力
12 313883611
出力
211838194
答えを $P$ で割った余りを求めることを忘れないでください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。