DP 套 DP / DFA 上 DP

· · 算法·理论

DFA 相关的理论参见 OI-Wiki。

P4590 [TJOI2018] 游园会

给定长为 k 的字符串 S。对每个 i=0,1,\cdots,k,求出满足如下要求的本质不同字符串 T 数目:

对 10^9+7 取模。

:::::success[题解]

前三条限制是容易压进 DP 状态的。我们发现 \text{LCS} 难以刻画,因为直接去算两个串的 LCS 都需要 dp。

不妨考察用于计算 LCS 的 dp。记 f_{i,j} 为 T[1:i] 与 S[1:j] 的 LCS 长度,转移为

f_{i,j}=\max(f_{i-1,j},f_{i,j-1}, f_{i-1,j-1} +[T[i]=S[j]])

对同一行的 f,根据经典结论有 f_{i,j}-f_{i,j-1} \in \{0,1\},从而考虑状压差分数组,状态数是 O(2^k) 的。我们将差分数组代表的 01 串作为 DFA 的节点。

这样,内层 DFA 的建立过程即为:枚举节点编码 \text{mask},将其还原为 DP 数组 f_i,再枚举出边字符 c,按照 DP 规则进行转移,得到新的 DP 数组 f'_i。将其压缩成 \text{mask}' 并记录转移边。

建立 LCS 的 DFA 后,设计如下外层 DP:

时空复杂度 O(2^kn)。进一步对 f 的第一维滚动数组,空间优化到 O(2^k)。

实际上,对内层 DFA 的状态进行搜索,只保留有效节点,可以得到 O(|\Sigma| n) 的复杂度,|\Sigma| 为 DFA 有效状态数。对于本题,O(2^k) 的状压已经足以通过本题。

:::::

:::::info[代码]

const int N = 4e4 + 5;
int n, k, trans[3][N];
char s[N];
int F(char c) {return c == 'N' ? 0 : c == 'O' ? 1 : 2;}
mint f[2][3][N], ans[N];
const int nxtj[3][3] = {{1, 0, 0}, {1, 2, 0}, {1, 0, 3}};

void _main() {
    cin >> n >> k >> (s + 1);
    for (int mask = 0; mask < (1 << k); mask++) {
        vector<int> f(20);
        for (int j = 1; j <= k; j++) f[j] = f[j - 1] + (mask >> (j - 1) & 1);
        for (int c = 0; c < 3; c++) {
            vector<int> g(20);
            for (int j = 1; j <= k; j++) {
                if (c == F(s[j])) g[j] = f[j - 1] + 1;
                else g[j] = max(f[j], g[j - 1]);
            }
            int& nxt = trans[c][mask];
            for (int j = 1; j <= k; j++) 
                if (g[j] - g[j - 1]) nxt |= 1 << (j - 1);
        }
    }
    f[0][0][0] = 1;
    for (int i = 1, st = 0; i <= n; i++, st ^= 1) {
        memset(f[st ^ 1], 0, sizeof(f[st ^ 1]));
        for (int j = 0; j < 3; j++) 
            for (int mask = 0; mask < (1 << k); mask++)
                for (int c = 0; c < 3; c++) {
                    if (nxtj[j][c] >= 3) continue;
                    f[st ^ 1][nxtj[j][c]][trans[c][mask]] += f[st][j][mask];
                }
    }
    for (int mask = 0; mask < (1 << k); mask++) 
        for (int j = 0; j < 3; j++) ans[popcount(mask)] += f[n & 1][j][mask];
    for (int i = 0; i <= k; i++) cout << ans[i] << '\n';
} 

:::::

XXS0103 局部函数

记 U=\{0,1,2,3\}。现有 n 个变量 x_i \in U,初始 x_i=a_i 且 x_0=x_{n+1}=0。另给定 n 个二元函数 g_i : U^2 \to U。

考虑 1\sim n 的排列 p_i,对 i=1,2,\cdots,n 依次执行如下操作:

  • 记 k=p_i,令 x_k \gets g_k(x_{k-1},x_{k+1})。

对所有排列 p,求可得 x_1 \sim x_n 最终序列的数目。取模 998244353。

:::::success[题解]

一个基本的刻画是,考虑相邻项 u,v,若 x_u 的更新时刻早于 x_v 则连边 u \to v,建图是有向链。

取任意拓扑序均可得到唯一的 x_1 \sim x_n。考虑 O(4^n) 枚举 x_1 \sim x_n,根据上述刻画设计内层 DP:

只要记录 (x_{i-1},x_i,f_{0,i-1}, f_{1,i-1}) 四元组,内层 DP 就能建模为 DFA,状态信息量 4^2 \times 2^2=64。考虑外层 DP:

复杂度 O(k^3 n),其中 k=4。代码。

:::::

P16415 【MX-X28-T4】「FAOI-R12」落花雨

给定长为 n 的 01 串 S。若 |S| \ge 2 可以选择相邻数 x,y,删去 x,y 后插入新数 x \text{ nor } y。求任意次操作后可以得到的不同 01 串数目,取模 998244353。

多测,\sum n \le 10^6,2 秒,512 MB。

:::::success[题解]

枚举最终串 T 并判定 S \to T 是否合法。判定条件是,将 S 划分为 |T| 个非空子串,使得子串内经 \text{nor} 合并后可以变为对应的单个 0 或 1。

通过打表观察,若 n \ge 4 则任意串都能变为单 0 和 1,无法变换的串只有以下 10 种:

考虑可行性 DP,设 f_i 表示 S 的 (i,n] 后缀是否匹配 T 的后缀。在 T 的前端添加字符 c \in \{0,1\} 时,有转移

f_i \gets \bigvee_{j>i \land S(i,j]\to c} f_j

从右向左加所有字符,若 f_0=1 则 T 合法。内层 DP 是 NFA,可以状压 \{i \mid f_i=1\} 转化为 DFA。

根据性质,长度 \ge 4 的串必然存在合法划分,故 f_j \to f_i 对 i \le j-4 恒成立,只保留最大的 j\sim j-3 就能转移。故 DFA 的节点可以构造为二元组 (m,X):

内层 NFA 的状态数为 n \times 2^4,转移 (m,X) \to (m',X') 可以枚举 10 种特殊情况 O(1) 算出。

设计如下外层 DP:

状态数 16 \times n,转移 2 \times 10,总复杂度 O(20 \times 16 \times n),注意常数问题。代码。

:::::