DP 套 DP / DFA 上 DP
stripe_python · · 算法·理论
DFA 相关的理论参见 OI-Wiki。
P4590 [TJOI2018] 游园会
给定长为
k 的字符串S 。对每个i=0,1,\cdots,k ,求出满足如下要求的本质不同字符串T 数目:
对
10^9+7 取模。
:::::success[题解]
前三条限制是容易压进 DP 状态的。我们发现
不妨考察用于计算 LCS 的 dp。记
对同一行的
这样,内层 DFA 的建立过程即为:枚举节点编码
建立 LCS 的 DFA 后,设计如下外层 DP:
- 记
f_{i,j,\text{mask}} 为满足如下条件时,合法的T 的数目: -
- 转移
f_{i,j,\text{mask}} \to f_{i,j',\text{mask}'} 。枚举出边字符c ,分别更新j' 和\text{mask}' ,其中\text{mask}' 由内层 DFA 走出边得到。对j' \ge 3 的转移忽略。 - DP 初值为
f_{0,0,0}=1 ,其中\text{mask}=0 为内层 DFA 起点的编码。 - 答案为
\text{ans}_k=\sum \limits_{\text{popcount}(\text{mask})=k} \sum\limits_{j=0 }^2 f_{n,j,\text{mask}} 。利用\text{popcount} 的原因是,\text{mask} 中1 的数目恰好等价于\text{LCS}(S,T) 。
时空复杂度
实际上,对内层 DFA 的状态进行搜索,只保留有效节点,可以得到
:::::
:::::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[题解]
一个基本的刻画是,考虑相邻项
取任意拓扑序均可得到唯一的
- 设
f_{0/1,i} 为满足下列条件时,是否存在合法定向方案:-
- 仅考虑
x_0 \sim x_i 。
-
- 转移分讨
f_{0/1,i-1} \to f_{0/1,i} 是否可行,只要根据a_i,x_i 和g_i 判定。 - DP 初值为
f_{{\tt{R}},0}=1 。 - 答案为
f_{{\tt{L}},n} 。
只要记录
- 设
f_{u,v,f_0,f_1,i} 为满足下列条件的方案数:-
-
- 仅考虑
x_0 \sim x_i 。
-
- 转移枚举
x_{i+1} 的取值,可算出新的(u',v',f_0',f_1') ,转移f_{u,v,f_0,f_1,i-1} \to f_{u',v',f_0',f_1',i} 即可。 - DP 初值为
f_{0,v,0,1,0}=1 。 - 答案为
\sum\limits_{u,f_1} f_{u,0,1,f_1,n} 。
复杂度
:::::
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[题解]
枚举最终串
通过打表观察,若
- 无法变为
0 :1、00、010; - 无法变成
1 :0、01、10、11、000、101、111。
考虑可行性 DP,设
从右向左加所有字符,若
根据性质,长度
内层 NFA 的状态数为
设计如下外层 DP:
- 设
g_{m,X} 表示走到状态(m,X) 的路径数。 - 转移枚举
c \in \{0,1\} 并得到出边(m',X') ,令g_{m,X} \to g_{m',X'} 。 - DP 初值为
g_{n,1}=1 。表示仅f_n=1 从而X=1 。 - 答案为
f_0=1 的所有g 的和,即m \ge 4 或者m<4 且X 的对应位为1 。
状态数
:::::