哎，從大一下學期末開始正式打ACM，到現在大三了，今年就A了6題拿了二等，C題真的就是差一點功力，沒想到預處理O(1)判組合數奇偶性，套Lucas定理又超時，然后就因此錯別金，
現在想起來真的是沒辦法，很無力，確實ACM是三個人打的游戲，我們有個天賦很好的選手可惜不喜歡刷題，，，能夠有非常巧妙的靈感，但是到底刷題量不夠還是不行，沒辦法，一個人再怎么努力也是行不通的，
其實也挺無語的，這次叉姐出的題，H,C，一道銀牌題，一道金牌題，可惜全是數學題，我準備了那么久dp，那么多資料結構，字串，圖論都沒派上用場，說到底還是被數學題給打爛了，還是缺少一點知識面啊，
昨天剛打完，今天人都比較失落吧，，，準備了這么久，到頭來還是一個二等，現在只能不停的安慰自己，人生不是完美的，沒有什么人的一生是一帆風順的，現在都不知道怎么去面對接下來的事情了，一下覺得心里落空很多…
哎，上面講的比較亂，現在來講一下如何預處理O(1)的判組合數奇偶性，
方法一:
關鍵點:一個數是偶數，則必定存在至少一個素因子2.
那么考慮到 C ( n , m ) = n ! m ! ? ( n ? m ) ! C(n,m)=\frac{n!}{m!*(n-m)!} C(n,m)=m!?(n?m)!n!?
現在就是求階乘中因子2的個數，這個就是 ∑ i = 1 l o g i x ? x 2 i ? ? i \sum_{i=1}^{log_ix}\lfloor\frac{x}{2^i}\rfloor * i ∑i=1logi?x??2ix???i
所以可以預處理1到1e6的階乘中因數2的個數， O ( n l o g n ) O(nlogn) O(nlogn)
然后根據組合數的階乘表示方法，我們可以 O ( 1 ) O(1) O(1)的判斷分子的因子2的個數，以及分母的因子2的個數.判斷大小關系即可.
方法二:
結論： C ( n , k ) C(n,k) C(n,k),當 n & k = k n \& k = k n&k=k時,組合數是奇數，否則是偶數.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184871.html
標籤：其他
上一篇：關于企業建站有哪些好的方案？