题目链接：点击打开链接
题意：
给出长度为n的2个数字串S ,T（有些位置为?表示可以随便填数字）
求：有多少种填充方式使得 S[i]>T[i] && S[j] <T[j]
思路：
先求出ans表示所有填充方式，ans = 10^num, num为2个串?的总个数
dp[0][i]表示长度为i 且对于任意的 j( 1<=j<=i)满足 S[j]<=T[j] 的填充方案数
dp[1][i] 表示 S[j]==T[j]
dp[2[i] 表示 S[j]>=T[j]
则答案= ans - dp[0][n] - dp[1][n] + dp[2][n];
#include<bits/stdc++.h>
const int inf = 1e8;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int mod = 1e9+7;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) { putchar('-');x = -x; }
if(x>9) pt(x/10);
putchar(x%10+'0');
}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5+10;
int n;
char s[2][N];
ll dp[3][N];
void mul(ll &x, ll y){
x = (x*y)%mod;
}
void add(ll &x, ll y){
x = (x+y)%mod;
}
int main()
{
while(cin>>n){
scanf("%s", s[0]+1);
scanf("%s", s[1]+1);
ll ans = 1;
for(int i = 0; i < 3; i++)dp[i][0] = 1;
ll a, b, c;
for(int i = 1; i <= n; i++){
if(s[0][i] == '?' && s[1][i] == '?')
{
a = c = 45; b = 10;
mul(ans, 100);
}
else if(s[0][i] == '?')
{
mul(ans, 10);
a = s[1][i]-'0';
b = 1;
c = 9-a;
}
else if(s[1][i] == '?')
{
mul(ans, 10);
c = s[0][i]-'0';
b = 1;
a = 9-c;
}
else {
a = s[0][i]<s[1][i];
b = s[0][i]==s[1][i];
c = s[0][i]>s[1][i];
}
dp[0][i] = dp[0][i-1]*(a+b)%mod;
dp[1][i] = dp[1][i-1]*b%mod;
dp[2][i] = dp[2][i-1]*(b+c)%mod;
}
ans -= dp[0][n];
ans -= dp[2][n];
ans += dp[1][n];
ans %= mod;
if(ans<0)add(ans, mod);
pt(ans%mod); puts("");
}
return 0;
}Codeforces 296B Yaroslav and Two Strings dp+容斥(入门
原文：http://blog.csdn.net/qq574857122/article/details/44892069