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