WinniethePooh解題報告中山一中齊小熊很喜歡蜂蜜。但是大千世界上有很多種蜂蜜。吃一罐蜂蜜需要應(yīng)付下面一些事件：一、發(fā)現(xiàn)新蜂蜜！姑且暫時給它一個。所有種類蜂蜜按出現(xiàn)時間依次1，2，…二、說，說他吃A1罐第1類的蜂蜜，吃A2罐第二類的蜂蜜，…，吃Ak罐第k類的蜂蜜（假設(shè)現(xiàn)在知道的蜂蜜有k種吧），要從星期S到星期E…三、計劃吃A1罐第1類的蜂蜜，吃A2罐第二類的蜂蜜，…，吃Ak罐k類的蜂蜜，現(xiàn)在是星期SAddLearnA0A1A2AkSE，EatA0A1A2AkS對每個Eat詢問輸出一行，表示要吃到星期幾。如果不確定則輸出know，如果前面說的話已經(jīng)了則輸出Alreadycrazy輸輸9Don'tAlready52SaturdayEat3094FridayEat063210SaturdayEat411TimusOnlineJudge,Problem1561,Winniethei類蜂蜜要xi天，對每個LearnA1x1+A2x2+…+Akxk=B(mod不同于一般方程組的是，本題中所考慮的所有方程組均是在模7意義上的。1)2)一個方3)對方程操作，直接完求一個多項式的值時，首先枚舉它的值，接著將該多項式連同枚舉的值作為一個方程加入，嘗試高斯消元，如果存在解則表示當前枚舉的值合法。最后，通過解的數(shù)目回答問題。但是該實現(xiàn)方法的第三個操作的時間復雜度是O(N3)事實上，每一次都進行高斯消元，其中的浪費是相當大的。設(shè)當前有A11x1+A12x2+…+A1kxk=B1(mod7)A21x1+A22x2+…+A2kxk=B2(mod7)A31x1+A32x2+…+A3kxk=B3(mod…Am1x1+Am2x2+…+Amkxk=Bm(mod若當前方程組已經(jīng)是經(jīng)過高斯消元的，即對j<i有Aij=0，那么新一個方程，要想當前方程組的性質(zhì)，需要對新的方程進行消元。該步驟可以在O(N2)0系數(shù)項，那么如果新方程的值B0AlreadyCrazy，不然該方程是沒有意義的，不管他。否則的話，將該方程加到這樣，每一次 操作可在O(N2)的時間內(nèi)完成斷可行性。但是這樣的代價太高，試圖優(yōu)化冗余運算。A1x1+A2x2+…+Akxk=p(mod7)0系數(shù)項是iAiixi+…+Aikxk=(A1*Aii)x1+(A2*Aii)x2+…+(Ai*Aii-Aii*Ai)xi+…+(Ak*Aii-Aik*Ai)xk=p*Aii-xp值無關(guān)，而常數(shù)項（等式右邊）最終結(jié)果必能表示為ap+b的形式。在判斷可行性時，可以姑且設(shè)出初始的p值，ap+b的p，如果存在多個則詢問有多解，如果存在一個則有唯該操作同樣經(jīng)歷了對一個方程的消元過程，時間復雜度仍然是O(N2)。消元問題至此已經(jīng)基本解決。雖然算法的時間復雜度為O(N3)，但可以分析比起一次詢問，一次方程的操作會使程序整體運行時間更長，那不妨設(shè)有t次未知數(shù)操作，1000-t次方程的操作。則總運算