ABC292G 题解

· · 题解

ABC292G-Count Strictly Increasing Sequences 题解

题意：求确定所有问号为字母并且使得这些序列字典序严格递增的方案数。n\le 40。

套路1：这类保证字典序，要求计数的题目通常是设置一个区间DP+记忆化搜索解决问题。

分析：字典序具有一些特殊性质，比如决定两个字符串大小的，只有一个字符；其前面的所有字符必须相同，后面的所有字符无所谓。

这其实就是这些序列所形成的字典树的形态计数。

但是怎么表达一棵字典树呢？观察到了字典树每个节点它子树之中所覆盖的叶子节点必然是一段连续的区间，所以使用区间DP即可解决问题。

其实用区间表达一棵树的形式也是线段树的思想，不过本题不是很涉及到它的特殊结构（比如完全二叉树的性质），不管。

套路2：如何表达一个字典树上的节点呢？我们很容易想到设置 f[l][r][k] 表示当前已经比较了前 k 个字符并且当前节点的子树之中覆盖了 [l,r] 区间的所有叶子节点的总方案数。

这题之中有涉及到字母的变换，可以一个个枚举字母，类似于背包的做法代入进去一个个处理颜色，但是码量比较大划不来。

套路3：重设状态，设 f[l][r][k][c] 表示区间 [l,r] 当前前 k 个字符相同，而它应该取的最小值是 c，然后在 [l,r] 区间也是使用背包的方法一个个处理，转移时候使用一个辅助数组 g[k][i] 当作背包的数组表示用到了第 k 种颜色而右端点为 i 的方案数。

判断方案合法可以预处理，即判断 [l,r] 区间有没有别的字母，这个时间复杂度不是瓶颈，所以实现得暴力一点也无所谓。初始值显然。

但是写个背包仍然划不来，毕竟有一些边界值的后顾之忧，码量和编码难度也比较大。

观察到背包的整个过程是一个这个 (l,r,k,c) 节点分裂成多个儿子的过程，我们记忆化搜索就是往它的子树里面搜索然后再通过平等层级的合并方法合并答案。这个过程是形如一个点分多个儿子再将其答案合并起来，而我们的背包过程是枚举其分的大小然后一个个加起来。

所以采用“左儿子右兄弟”的记录法，这样 DP 其实只需要转移两个式子即可。

可以选一些 c 这个数字，f[l][r][k][c]=\sum_{i=l}^{r-1} f[l][i][k+1][0]+f[i+1][r][k][c+1]。

可以全选 c 这个数字，也可以全不选 c 这个数字。这时的转移显然。

这个DP的过程显然采用记忆化搜索，因为简洁有力。

时间复杂度分析：O(N^3M|C|)（|C| 为字符集大小）。

#include<bits/stdc++.h>
using namespace std;typedef int I;
const I N=42,M=42;
I f[N][N][M][10],n,m;
string s[N];
const I mod=998244353;
I mul(I x,I y){return 1ll*x*y%mod;}
I dfs(I l,I r,I k,I c){
    if(c==10)return 0;
    if(k==m+1)return l==r;I&ans=f[l][r][k][c];
    if(ans^-1)return ans;
    ans=dfs(l,r,k,c+1);
    for(I i=l;i<=r;++i)
        if(s[i][k-1]=='0'+c||s[i][k-1]=='?')
            ans=(ans+(1ll*dfs(l,i,k+1,0)*(i==r?1:dfs(i+1,r,k,c+1)%mod)))%mod;
        else break;
    return ans;}
I main(){
    cin>>n>>m;
    for(I i=1;i<=n;++i)
        cin>>s[i];
    memset(f,-1,sizeof(f));
    printf("%d\n",dfs(1,n,1,0));
    return 0;
}