#公告 MCC Round #2 題解

程式設計板 {{ articleMoment(createdAt) }}

首先先公佈名次： http://codeforces.com/group/cQT9NVfHrA/contest/216252/standings/groupmates/true 第一名：軟男不是暖男 (16384M幣) 第二名：Takumi (8192M幣) 第三名：加西亞 (4096M幣) 第四～六名：小鳥紳士、莫測、gsmaster (各2048M幣) 參加獎：LuLuSaBee (1024M幣) 獎勵應該都發出去了，請查收 比賽時在看計分板的時候才發現每一題的陷阱都比想像中多啊… 也因為這樣讓大家沒辦法好好寫後面兩題 後面兩題我花很久準備的說ＱＱ（第四題還要自己寫checker） 有時間可以繼續挑戰，不要讓題目浪費掉了（測資都公開的） 總之請大家下次要繼續支持！ A. A^B問題 對不起我以為次方的末位數會以四為單位循環是常識😱 做個實驗找找規律其實也能發現 總之A留下末位數 B=4K+N就當作B=N就好，N=1~4 特例是B=0，這時不管A是多少末位數都是1😂 當然你高興的話也可以寫個快速冪，學過的話也不難寫（而且第五題需要） http://codeforces.com/group/cQT9NVfHrA/contest/216252/submission/31148622 B. 排數字 首先注意到只要除以三剩下的餘數是一樣的，那這些數在這個問題裡就可以當成同樣的數。所以先統計除以三的餘數分別是0,1,2的各有多少個，令它們為a0、a1和a2。 相鄰兩數總和為三的倍數可以分成兩類：兩個都餘0或一個餘1一個餘2。 如果a0>a1+a2+1，那麼不管怎麼排一定會有兩個餘0的數相鄰。 如果a1≠0, a2≠0, a0=0，那麼不管怎麼排一定會有餘1和餘2的數相鄰。 如果這兩項都不符合，那就一定有解。構造方法如下： 如果沒有餘0的數，那就全部排成一列。否則把所有餘1的數排成一列，之後接著所有餘2的數，中間以一個餘0的數分隔，之後把所有剩下的餘0的數兩兩不相鄰的插入這一列數當中就完成了。 http://codeforces.com/group/cQT9NVfHrA/contest/216252/submission/31148636 C. 子序列 首先你要先想到這題要用動態規劃 然後狀態定義應該就不難想到：a[i] = 考慮"meteor"的前幾個字，如果這是最後一個字的話有幾種方法。 轉移式應該也可以推出來：檢查這個字元之前的所有字元，看看能不能從那個字接到這個字。 不過因為'e'有兩個，所以遇到'e'時需要分別考慮這個'e'要當第一個或第二個。我的作法是如果當第二個就儲存在b[i]裡面。 最後要記得使用long long！ ＊bonus：如果長度最大到10^5(10^6也可以)，你還會做嗎？（留下除以10^9+7的餘數）＊ http://codeforces.com/group/cQT9NVfHrA/contest/216252/submission/31148643 D. 最短死路 直接做DFS一定會超時 首先先想想看答案的長度最大會到多少 就算起點距離邊界很遠，也可以用八步自己把自己困住： 2 3 4 1 8 5 0 7 6 前提是空間足夠，所以N<3、M<3、起點在角落或是N=3,M=3,X=2,Y=2都不能使用這種方法，其他都可以。 如果在邊上或是角落，可以用最多六步： ———（邊界） 1 6 5 2 3 4 前提是N>1且M>1。 (3, 3, 2, 2)一定要用九步，而N=1或M=1則有可能用更多步。 不過這樣的資訊已經足夠了，就從起點開始DFS，同時要記錄目前版面的狀態，如果長度到九還沒被困住就不要再繼續做了（N=1或M=1例外，要做到底） 被困住之後如果長度小於目前紀錄的最小值，就更新最小值和最終答案。 http://codeforces.com/group/cQT9NVfHrA/contest/216252/submission/31148652 E. 正多邊形 應該不難想到O(NK)的dp作法，這裡就不多說了，會太慢 透過觀察可以發現最後的位置其實只和走了幾步順時針方向（走了幾步逆時針方向也能知道）有關而已。最後可以走回原點當且僅當兩種方向的差是N的倍數。 然後就可令i為滿足「走幾步順時針方向會走回原點」的所有值，則C(K, i)的總和即為答案。 要計算C(K, i)，需要先預處理所有階乘（除以10^9+7的餘數），然後再透過計算乘法反元素得出K!/(i!(K-i)!)除以10^9+7的值。 一個數在模10^9+7的情況下的反元素其實就是那個數的10^9+5次方，可用快速冪求出這個值。 想要了解更多可以參考以下網站： http://www.csie.ntnu.edu.tw/~u91029/Residue.html#1 http://codeforces.com/group/cQT9NVfHrA/contest/216252/submission/31148659