第二屆飲料盃解題手冊 Beverage Cup II Solution Manual

F - Walking on a Hypercube

題解

這題最簡單的作法是利用指數型生成函數。

-cube 上面走一步,相當於把一個長度為 的 binary string 其中一個 bit 翻過去(0/1 互換)。因此走過若干步以後要回到原點,必須每一個bit恰好被翻偶數次。因此每一條長度為 的 walk 便一一對應到一條長度為 的 sequence,其每一項都是 的整數,而且每一個數字必須出現偶數次

有多少個這樣的 sequence 呢?利用指數型生成函數,我們會發現,若全部都是 ,那麼長度為 的合法序列數便是

項係數。

若現在考慮所有有 的序列,那麼長度為 的序列,同時有 ,其貢獻的係數是

正巧符合指數型生成函數的乘法條件(本來便適用於組合數)!因此我們會知道答案便是

項係數。

依此類推,若 各出現偶數次,那麼我們所求的答案便是

項係數。

利用二項式定理展開,我們會發現答案便是

剩下就好辦囉!

常數加速

然後更痛苦的地方是要減少取餘數MOD的次數、然後要把快速冪用非遞迴方式撰寫才會快。