問題一覧 > 通常問題

No.1261 数字集め

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 19
作問者 : PCTprobabilityPCTprobability / テスター : magstamagsta
0 ProblemId : 5136 / 出題時の順位表
問題文最終更新日: 2020-10-18 14:25:53

制限実行時間について

チャレンジケースの追加により、制限実行時間が厳しくなってしまったため $8000ms$ に変更いたしました。申し訳ありません。

問題文

ある正整数 $N$ が与えられます。

$1$ から $N$ の番号がついた町があり、PCT君は町 $1$ から 町 $N$ を目指すゲームを行います。 経由する街の数は、町 $1$ と町 $N$ を除いてちょうど $2$ 個になるようにします。

PCT君は、以下の (操作) をゲームが終了するまで行い続けます。


(操作)

PCT君が町 $1$ にいる時 : 町 $1$ 以外の任意の町に移動できます。

PCT君が町 $1$ 以外にいる時 (現在いる町を町 $i$ とします) : その町にあるガチャを回します。 町 $i$ にあるガチャは $1$ 以上 $A_i$ 以下の整数が出てきます。 この時、$1$ 以外の数が出てきた場合はどこの町へも移動しません。 また、$1$ が出てきた場合は、$i \neq j$ を満たす $j$ が $i$ の倍数である町 $j$ へと移動することができます。 ただし、移動する町が無くなったときは、このゲームを終了します。


最終的に、PCT君がゲームが終了するまでに回したガチャの回数はちょうど $M$ 回でした。また、ゲームが終了した時町 $N$ にいました。

この時、考えられうるガチャで出た数字を順番に並べて出来る数列と町の移動の仕方の組としてあり得るものの個数を $1000000007$ で割った余りを出力してください。


またさらに、クエリを $Q$ 個追加します。内容は以下の通りです。

$Query: $ $X \ \ Y$ $(X < Y)$ : 町 $X$ から町 $Y$ へ移動可能にします。この移動可能とはガチャで $1$ が出た時に本来倍数の町に移動が可能ですが、町 $X$ から町 $Y$ も移動可能にするということであり、ガチャで $1$ が出なくても移動できるというわけではありません。ただし、クエリが与えられた段階では町 $X$ から町 $Y$ に直接移動することは出来ないことが保証されます。(21:56 $X \le Y$ を $X < Y$ に修正しました。)

ここで町 $X$ から町 $Y$ へ移動が出来ないということは $Y$ が $X$ の倍数でなく、かつ今までのクエリに同一の $(X,Y)$ がないということです。

クエリが追加される度に、考えられうるガチャで出た数字を順番に並べて出来る数列と町の移動の仕方の組としてあり得るものの個数を $1000000007$ で割った余りを出力してください。


(補足) 「考えられうるガチャで出た数字を順番に並べて出来る数列と町の移動の仕方の組」は、$i (1 \leqq i \leqq M)$ 回目のガチャで出た数字が異なる時、また、1個目または2個目の経由する町が異なる時、別の組として考えます。

入力

$N$ $M$
$A_2\ A_3\ \dots\ A_N$
$Q$
$Query1$
$Query2$
...
$QueryQ$
それぞれのクエリは以下の形式で与えられます。
$X$ $Y$

  • 入力は全て整数である。
  • $2 \le N \le 10^6$
  • $3 \le M \le 10^6$
  • $2 \le A_i \le 10^6$
  • $i \neq j $であれば$A_i \neq A_j$
  • $0 \le Q \le 10^4$
  • $2 \le X < Y \le N$
  • 各クエリが与えられたとき町 $X$ から町 $Y$ へは直接移動出来ない。
最後から $2$ 番目の制約を $1$ 以上から $2$ 以上に変更しました。(22:14追記)

出力

出力は $Q+1$ 行に渡ります。$i$ 行目には $i-1$ 個目までのクエリが追加された状況での答えを出力してください。ただし $0$ 個目とはクエリが追加されていない状況のことを指します。

サンプル

サンプル1
入力
8 4
2 3 4 5 6 7 8
2
3 8
2 3
出力
11
11
21

  • 初めの状態でのルートは町 $1→2→4→8$ しかなく、あり得る数列としては $1,3,1,1$ など $11$ 通りがあります。
  • $1$ 個目のクエリが追加された時、町 $3$ と町 $8$ を直接移動出来るようになりますが、これで増えるルートはありません。
  • $2$ 個目のクエリが追加された時、町 $2$ と町 $3$ を直接移動出来るようになることで、新しいルート町 $1→2→3→8$ と移動出来るようになり、この場合の増える数列は $1,1,6,1$ などの $10$ 通りです。なので $11+10=21$ を出力します。

サンプル2
入力
5 4
10 100 1000 10000
0
出力
0

移動することが不可能な場合やクエリが $1$ 個もないようなこともあります。

サンプル3
入力
8 1000000
2 3 4 5 6 7 8
0
出力
26342024

この場合PCT君はとても運が悪いです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。