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

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

其實(shí)也挺無語的，這次叉姐出的題，H,C。一道銀牌題，一道金牌題?？上菙?shù)學(xué)題。我準(zhǔn)備了那么久dp，那么多數(shù)據(jù)結(jié)構(gòu)，字符串，圖論都沒派上用場。說到底還是被數(shù)學(xué)題給打爛了。還是缺少一點(diǎn)知識面啊。

昨天剛打完，今天人都比較失落吧。。。準(zhǔn)備了這么久，到頭來還是一個(gè)二等?，F(xiàn)在只能不停的安慰自己，人生不是完美的，沒有什么人的一生是一帆風(fēng)順的。現(xiàn)在都不知道怎么去面對接下來的事情了。一下覺得心里落空很多…

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

方法一:

關(guān)鍵點(diǎn):一個(gè)數(shù)是偶數(shù)，則必定存在至少一個(gè)素因子2.

那么考慮到$C(n,m)=\frac{n!}{m!?(n?m)!}$

現(xiàn)在就是求階乘中因子2的個(gè)數(shù)，這個(gè)就是${\sum }_{i=1}^{lo{g}_{i}x}?\frac{x}{2^i}??i$

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

然后根據(jù)組合數(shù)的階乘表示方法，我們可以$O(1)$的判斷分子的因子2的個(gè)數(shù)，以及分母的因子2的個(gè)數(shù).判斷大小關(guān)系即可.

方法二:

結(jié)論：$C(n,k)$,當(dāng)$n\&k=k$時(shí),組合數(shù)是奇數(shù)，否則是偶數(shù).