題目連結：d541: “∧”形排列
題目大意：給定Ｎ（Ｎ ≦ ２０００００００００），求出１～Ｎ的正整數的排列數裡面，符合先遞增再遞減（１２５４３這種）或是只遞增、遞減的方法數（取１２３４５６７的餘數）。
解題思維：
先觀察Ｎ＝２，有１２、２１，２種；Ｎ＝３，有１２３、２３１、１３２、３２１，這４種方式；再來，Ｎ＝４，有１２３４、２３４１、１３４２、１２４３、３４２１、２４３１、１４３２、４３２１，這８種。
因此，猜測所求方法數為２ ^ （Ｎ－１）種（Ｎ＝０設為０種）。而這個猜測為「真」的緣由是因為一個排列組合的基本性質。
觀察Ｎ＝３的方法，可以發現其架構等同於以下：從１～２取０個數放到３的後面（１２３）＋１～２取１個數放到３的後面（２３１及１３２）＋１～２取２放到３後面（３２１）。也就是總方法數為Ｃ２取０＋Ｃ２取１＋Ｃ２取２＝４＝２ ^ ２。
同理，Ｎ＝４時為Ｃ３取０＋Ｃ３取１＋Ｃ３取２＋Ｃ３取３＝８＝２ ^ ３。
因為巴斯卡三角形與（Ｘ＋１）^ Ｎ的係數有著密切關係，所以當Ｘ＝１時，巴斯卡三角形的第Ｎ列的數之和正是２ ^ Ｎ。而這剛好也是我們題目的所求。
但是由於題目給定的Ｎ可以到２０億，所以需要快速冪來幫忙加速。快速冪：參見之前的文章的大概中後的段落。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大們可以提出來討論。
達人
