No.645 Count Permutation

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.645 Count Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 :

Pulmn / テスター :

yosupot

2 ProblemId : 1864 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2018-02-02 20:59:59

問題文

以下の条件を満たす $(1, 2, \dots, N)$ の順列 $A$ の通り数を求めてください。ただし、この値は非常に大きくなる場合があるので $1,000,000,007$ で割った時の余りを出力してください。

条件： $f (B) = A$ を満たす $(1, 2, \dots, N)$ の順列 $B$ の通り数が $L$ 以上 $R$ 以下になる。ただし、 $f (B)$ は $B$ に次の操作を行った順列とします。

操作： $i = 1, 2, \dots, N - 1$ という順番で $B_{i} > B_{i + 1}$ ならば、 $B_{i}$ の値と $B_{i + 1}$ の値を入れ替える。

入力

 $N$   $L$   $R$

$2 \leq N \leq 10^{5}, 0 \leq L \leq R \leq 10^{18}$

出力

条件を満たす順列 $A$ の通り数を $1,000,000,007$ で割った時の余りを出力してください。最後に改行してください。

サンプル

サンプル1

入力

5 2 7

出力

$B = {2, 4, 1, 3, 5}$ として上記の操作を行ってみます。
$i = 1$ のとき $B_{i} < B_{i + 1}$ なので何もしない。
$i = 2$ のとき $B_{i} > B_{i + 1}$ なので $B = {2, 1, 4, 3, 5}$ になる。
$i = 3$ のとき $B_{i} > B_{i + 1}$ なので $B = {2, 1, 3, 4, 5}$ になる。
$i = 4$ のとき $B_{i} < B_{i + 1}$ なので何もしない。
したがって、 $f ({2, 4, 1, 3, 5}) = {2, 1, 3, 4, 5}$ になります。
また、条件を満たす順列 $A$ として、 $A = {3, 4, 2, 1, 5}, {4, 2, 3, 1, 5}$ などがあります。

サンプル2

入力

10 0 3628800

出力

$10! = 3628800$ なので、条件を満たす順列 $A$ は $(1, 2, \dots, 10)$ の順列全てです。

サンプル3

入力

1000 1000 1000

出力

出力する値が $0$ の場合もあります。

サンプル4

入力

100 1000000000 1000000000000000000

出力

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

yukicoder

No.645 Count Permutation

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力