b079: 直線排列與環狀排列
Tags : Binary Exponentiation matrix multiplication 快速冪
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-15 21:01

Content

 有 $n$ 個數, $1$~$n$,

每個數可以選擇留於原處或是跟隔壁的交換,每個數最多可以換一次

 

 

依順序排成一列,其方法數叫 $a_n$

例如 $n=4$ 時有

$1234$ $2134$ $1324$ $1243$ $2143$

共 $5$ 種排法

 

依順序排成一環,也就是 $1$ 跟 $n$ 也相鄰,其方法數叫 $b_n$

Input

$n$

$n ≤ 10^{15}$

Output

第一行輸出 $a_n$

第二行輸出 $b_n$

因為答案會很大,所以請輸出答案除以 $10^9+7$ 的餘數

Sample Input #1
4
Sample Output #1
5
7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (6%): 1.0s , <1K
公開 測資點#15 (6%): 1.0s , <1K
公開 測資點#16 (6%): 1.0s , <1K
公開 測資點#17 (6%): 1.0s , <1K
公開 測資點#18 (6%): 1.0s , <1K
Hint :
Tags:
Binary Exponentiation matrix multiplication 快速冪
出處:
臺中一中電腦資訊研習社 [管理者:
Ching367436 (Ching367436)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」