A/B按題意模擬即可。nAnBC注意到共要走  步，每步有兩個方向可選，共  種情況。n由于  ，故  ，故爆搜即可。nCD顯然的，顏色在本題中是無效

A/B

按題意模擬即可。
nA
nB

C

注意到共要走 步，每步有兩個方向可選，共 種情況。
n由于 ，故 ，故爆搜即可。
nC

D

顯然的，顏色在本題中是無效的變量，實際題意如下：

給定一張無向圖，保證任意一點度不超過 ，無重邊、自環，
n求環的數量和非環的連通塊數。

其實已經可以 了，但我不想寫，所以再觀察下。

由于任意一點度不超過 ，因此連通塊只有點、鏈、環三種可能。
n其中，滿足每個點度數都為 的聯通塊才是環。
n因此考慮并查集，對于每個點維護度數，最后再求出每個連通塊的點的最小度數即可。
nD

E

首先考慮暴力。設 ，
n則有 ，邊界值
n此時發現 的值僅和 有關，因此考慮到矩陣快速冪。
n我們可以對 構造如下矩陣：

則每次遞推相當于乘上如下矩陣:

每次乘完 即可。

題目至此已經解決了
n嗎？

交上去，會發現 。。。
n問題在哪？

在 邊界值 。
n因為原題數據范圍為
n因此還要特判 的情況。。。
nE 和 四發罰時

F

好像是有結論的？
n不重要。
n暴力可以解決一切~

注意到對于不同進制 ， 的 進制表示法顯然不同，
n可以得出以下兩種暴力：

1. 枚舉進制 ，判斷 的 進制表示法是否只由 和 構成，時間復雜度
2. 枚舉 的表示法，二分是否有滿足此表示法的 。看似更優了，可時間復雜度仍為 。

此時已經可以通過 左右，我們接著考慮 時的做法。

接著，我們發現對于第一種暴力，當進制 時，有且僅有 和 兩種答案。從第二個暴力的角度，我們發現當 時 最多只有以下 種表示法：
n10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111，因此考慮將兩種暴力結合，先使用第二種暴力判段以上 種表示方法，再使用第一種方法枚舉 的情況，復雜度為 ，已經可以通過此題。
n若是將特判擴大更多以尋找平衡點可以有更優的復雜度，此處不在討論。
nF
nPS：一定要處理好二分邊界!

G

一眼莫隊。
n具體的，一個點加入區間的貢獻為增加的同顏色三元組數，由于這個點加在邊界處，貢獻即為加入前已有點的兩元組數，為
n
n刪除時同理。
nG
nPS：一定是 組詢問，不是 組！一定是 組詢問，不是 組！一定是 組詢問，不是 組！……

Ex

感覺是換根 ？還沒做出來，待會來補。

本文使用 Zhihu On VSCode 創作并發布