No.645 Count Permutation
タグ : / 解いたユーザー数 22
作問者 :
Pulmn
/ テスター :
yosupot
問題文
以下の条件を満たす $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。