NPSC 魔法學院在今年正式成立囉!
從小就展現過人天賦的天才兒童殿壬,如今已成長茁壯並成為NPSC 魔法學院第一屆的學員了。一年級的課程對於殿壬來講根本就是小菜一碟,所以他跟著學院裡的教授一起衝鋒陷陣,研究最新穎的魔法技術:魔法鏈。
施展這種法術前,殿壬要先擁有一串由魔法寶石組成的魔力串珠。一串魔力串珠會由
這項法術的施展,就是利用這串魔力串珠來製造一條魔法鏈。
製造魔法鏈時,若這串魔力串珠只有2 顆魔法寶石,就直接用魔力剪刀剪斷中間唯一的那條線,並且把這2 顆魔法寶石依任意順序放在魔法鏈的第1 跟第2 個位置。
否則,殿壬要挑選魔力串珠中的一條線並用魔力剪刀把它剪斷,使得在剪斷之後會形成一串有多顆魔法寶石的魔力串珠以及一顆獨立的魔法寶石(如果剪斷後不會變成這種結果,那麼殿壬就不能剪這條線),接著把這獨立的魔法寶石放在魔法鏈的下一個位置(剪第一刀時得到的魔法寶石放在第一個位置、剪第二刀時得到的魔法寶石放在第二個位置,依此類推),重複上述動作直到這串魔力串珠只剩下兩顆魔法寶石(中間由一條線連接著)時,殿壬就把最後這條線剪斷,並依他的選擇將最後的兩顆魔法寶石放在魔法鏈的第
現在給你一串魔法串珠,請你計算總共可以創造出多少種不同的魔法鏈。兩個魔法鏈只要任一個對應的位置不相等,就視為不同。因為答案可能很大,你的程式只需要輸出答案除以
測試資料第一行包含一個正整數
料接下來包含
輸出一行,包含一個整數,表示該魔法串珠所能創造出的魔法鏈種類數除以
2017 NPSC高中組決賽
No. | Testdata Range | Score |
---|---|---|
1 | 0~97 | 100 |