題意：給你兩個數字串，其中可以包含'?'，求將兩個數字串變成不可比較的數字串有多少種方案。（不可比較當且僅當存在i,j,使得s[i]<w[i]&&s[j]>w[j])。
題意理解清楚後，就知道這題其實就是一道排列組合的題目了。
[cpp]
//排列組合
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
const int M=1000000007;
char s[N],w[N];//輸入字符串
int n;
int main()
{
int cnt;//'?'個數
int small,big;
while(~scanf("%d",&n))
{
cnt=0;
small=big=0;
scanf("%s%s",s,w);
for(int i=0;i<n;i++)
{
if(s[i]=='?'||w[i]=='?')
{
if(s[i]=='?')
cnt++;
if(w[i]=='?')
cnt++;
}
else
{
if(s[i]<w[i])
small=1;//s[i]<w[i]
else if(s[i]>w[i])
big=1;//s[i]>w[i]
}
}
if(small==1&&big==1)//除'?'以外的其它字符已經符合題意，則'?'可以隨意替換
{
long long ans=1;
for(int i=1;i<=cnt;i++)
ans=ans*10%M;
printf("%d\n",ans);
}
else if(cnt==0)//無'?'
printf("0\n");
else if(cnt==n*2)//全'?'
{
long long sum,tmp1,tmp2;
sum=tmp1=tmp2=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=1;i<=n;i++)
{
tmp1=tmp1*55%M;//大於或等於
tmp2=tmp2*10%M;//等於
}
sum=(sum-tmp1*2+tmp2+M*2)%M;
printf("%d\n",sum);
}
else
{
if(small)//小於或等於
{
long long sum=1,tmp=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=0;i<n;i++)
{
if(s[i]=='?'&&w[i]=='?')
tmp=tmp*55%M;
else if(s[i]=='?')
tmp=tmp*(w[i]-'0'+1)%M;
else if(w[i]=='?')
tmp=tmp*(10-(s[i]-'0'))%M;
}
sum=(sum-tmp+M)%M;
printf("%d\n",sum);
}
else if(big)//大於或等於
{
long long sum=1,tmp=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=0;i<n;i++)
{
if(s[i]=='?'&&w[i]=='?')
tmp=tmp*55%M;
else if(s[i]=='?')
tmp=tmp*(10-(w[i]-'0'))%M;
else if(w[i]=='?')
tmp=tmp*(s[i]-'0'+1)%M;
}
sum=(sum-tmp+M)%M;
printf("%d\n",sum);
}
else
{
long long sum,tmp1,tmp2,tmp3;
sum=tmp1=tmp2=tmp3=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=0;i<n;i++)
{
if(s[i]=='?'&&w[i]=='?')
{
tmp1=tmp1*55%M;
tmp2=tmp2*55%M;
tmp3=tmp3*10%M;
}
else if(s[i]=='?')
{
tmp1=tmp1*(10-(w[i]-'0'))%M;
tmp2=tmp2*(w[i]-'0'+1)%M;
}
else if(w[i]=='?')
{
tmp1=tmp1*(s[i]-'0'+1)%M;
tmp2=tmp2*(10-(s[i]-'0'))%M;
}
}
sum=(sum-tmp1-tmp2+tmp3+M*2)%M;
printf("%d\n",sum);
}
}
}
return 0;
}
//排列組合
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
const int M=1000000007;
char s[N],w[N];//輸入字符串
int n;
int main()
{
int cnt;//'?'個數
int small,big;
while(~scanf("%d",&n))
{
cnt=0;
small=big=0;
scanf("%s%s",s,w);
for(int i=0;i<n;i++)
{
if(s[i]=='?'||w[i]=='?')
{
if(s[i]=='?')
cnt++;
if(w[i]=='?')
cnt++;
}
else
{
if(s[i]<w[i])
small=1;//s[i]<w[i]
else if(s[i]>w[i])
big=1;//s[i]>w[i]
}
}
if(small==1&&big==1)//除'?'以外的其它字符已經符合題意，則'?'可以隨意替換
{
long long ans=1;
for(int i=1;i<=cnt;i++)
ans=ans*10%M;
printf("%d\n",ans);
}
else if(cnt==0)//無'?'
printf("0\n");
else if(cnt==n*2)//全'?'
{
long long sum,tmp1,tmp2;
sum=tmp1=tmp2=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=1;i<=n;i++)
{
tmp1=tmp1*55%M;//大於或等於
tmp2=tmp2*10%M;//等於
}
sum=(sum-tmp1*2+tmp2+M*2)%M;
printf("%d\n",sum);
}
else
{
if(small)//小於或等於
{
long long sum=1,tmp=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=0;i<n;i++)
{
if(s[i]=='?'&&w[i]=='?')
tmp=tmp*55%M;
else if(s[i]=='?')
tmp=tmp*(w[i]-'0'+1)%M;
else if(w[i]=='?')
tmp=tmp*(10-(s[i]-'0'))%M;
}
sum=(sum-tmp+M)%M;
printf("%d\n",sum);
}
else if(big)//大於或等於
{
long long sum=1,tmp=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=0;i<n;i++)
{
if(s[i]=='?'&&w[i]=='?')
tmp=tmp*55%M;
else if(s[i]=='?')
tmp=tmp*(10-(w[i]-'0'))%M;
else if(w[i]=='?')
tmp=tmp*(s[i]-'0'+1)%M;
}
sum=(sum-tmp+M)%M;
printf("%d\n",sum);
}
else
{
long long sum,tmp1,tmp2,tmp3;
sum=tmp1=tmp2=tmp3=1;
for(int i=1;i<=cnt;i++)
sum=sum*10%M;
for(int i=0;i<n;i++)
{
if(s[i]=='?'&&w[i]=='?')
{
tmp1=tmp1*55%M;
tmp2=tmp2*55%M;
tmp3=tmp3*10%M;
}
else if(s[i]=='?')
{
tmp1=tmp1*(10-(w[i]-'0'))%M;
tmp2=tmp2*(w[i]-'0'+1)%M;
}
else if(w[i]=='?')
{
tmp1=tmp1*(s[i]-'0'+1)%M;
tmp2=tmp2*(10-(s[i]-'0'))%M;
}
}
sum=(sum-tmp1-tmp2+tmp3+M*2)%M;
printf("%d\n",sum);
}
}
}
return 0;
}
