如果两个只包含数字且长度为 \(n\) 的字符串 \(s\) 和 \(w\) 存在两个数字 \(1\leq i,j\leq n\)，使得 \(s_i<w_i,s_j>w_j\)，则称 \(s\) 和 \(w\) 是不可比的。现在给定两个包含数字和问号且长度为 \(n\) 的字符串，问有多少种方案使得将所有问号替换成0到9的数字后两个字符串是不可比的？

考虑直接对不可比的串进行dp，设\(f_i\)表示前\(i\)个字符不可比的串的个数，\(g1_i\)表示前\(i\)个字符可比的字符串且所有\(s\leq t\)的个数，\(g2_i\)表示前\(i\)个字符可比的字符串且所有\(s\geq t\)的个数，\(g3_i\)表示前\(i\)个字符可比的字符串且\(s=t\)的个数。

于是考虑转移方程：

1. \(s_i\neq ?,w_i\neq?\)

\[\begin{cases}f_i=f_{i-1}+g1_{i-1}[s_i>w_i]+g2_{i-1}[s_i<w_i]-g3_{i-1}[s_i\ne w_i]\\g1_i=g1_{i-1}[s_i\le w_i]\\g2_i=g2_{i-1}[s_i\ge w_i]\\g3_i=g3_{i-1}[s_i=w_i]\end{cases} \]

就是之前的方案乘和这一位相反的方案，但还要减去之前都相等的方案。

2. \(s_i=?,w_i\neq?\)

有一个是问号的做法是类似的，所以我只拿一个来说。

\[\begin{cases}f_i=10f_{i-1}+(9-(w_i-'0'))g1_{i-1}+(w_i-'0')g2_{i-1}-9g3_{i-1}\\g1_i=(w_i-'0'+1)g1_{i-1}\\g2_i=(9-(w_i-'0')+1)g2_{i-1}\\g3_i=g3_{i-1}\end{cases} \]

直接考虑问号会取到哪些值，然后用和上面一样的容斥处理方案。

3. \(s_i=?,w_i=?\)

\[\begin{cases}f_i=100f_{i-1}+45g1_{i-1}+45g2_{i-1}-90g3_{i-1}\\g1_i=55g1_{i-1}\\g2_i=55g2_{i-1}\\g3_i=10g3_{i-1}\end{cases} \]

多考虑一个问号，就是多用一个求和公式算算就可以了。

最后注意下\(i=1\)的时候不会构成不可比的串，所以\(f_1=0\)

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int N = 1e5;
const int p = 1e9 + 7;
using namespace std;
int n,g1[N + 5],g2[N + 5],f[N + 5],g3[N + 5];
char s[N + 5],w[N + 5];
int main()
{
    scanf("%d",&n);
    scanf("%s",s + 1);
    scanf("%s",w + 1);
    g1[0] = g2[0] = g3[0] = 1;
    for (int i = 1;i <= n;i++)
    {
        if (s[i] != '?' && w[i] != '?')
        {
            if (s[i] <= w[i])
                g1[i] = g1[i - 1];
            if (s[i] >= w[i])
                g2[i] = g2[i - 1];
            if (s[i] == w[i])
                g3[i] = g3[i - 1];
            f[i] = f[i - 1];
            if (s[i] < w[i])
                f[i] += g2[i - 1],f[i] %= p;
            if (s[i] > w[i])
                f[i] += g1[i - 1],f[i] %= p;
            if (s[i] != w[i])
                f[i] -= g3[i - 1],f[i] %= p;
        }
        if (s[i] == '?' && w[i] != '?')
        {
            f[i] = 10ll * f[i - 1] % p;
            g1[i] = 1ll * g1[i - 1] * (w[i] - '0' + 1) % p;
            g2[i] = 1ll * g2[i - 1] * (9 - (w[i] - '0') + 1) % p;
            g3[i] = g3[i - 1];
            f[i] += 1ll * g1[i - 1] * (9 - (w[i] - '0')) % p;
            f[i] %= p;
            f[i] += 1ll * g2[i - 1] * (w[i] - '0') % p;
            f[i] %= p;
            f[i] -= 9ll * g3[i - 1] % p;
            f[i] %= p;
        }
        if (s[i] != '?' && w[i] == '?')
        {
            f[i] = 10ll * f[i - 1] % p;
            g1[i] = 1ll * g1[i - 1] * (9 - (s[i] - '0') + 1) % p;
            g2[i] = 1ll * g2[i - 1] * (s[i] - '0' + 1) % p;
            g3[i] = g3[i - 1];
            f[i] += 1ll * g1[i - 1] * (s[i] - '0') % p;
            f[i] %= p;
            f[i] += 1ll * g2[i - 1] * (9 - (s[i] - '0')) % p;
            f[i] %= p;
            f[i] -= 9ll * g3[i - 1] % p;
            f[i] %= p;
        }
        if (s[i] == '?' && w[i] == '?')
        {
            f[i] = 100ll * f[i - 1] % p;
            g1[i] = 55ll * g1[i - 1] % p;
            g2[i] = 55ll * g2[i - 1] % p;
            g3[i] = 10ll * g3[i - 1] % p;
            f[i] += (45ll * g1[i - 1] % p + 45ll * g2[i - 1] % p) % p;
            f[i] %= p;
            f[i] -= 90ll * g3[i - 1] % p;
            f[i] %= p;
        }
        f[1] = 0;
    }
    cout<<(f[n] + p) % p<<endl;
    return 0;
}