题目描述

难度分:$2000$

输入$n(1 \leq n \leq 10^5)$和两个长为$n$的字符串$s$和$t$，只包含0到9以及?。

你需要把所有?都替换成0到9中的数字字符。

替换后，如果存在$i$和$j$使得$s[i] \gt t[i]$和$s[j] \lt t[j]$同时成立，则称$s$和$t$不可比。

有多少种替换?的方法，可以使$s$和$t$不可比？模$10^9+7$。

输入样例$1$

2
90
09

输出样例$1$

1

输入样例$2$

2
11
55

输出样例$2$

0

输入样例$3$

5
?????
?????

输出样例$3$

993531194

算法

容斥原理

这个题一看就觉得正面刚不如求对立事件容易。因此正难则反，求出对于所有位置$i$，都满足$s[i] \leq t[i]$或$s[i] \geq t[i]$的方案数，然后用总方案数（每个?可以填$10$种数字，总方案数为$10^{q}$，$q$为$s$和$t$串中?的总数）减去这些方案就能得到不可比的方案数。

需要注意的是，$s[i]=t[i],i \in [1,n]$既属于$s[i] \leq t[i],i \in [1,n]$也属于$s[i] \geq t[i],i \in [1,n]$，因此被减了两次，需要加回来一次。

复杂度分析

时间复杂度

最多遍历两遍字符串就可以求得答案，因此时间复杂度为$O(n)$。

空间复杂度

除了输入的$s$和$t$两个字符串，仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010, MOD = 1e9 + 7;
int n;
char s[N], t[N];

int fast_power(int a, int b) {
    int res = 1 % MOD;
    while(b) {
        if(b & 1) res = (LL)res * a % MOD;
        a = (LL)a * a % MOD;
        b >>= 1;
    }
    return res;
}


int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    int scnt = 0, tcnt = 0;
    int t1 = 0, t2 = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] != '?' && t[i] != '?') {
            if(s[i] < t[i]) t1++;
            if(s[i] > t[i]) t2++;
        }
        if(s[i] == '?') scnt++;
        if(t[i] == '?') tcnt++;
    }
    if(t1 > 0 && t2 > 0) {
        printf("%d\n", fast_power(10, scnt + tcnt));
    }else if(t1 > 0) {
        // 让所有s[i]<=t[i]
        int res = 1;
        for(int i = 1; i <= n; i++) {
            if(s[i] == '?' && t[i] == '?') {
                res = (LL)res * 55 % MOD;
            }else if(s[i] == '?') {
                res = (LL)res * (t[i] - '0' + 1) % MOD;
            }else if(t[i] == '?') {
                res = (LL)res * ('9' - s[i] + 1) % MOD;
            }
        }
        res = (fast_power(10, scnt + tcnt) - res + MOD) % MOD;
        printf("%d\n", res);
    }else if(t2 > 0) {
        // 让所有s[i]>=t[i]
        int res = 1;
        for(int i = 1; i <= n; i++) {
            if(s[i] == '?' && t[i] == '?') {
                res = (LL)res * 55 % MOD;
            }else if(s[i] == '?') {
                res = (LL)res * ('9' - t[i] + 1) % MOD;
            }else if(t[i] == '?') {
                res = (LL)res * (s[i] - '0' + 1) % MOD;
            }
        }
        res = (fast_power(10, scnt + tcnt) - res + MOD) % MOD;
        printf("%d\n", res);
    }else {
        if(scnt + tcnt < 2) {
            puts("0");
        }else {
            int less = 1, great = 1, equal = 1;
            for(int i = 1; i <= n; i++) {
                if(s[i] == '?' && t[i] == '?') {
                    less = (LL)less * 55 % MOD;
                    great = (LL)great * 55 % MOD;
                    equal = (LL)equal * 10 % MOD;
                }else if(s[i] == '?') {
                    less = (LL)less * (t[i] - '0' + 1) % MOD;      // s[i]<=t[i]
                    great = (LL)great * ('9' - t[i] + 1) % MOD;    // s[i]>=t[i]
                }else if(t[i] == '?') {
                    less = (LL)less * ('9' - s[i] + 1) % MOD;      // s[i]<=t[i]
                    great = (LL)great * (s[i] - '0' + 1) % MOD;    // s[i]>=t[i]
                }
            }
            printf("%d\n", (((fast_power(10, scnt + tcnt) - less + MOD) % MOD - great + MOD) % MOD + equal) % MOD);
        }
    }
    return 0;
}