ABC292G Count Strictly Increasing Sequences [区间DP]

Description

你有 \(n\) 个数，每个数长度为 \(m\)。

不过这 \(n\) 个数中，可能有某些位不确定，需要你在每个 ? 位置上 \(0\) 到 \(9\) 之间填一个数。设你填出来的序列是 \(\{S_i\}\)。

请你求出，在所有可能的填数方案中，有多少种满足 \(S_1 < S_2 < \dots < S_n\)？对 \(998244353\) 取模。允许前导零存在。

\(n,m \le 40\)。

Solution

推性质：

我们考虑一个合法的序列长什么样，它的每个数的最高位可能是这样的，111...222...333...444......999,

其中，最高位的数严格递增，即可保证序列严格递增，那如果最高位相等，就要求往后一位（去掉最高位后）严格递增。

设状态：

设 \(f(i,j,l,r)\) 表示，当前考虑了后 \(i\) 位（越靠前的位权越高）（\(i\) 是 \(m\) 这一维的），\([l,r]\) （是 \(n\) 这一维的） 这个区间的数严格递增，且当前填的最大的数是 \(j\)，的方案数。

举个例子：\(12345，12356，12378，12390\)，\(f(2,1,4,9)\) 就表示 \([1,4]\) 的数，\(45<56<78<90\)，且最大的数是 \(\max\{4,5,7,9\}\)。

写转移：

我们枚举一个 \(k\)，表示 \([l,k]\) 的数严格递增，\([k+1,r]\) 的数最高位相等，

转移即是：\(f(i,j,l,r)=\sum f(i,j-1,l,k)\times f(i+1,9,k+1,r)\)，

含义就是，既然 \([l,k]\) 的数严格递增，于是我们就直接算上它的贡献，然后再保证 \([k+1,r]\) 严格递增，保证的方法就是让它上一位严格递增。

然后 \(j\) 这一维是可以用滚动数组滚掉的。

时间：\(O(n^3m\left|\sum\right|)\)，空间：\(O(n^3)\)。

Code

const int N = 40 + 5, mod = 998244353;

int n, m;
string s[N];
int f[N][N][N], g[N][N][N]; // 滚动数组

void Solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> s[i];
		s[i] = " " + s[i];
	}
	for(int i = 1; i <= n; i++) f[m + 1][i][i] = 1; // 边界
	for(int i = m; i >= 1; i--){
		for(int j = 0; j <= 9; j++){
			memcpy(g[i], f[i], sizeof(f[i]));
			for(int len = 1; len <= n; len++){
				for(int l = 1; l + len - 1 <= n; l++){
					int r = l + len - 1;
					bool flag = true;
					for(int k = r; k >= l; k--){
						if(s[k][i] == '?' || s[k][i] == j + '0'){
							if(k == l) break;
							f[i][l][r] = (1ll * f[i][l][r] + 1ll * g[i][l][k - 1] * f[i + 1][k][r] % mod) % mod;
						}else{
							flag = false;
							break;
						}
					} // 个人代码实现，最后需要特判整个区间都相等，不必纠结
					if(flag) f[i][l][r] = (1ll * f[i][l][r] + f[i + 1][l][r]) % mod;
				}
			}
		}
	}
	cout << f[1][1][n] << endl;
}