总结-数学
數(shù)學(xué)
比較害怕數(shù)學(xué)題, 因為數(shù)學(xué)題一般代碼比較短, 一旦想到正解往往就能AC, 但是我數(shù)學(xué)水平很洼, 知道的東西也比較少. 感覺寫寫暴力拿部分分比較現(xiàn)實. 畢竟不是每個人都能找到正解.
1. 組合數(shù)
- 一般用階乘計算, 需要求逆元. 可以用lucas定理優(yōu)化時間復(fù)雜度.
- 組合類的問題就要考慮組合數(shù)
- 1.?BestCoder-Round#33?第二題是組合數(shù)的題目
- 2.?BZOJ-1005-明明的煩惱?用組合數(shù)階乘公式推導(dǎo)出最后的式子
- 3.?BZOJ-1951-古代豬文-SDOI2010-費馬小定理+歐拉函數(shù)+lucas定理+中國剩余定理?除了組合數(shù)還用到了一堆定理
- 4.?BZOJ-3505-數(shù)三角形-CQOI2014?方格上的整點組合, 正難則反易
2. 歐拉函數(shù)
- 即 < n 和 n 互質(zhì)的數(shù)的個數(shù)
- 當(dāng) n 為質(zhì)數(shù)的時候 φ(n)=n-1
- 有一個定理在求逆元的時候很有用: a^φ(p)≡1(mod p) 當(dāng) p 為質(zhì)數(shù)時a的逆元就是 a^(p-2) mod p.
- 1.?BZOJ-2705-Longge的游戲-SDOI2012-歐拉函數(shù)?數(shù)學(xué)變形是關(guān)鍵
- 2.?BZOJ-1951-古代豬文-SDOI2010-費馬小定理+歐拉函數(shù)+lucas定理+中國剩余定理?逆元的應(yīng)用
- 3.?BZOJ-2190-儀仗隊-SDOI2008-歐拉函數(shù)?往往先從gcd=1入手發(fā)現(xiàn)是歐拉函數(shù)
3. 離散對數(shù)(BSGS算法)
- a^n mod p = b 求 n, 即 log(a, b) (mod p)
- 1.?BZOJ-2242-計算器-SDOI2011-BSGS
- 2.?BZOJ-3122-隨機數(shù)生成器-SDOI2013-BSGS?數(shù)學(xué)變形還是關(guān)鍵, 等比數(shù)列求和會得到分母上的(1-q), 這時最好把等式兩邊同乘(1-q), 而不是計算逆元. 變形結(jié)果不一樣復(fù)雜度就不一樣
4. 容斥原理
- 實現(xiàn)方式只會dfs
- 當(dāng)初學(xué)的很倉促
- 1.?[CODEVS 1301] 任務(wù)分配?dfs實現(xiàn)
- 2.?BZOJ-2440-完全平方數(shù)-中山市選2011-容斥原理-莫比烏斯函數(shù)-二分查找?推導(dǎo)過程是關(guān)鍵. 因為系數(shù)正好和因數(shù)個數(shù)聯(lián)系起來了, 所以用篩法求莫比烏斯函數(shù).
5. 解線性模方程(組)
- 線性模方程就直接乘逆元.
- 方程組用中國剩余定理.
- 1.?BZOJ-1951-古代豬文-SDOI2010-費馬小定理+歐拉函數(shù)+lucas定理+中國剩余定理?真是神題...處理lucas定理不能用于模非質(zhì)數(shù)的情況.
- 2.?BZOJ-2242-計算器-SDOI2011-BSGS?第二問
6. 高斯消元
- 一種是解線性一次方程組. 一種是Xor方程組. 前者O(n^3), 后者接近O(n^2)
- 有時Gauss Joran算法比高斯消元更方便
- 在處理無解和多解的時候我不太明白
- 1.?BZOJ-1923-外星千足蟲-SDOI2010?bitset 的應(yīng)用. 解異或方程組
- 2.?BZOJ-2337-XOR和路徑?求期望. 解異或方程組
- 3.?BZOJ-1013-球形空間產(chǎn)生器sphere?列方程, 化簡解
- 4.?BZOJ-2115-Xor-WC2011?線性基
7. 矩陣乘法
- 這是這里面做題最多的算法了
- 比較有用吧, 主要處理一些死板的而n又很大的遞推式
- O(m^3), 如果發(fā)現(xiàn)是循環(huán)矩陣則可以優(yōu)化到O(m^2). m是矩陣面積, 一般的遞推式子不會超過10吧.
- 1.?[CODEVS 3147] 矩陣乘法 2?挖掘矩陣乘法的性質(zhì)
- 2.?[CODEVS 1281] Xn數(shù)列?比較基本的題目
- 3.?BZOJ-2326-數(shù)學(xué)作業(yè)-HNOI2011-矩陣乘法?分段動態(tài)規(guī)劃
- 4.?BZOJ-1875-HH去散步-SDOI2009-矩陣乘法?圖上的動態(tài)規(guī)劃
- 5.?BZOJ-1009-GT考試-HNOI2008?和KMP算法結(jié)合起來, 用到了失配函數(shù). 細(xì)節(jié)有太多需要注意了.
8. 群論
- 感覺也比較偏數(shù)學(xué)吧
- 圍繞burnside引理和polya定理展開
- [codevs 2926] 黑白瓷磚(2002年安徽省隊選拔賽)?polya定理會用, 注意置換要滿足封閉性
9. 其他
- 數(shù)學(xué)思維
- 1.?BZOJ-2659-算不出的算式?找到幾何意義
- 2.?BZOJ-1053-反素數(shù)ant?搜索
- 3.?BZOJ-幾道比較有趣的題目
- 4.?BZOJ-1192-鬼谷子的錢袋?二進(jìn)制的思想
- 5.?BZOJ-1406-密碼箱-AHOI2007-數(shù)學(xué)?巧妙地變形
- 6.?[vijos P1919] 最有活力的鮮花?求期望
總結(jié): 往往一個變形拯救世界. 做數(shù)學(xué)題就是要開腦洞吧, 敢猜想才更可能找到正解. 猜的方向也很重要.
總結(jié)
