主題

ZeroJudge - d309: Put a banana in your ear! 解題心得

Not In My Back Yard | 2021-04-06 00:00:11 | 巴幣 2 | 人氣 25

題目連結:


題目大意:
給定一正整數 N (N < 2 ^ 31),代表有 N 位外星人。現在要先從 N 位外星人中選出一位隊長以及副隊長,然後再看剩下的 N - 2 位外星人每人要入隊或是不入隊。試問有多少可能的隊伍組合?

因為答案可能會非常大,所以取 1000000007 的餘數後輸出。

注:隊伍一定要有隊長以及副隊長,不一定要有隊員。



範例輸入:
3


範例輸出:
12


解題思維:
可以看到選出隊長以及副隊長的方法數為 N × (N - 1),而剩下的人可選可不選,所以是 2 ^ (N - 2)。

因此所求為 N × (N - 1) × 2 ^ (N - 2)。但是因為 N 值很大,所以在求 2 ^ (N - 2) 時需要用到快速冪的概念。參見這題的中段。而且記得每次運算之後要取餘數,否則容易超出變數儲存範圍。

但是要注意的是當 N = 1 時,因為只選得出隊長或是副隊長(畢竟只有一人),根據題意這個隊伍不成立,所以方法數 = 0。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作