問題一覧 > 通常問題

No.645 Count Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : PulmnPulmn / テスター : yosupotyosupot
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\gt B_{i+1}$ ならば、$B_i$ の値と $B_{i+1}$ の値を入れ替える。

入力

$N$ $L$ $R$

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

出力

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

サンプル

サンプル1
入力
5 2 7
出力
17

$B=\{2,4,1,3,5\}$ として上記の操作を行ってみます。
$i=1$ のとき $B_i \lt B_{i+1}$ なので何もしない。
$i=2$ のとき $B_i \gt B_{i+1}$ なので $B=\{2,1,4,3,5\}$ になる。
$i=3$ のとき $B_i \gt B_{i+1}$ なので $B=\{2,1,3,4,5\}$ になる。
$i=4$ のとき $B_i \lt 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
出力
3628800

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

サンプル3
入力
1000 1000 1000
出力
0

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

サンプル4
入力
100 1000000000 1000000000000000000
出力
2041684

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