@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³logK)，需要優(yōu)化……
由于mod 2，矩陣中所有的元素都是0或1，于是可以壓位，設(shè)壓w位，則時(shí)間復(fù)雜度變?yōu)镺(N³logK/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……
因此可以一開(kāi)始就對(duì)B進(jìn)行分塊，每塊大小為w*32，每塊計(jì)算出對(duì)于每個(gè)w位二進(jìn)制數(shù)對(duì)應(yīng)行的xor和……
這樣兩個(gè)矩陣相乘的總時(shí)間就是O(N³/w/32)了囧……（A中一共N²/w段，每段在B中乘N/32塊，每段和每塊的相乘結(jié)果可以直接在預(yù)處理記錄的xor和里面調(diào)，是O(1)的）
預(yù)處理時(shí)間顯然是O(N²/w/32*2^w)，w=logN時(shí)兩者平衡……
這樣很明顯可以卡過(guò)去N=1000，K=10⁹的那些點(diǎn)（w取10），N=2000的或許也可以卡過(guò)去囧……

Day2 crypto：
N=50的，由于p大，直接隨機(jī)53~58個(gè)方程，解方程組，有解的就認(rèn)為是答案囧……
N=60的，基本思想是通過(guò)碰撞（兩個(gè)方程xor）消去某些未知數(shù)，然后當(dāng)未知數(shù)個(gè)數(shù)較小時(shí)暴力枚舉驗(yàn)證……
@fanhq666 在講題的時(shí)候，說(shuō)進(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ù)，按每列拆分，可以確定上方的開(kāi)口大小，然后取開(kāi)口前若干小的為9，其它為4……

（未完待續(xù)）
———————————————————————————————————————————————————
一些感想：

我的OI生涯就這么結(jié)束了……
沒(méi)能參加IOI，真的很遺憾……
但是像我這樣的沙茶，除了提交答案和某些亂搞題外幾乎木有任何優(yōu)勢(shì)，要是進(jìn)了隊(duì)，很明顯是給中國(guó)丟臉啊囧……

CTSC的這幾天，我和HN、ZJ的神犇進(jìn)行了充分細(xì)致的交流……畢竟這是大學(xué)前最后一次和他們見(jiàn)面的機(jī)會(huì)了……
從這個(gè)交流當(dāng)中感受到了很多東西……
首先當(dāng)然是和他們討論各種問(wèn)題的過(guò)程中，他們告訴我的那些新思想和新方法……當(dāng)然在他們的論文中也有體現(xiàn)……
真是太神了……我為什么就一直沒(méi)想起來(lái)這些呢囧……
還有就是他們?cè)谝黄鹩懻搯?wèn)題時(shí)的熱烈的場(chǎng)景……原來(lái)那些新思想都是在這里出現(xiàn)的，只要一人想出來(lái)，大家都知道了囧……
想起我平時(shí)有多么孤獨(dú)……這樣的場(chǎng)景只能在比賽時(shí)經(jīng)歷……
眾多神犇在一起，每人都可以從別人那里獲得動(dòng)力，以及獲得各種有用的資料……
而我這樣的沙茶，本來(lái)就很弱，被神犇們鄙視，又木有好的資料來(lái)源，自然也缺乏動(dòng)力了……

這些因素加在一起的效果，就是我進(jìn)步的速度明顯比他們慢，明顯跟不上時(shí)代……
回想起從2008年7月以來(lái)的這些日子……
前兩年不用說(shuō)了，學(xué)習(xí)的都是最基礎(chǔ)的東西（這些東西在強(qiáng)省都是幾個(gè)月解決的事，而我用了兩年，已經(jīng)明顯落后）……
后面，雖然各位神犇給我提供了一些榜樣作用，但是這種作用效果還是太差……
我仍然需要幾乎完全靠自己的努力來(lái)解決那些巨可怕的問(wèn)題……
當(dāng)2011年LCT、各種分塊開(kāi)始爛大街的時(shí)候，我還在寫(xiě)線段樹(shù)、splay tree的模板……
當(dāng)2012年SAM出現(xiàn)的時(shí)候，我還在寫(xiě)一般的SA……
當(dāng)2013年cdq-gyz分治等各種詭異的思想出現(xiàn)的時(shí)候，我還在寫(xiě)動(dòng)態(tài)樹(shù)的模板……
總是跟不上時(shí)代，以至于我相對(duì)于其他人變得越來(lái)越弱……
用比他們更多的時(shí)間，收益卻遠(yuǎn)遠(yuǎn)小于他們……
每一次聽(tīng)到一道題是ZJ、HN等的資料題、模擬賽題等原題時(shí)，就有一種想哭的沖動(dòng)……

我曾經(jīng)不止一次地想過(guò)，假如我生在ZJ或HN，或者小時(shí)候轉(zhuǎn)移到了那里……
這幾年的生活會(huì)腫么樣呢……現(xiàn)在會(huì)是什么樣呢囧……
不用為了需要一篇論文或者一道題，在google、baidu、citeseerx等上面到處找，找了很久無(wú)果……
不用在看知識(shí)點(diǎn)或題解時(shí)，面對(duì)無(wú)論如何也搞不懂的部分，急得想撞墻，也木有用……
不用為了一道難題的解決折騰幾天，可能幾分鐘討論一下就完事了……
不會(huì)在比賽后討論時(shí)，別人說(shuō)到一種很熟悉的方法，自己卻從未想到過(guò)也從未聽(tīng)說(shuō)過(guò)……
不會(huì)每天都在痛苦中度過(guò)，卻一直跟不上時(shí)代，越來(lái)越弱……
弱省之所以弱，也就是因?yàn)檫@些原因吧囧……