某岛

… : "…アッカリ~ン . .. . " .. .
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