Codeforces 296 B. Yaroslav and Two Strings http://codeforces.com/problemset/problem/296/B 容斥原理

CF296B.cpp

/*
a[i],b[i],c[i],d[i]分别表示 、ch1[i]<=ch2[i]的情况数、
ch1[i]>=ch2[i]的情况数、ch1[i]==ch2[i]的情况数看，
所有的情况数。那么根据容斥原理，
有ans = sum(d) - sum(a) - sum(b) + sum(c)
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

const int maxn = 100100;
const int mod = 1000000007;

int a[maxn], b[maxn], c[maxn], d[maxn];
int n;
char ch1[maxn], ch2[maxn];

void get(char x, char y, int i) {
	if (x == '?' && y == '?') {
		a[i] = b[i] = 55;
		c[i] = 10; d[i] = 100;
	} else if (x == '?') {
		a[i] = y - '0' + 1;
		b[i] = 11 - a[i];
		c[i] = 1; d[i] = 10;
	} else if (y == '?') {
		b[i] = x - '0' + 1;
		a[i] = 11 - b[i];
		c[i] = 1; d[i] = 10;
	} else {
		if (x <= y) a[i] = 1;
		if (x >= y) b[i] = 1;
		if (x == y) c[i] = 1;
		d[i] = 1;
	}
}

int main() {
	scanf("%d %s %s", &n, ch1, ch2);
	for (int i = 0; i < n; i++) {
		get(ch1[i], ch2[i], i);
	}
	long long ans1 = 1, ans2 = 1, ans3 = 1, ans4 = 1;
	for (int i = 0; i < n; i++) {
		ans1 *= a[i]; ans1 %= mod;
		ans2 *= b[i]; ans2 %= mod;
		ans3 *= c[i]; ans3 %= mod;
		ans4 *= d[i]; ans4 %= mod;
	}
	long long ans = (ans4 - ans1 - ans2 + ans3) % mod;
	if (ans < mod) ans += mod;
	cout << ans << endl;
	return 0;

}