2020HNCPC賽後總結

哎，從大一下學期末開始正式打ACM，到現在大三了。今年就A了6題拿了二等。C題真的就是差一點功力。沒想到預處理O(1)判組合數奇偶性，套Lucas定理又超時。然後就因此錯別金。

現在想起來真的是沒辦法。很無力。確實ACM是三個人打的遊戲，我們有個天賦很好的選手可惜不喜歡刷題。。。能夠有非常巧妙的靈感。但是到底刷題量不夠還是不行。沒辦法，一個人再怎麼努力也是行不通的。

其實也挺無語的，這次叉姐出的題，H,C。一道銀牌題，一道金牌題。可惜全是數學題。我準備了那麼久dp，那麼多資料結構，字串，圖論都沒派上用場。說到底還是被數學題給打爛了。還是缺少一點知識面啊。

昨天剛打完，今天人都比較失落吧。。。準備了這麼久，到頭來還是一個二等。現在只能不停的安慰自己，人生不是完美的，沒有什麼人的一生是一帆風順的。現在都不知道怎麼去面對接下來的事情了。一下覺得心裡落空很多…

哎，上面講的比較亂，現在來講一下如何預處理O(1)的判組合數奇偶性。

方法一:

關鍵點:一個數是偶數，則必定存在至少一個素因子2.

那麼考慮到$C(n,m)=\frac{n!}{m!\ast (n-m)!}$

現在就是求階乘中因子2的個數，這個就是${\sum }_{i=1}^{lo{g}_{i}x}\lfloor \frac{x}{2^i}\rfloor \ast i$

所以可以預處理1到1e6的階乘中因數2的個數。 $O(nlogn)$

然後根據組合數的階乘表示方法，我們可以$O(1)$的判斷分子的因子2的個數，以及分母的因子2的個數.判斷大小關係即可.

方法二:

結論：$C(n,k)$,當$n\&k=k$時,組合數是奇數，否則是偶數.