F - Walking on a Hypercube

題解

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

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

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

$\displaystyle\frac{1}{2}(e^x + e^{-x})$

的 $x^L$ 項係數。

若現在考慮所有有 $1$ 和 $2$ 的序列，那麼長度為 $L$ 的序列，同時有 $2k$ 個 $1$ 和 $L-2k$ 個 $2$，其貢獻的係數是

$\frac{L!}{(2k)!(L-2k)!}$

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

$\displaystyle\frac{1}{2^2}(e^x + e^{-x})^2$

的 $x^L$ 項係數。

依此類推，若 $1$ 到 $n$ 各出現偶數次，那麼我們所求的答案便是

$\displaystyle\frac{1}{2^n}(e^x + e^{-x})^n$

的 $x^L$ 項係數。

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

$\displaystyle\frac{1}{2^n}\sum_{k=0}^n (n-2k)^L$

剩下就好辦囉！

常數加速

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