某島

… : "…アッカリ~ン . .. . " .. .
March 26, 2020

Educational Codeforces Round 84

F. AND Segments

按位分離後是一個非常經典的計數問題。
AND 等於 1 的情況,那麼這個區間必須都必須填 1。
AND 等於 0 的情況,那麼這個區間必須不全為 1。

我們設 f[i] 表示第 i 位一定填 0 時的方案數,那麼最後答案就是 f[n+1]。
那麼對於情況一,有 f[i] = 0。
對於情況二,我們枚舉最右邊 0 的位置,以避免重複計數,一定是一些形如 …011110 的 Pattern 累加,既 f[i] = sigma f[j]。

我們只要維護最大的合法的 j,並用前綴和優化轉移即可。

https://codeforces.com/contest/1327/submission/74341283

G. Letters and Question Marks

每個字元只能用一次,顯然狀態壓縮 AC 自動機 DP,
dp[i][u][s] 表示,當前在文本串的位置為 i,在自動機的位置為 u,已經使用的字符集合為 s。

複雜度略微有點高,我們注意到只有遇到問號的時候,字符集合才會變化,於是我們用問號劃分階段,每次預處理之間的字元串整體轉移即可。

https://codeforces.com/contest/1327/submission/74333174