問題一覧 > 通常問題

No.2705 L to R Graph (Another ver.)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 8
作問者 : hirayuu_ychirayuu_yc / テスター : hamamuhamamu MagentorMagentor
1 ProblemId : 10648 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-29 19:31:48

注意

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