@import url(http://www.shnenglu.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);
Day1 random：
首先基本方法是矩乘……xor可以轉(zhuǎn)化為mod 2意義下的加法操作……
直接矩乘O(N
3logK)，需要優(yōu)化……
由于mod 2，矩陣中所有的元素都是0或1，于是可以壓位，設(shè)壓w位，則時間復(fù)雜度變?yōu)镺(N
3logK/w)……
其實還可以繼續(xù)優(yōu)化。
在mod 2意義下，乘法相當(dāng)于and，加法相當(dāng)于xor……假設(shè)某次待乘的兩個N*N矩陣分別為A和B……
先對A的每一行進(jìn)行分段，每w位一段，然后這一段在進(jìn)行矩乘的時候，實際上是對B的每個w*32的塊，都將該塊對應(yīng)的若干行（這一段值為1的位置對應(yīng)的那些行）取出并整體xor……
因此可以一開始就對B進(jìn)行分塊，每塊大小為w*32，每塊計算出對于每個w位二進(jìn)制數(shù)對應(yīng)行的xor和……
這樣兩個矩陣相乘的總時間就是O(N
3/w/32)了囧……（A中一共N
2/w段，每段在B中乘N/32塊，每段和每塊的相乘結(jié)果可以直接在預(yù)處理記錄的xor和里面調(diào)，是O(1)的）
預(yù)處理時間顯然是O(N
2/w/32*2
w)，w=logN時兩者平衡……
這樣很明顯可以卡過去N=1000，K=10
9的那些點（w取10），N=2000的或許也可以卡過去囧……
Day2 crypto：
N=50的，由于p大，直接隨機(jī)53~58個方程，解方程組，有解的就認(rèn)為是答案囧……
N=60的，基本思想是通過碰撞（兩個方程xor）消去某些未知數(shù)，然后當(dāng)未知數(shù)個數(shù)較小時暴力枚舉驗證……
@fanhq666 在講題的時候，說進(jìn)行兩輪碰撞，第一輪消去第41~60個未知數(shù)，第二輪消去第21~40個，然后暴枚……
優(yōu)化：這樣在兩輪之后其實是對4個方程合并后的結(jié)果，正確率嚴(yán)重降低，可以直接取3個方程碰撞消去40個（也可能>40個，減少枚舉量）未知數(shù)，這樣正確率就木有那么慘不忍睹了囧……
Day2 numbers：
基本方法：手打前若干個數(shù)字，后面的進(jìn)行比對，選那個最像的（其實這樣正確率并不能達(dá)到最高，可以取前10像的，看哪個數(shù)字最多，或者加入其它的一些估價……）
這樣正確率可以達(dá)到約0.9……
為了進(jìn)一步提高正確率，可以找出那些出錯的數(shù)字，看都是將什么判成了什么……
結(jié)果是，4和9、7和9、3和5、某些1和8、某些1和2等易出錯……
因此可以針對這些繼續(xù)優(yōu)化……比如對4和9設(shè)計更精細(xì)的估價函數(shù)，按每列拆分，可以確定上方的開口大小，然后取開口前若干小的為9，其它為4……
（未完待續(xù)）
———————————————————————————————————————————————————
一些感想：
我的OI生涯就這么結(jié)束了……
沒能參加IOI，真的很遺憾……
但是像我這樣的沙茶，除了提交答案和某些亂搞題外幾乎木有任何優(yōu)勢，要是進(jìn)了隊，很明顯是給中國丟臉啊囧……
CTSC的這幾天，我和HN、ZJ的神犇進(jìn)行了充分細(xì)致的交流……畢竟這是大學(xué)前最后一次和他們見面的機(jī)會了……
從這個交流當(dāng)中感受到了很多東西……
首先當(dāng)然是和他們討論各種問題的過程中，他們告訴我的那些新思想和新方法……當(dāng)然在他們的論文中也有體現(xiàn)……
真是太神了……我為什么就一直沒想起來這些呢囧……
還有就是他們在一起討論問題時的熱烈的場景……原來那些新思想都是在這里出現(xiàn)的，只要一人想出來，大家都知道了囧……
想起我平時有多么孤獨……這樣的場景只能在比賽時經(jīng)歷……
眾多神犇在一起，每人都可以從別人那里獲得動力，以及獲得各種有用的資料……
而我這樣的沙茶，本來就很弱，被神犇們鄙視，又木有好的資料來源，自然也缺乏動力了……
這些因素加在一起的效果，就是我進(jìn)步的速度明顯比他們慢，明顯跟不上時代……
回想起從2008年7月以來的這些日子……
前兩年不用說了，學(xué)習(xí)的都是最基礎(chǔ)的東西（這些東西在強(qiáng)省都是幾個月解決的事，而我用了兩年，已經(jīng)明顯落后）……
后面，雖然各位神犇給我提供了一些榜樣作用，但是這種作用效果還是太差……
我仍然需要幾乎完全靠自己的努力來解決那些巨可怕的問題……
當(dāng)2011年LCT、各種分塊開始爛大街的時候，我還在寫線段樹、splay tree的模板……
當(dāng)2012年SAM出現(xiàn)的時候，我還在寫一般的SA……
當(dāng)2013年cdq-gyz分治等各種詭異的思想出現(xiàn)的時候，我還在寫動態(tài)樹的模板……
總是跟不上時代，以至于我相對于其他人變得越來越弱……
用比他們更多的時間，收益卻遠(yuǎn)遠(yuǎn)小于他們……
每一次聽到一道題是ZJ、HN等的資料題、模擬賽題等原題時，就有一種想哭的沖動……
我曾經(jīng)不止一次地想過，假如我生在ZJ或HN，或者小時候轉(zhuǎn)移到了那里……
這幾年的生活會腫么樣呢……現(xiàn)在會是什么樣呢囧……
不用為了需要一篇論文或者一道題，在google、baidu、citeseerx等上面到處找，找了很久無果……
不用在看知識點或題解時，面對無論如何也搞不懂的部分，急得想撞墻，也木有用……
不用為了一道難題的解決折騰幾天，可能幾分鐘討論一下就完事了……
不會在比賽后討論時，別人說到一種很熟悉的方法，自己卻從未想到過也從未聽說過……
不會每天都在痛苦中度過，卻一直跟不上時代，越來越弱……
弱省之所以弱，也就是因為這些原因吧囧……
（聽說AH已經(jīng)連續(xù)6年無國家隊了，各科國家隊都木有……這不奇特，看看AH這環(huán)境，將來要有，只能說那個人太高能了囧……至少現(xiàn)在還木有這么神的人……）
當(dāng)然，我不能改變自己所處的環(huán)境，只能在這種環(huán)境下選擇盡可能優(yōu)的行動……
我希望能有一個更加精彩的人類智慧時代……
cong 國家隊：一出現(xiàn)就能使人嚇傻的鼎爺、xyz大爺；壓位帝+亂搞帝+人類智慧之神 sy菊苣；幾何帝花神。
今年中國隊?wèi)?yīng)該可以延續(xù)輝煌了囧……
Orz @法法塔 @vfleaking @matthew99等神犇