考試過程：這次考試時間安排有點不合理，主要是T1影響了我的考試心态，因為我以為旁邊的人切掉了T1，是以我一直在死磕這道題，花了差不多三個小時，最後也沒什麼思路，最後打了顆線段樹拿了50分。然後就是後三個題沒時間想了，隻能打暴力，倒是沒有挂分。
但是下次的時間安排一定要合理，不要因為周圍的人影響心态。
思路：我在考場上剛開始一直在想之前做過的一道題，那道題有一個思路：若\(x\%n==y\%n\),則\(x-y\)為\(n\)的倍數。但是這道題好像并不能這麼用，我前兩個小時都在想這個，後來實在想不出，就想了一個dp，設\(f_{i,j}\)表示\(dp\)道第\(i\)位，模\(n\)餘數為\(j\)的方案是否存在，轉移就很暴力\(f_{i,j}|=f_{k,n-j}\),最後再加個線段樹優化把複雜度變成\(n^2log(n)\),得到了50分。
正解是利用字首和，因為字首和的取值隻有\(0\)到\(n-1\)的範圍，是以一定存在兩個\(i\),\(j\),滿足\(i<j\)且\(s_i==s_j\)那麼我們将\(i+1\)到\(j\)輸出即可，這顯然是對的。
代碼如下：
50pts_code
AC_code
這道題其實我覺得我是可做的，但是我在考場上沒有時間仔細想了，同時也是了解錯了題意。
1.是上次考試有一個輸入是循環節的題，我以為這也是，但是它不是。仔細分析一下資料生成就顯然了。
2.我以為\(A\)數組與每一天是對應的，但是他不是，在第一天可以閱讀\(A_n\)的書，也就是說\(A\)隻代表種類，與那一天看無關。
那麼這道題思路就很顯然了。
要想每天讀書的種類都不同 , 就要求每一種書的數目不超過其它書的數目 +1. 是以隻要看是否有一種書超過了 \((N+1)/2\). 本題空間限制很小 , 但是 N 有很大 , 是以不能用數組存下來 , 但是我們隻要找到超過\((N + 1) / 2\) 的書 , 是以我們用兩個變量 \(id\), \(cnt\), \(cnt\) 初始為 0. 然後生成每一個 \(A[i]\), 如果 \(cnt==0,\) 那麼就令 \(id=A[i]\), \(cnt=1\), 否則如果 \(id==A[i]\), 則 \(cnt++\), 如果不等于 , \(cnt--\). 最後隻要再掃一遍求出 \(id\) 的出現次數即可 .
因為如果有書超過 \((N+1)/2\), 那麼就以為這它比其他所有書的和都多 , 那麼 \(cnt\) 怎麼減都不會小于0, 如果沒有那 \(id\) 随便是哪個都沒有關系了 . 最後再求這種書要減少多少個就可以了 .
這裡解釋一下最後那個容斥的意思，顯然\(f_n=g_n\)減去不合法的方案數，那麼我們對于一個有\(n\)個點的圖，随便劃出一條線，将這個圖分成左右兩部分，我們欽定左邊的部分是合法的，右邊的部分是不合法的，那麼我們再講左右兩部分進行連邊，這條邊的邊權必須大于0，那麼一共有\(f_i\times g_i\times (k)^{i\times(n-i)}\)種方案，最後就是那個組合數，為什麼不是\(c^{i}_{n}\) ，因為我們在分組的時候，隻是随便劃了一條線，将這個集合分成了兩組，那麼可能會出現同一個點同時出現在兩邊的情況，這樣就是不合法的，那麼我們欽定一個點在左邊，那麼就不會産生這樣的情況。
再正式一點的解釋就是：我們利用“”圍繞基準點構造一個整體的“”的思想，我們可以枚舉标号為1的節點所在的聯通塊包含的節點個數\(k\),從剩下的\(n-1\)個節點中選出\(k-1\)個，與一号節點一起構成大小為\(k\)的聯通塊，顯然我們有\(c^{n-1}_{k-1}\)種選法。
最後再說一下自己的調試，首先，因為壓行導緻我把一個變量重複定義了，調了半天。
2.我在縮點後找點\(k\)的時候直接利用了之前的\(floyd\)，也就是說在沒有縮點的時候我就判斷了，但是我沒有考慮到縮點之後可能我找到的點\(K\)就被縮到同一個集合裡了。這兩個問題調了兩個多小時