直接求incomparable很复杂...反过来算..先算情况总数sum,和comparable的总数...sum-comparable=incomparable
求comparable用动态规划....dp[a][b] .....b为0代表0~a..上下关系为全等的方法数..
b为1代表0~a..上面的大于下面的方法数..
b为2代表0~a..上面的小于下面的方法数..
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<algorithm> #define ll long long #define oo (ll)1000000007 using namespace std; ll n,dp[2][3],sum; char s1[100005],s2[100005]; int main() { // freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,k,x,p1,p2; scanf("%I64d%s%s",&n,&s1,&s2); memset(dp,0,sizeof(dp)); k=0; sum=1; dp[0][0]=1; // 0上下等 1上大下小 2上小下大 for (x=0;x<n;x++) { k=1-k; memset(dp[k],0,sizeof(dp[k])); if (s1[x]=='?') { if (s2[x]=='?') { sum=(sum*100)%oo; dp[k][0]=(dp[1-k][0]*10)%oo; dp[k][1]=(dp[1-k][0]*45+dp[1-k][1]*55)%oo; dp[k][2]=(dp[1-k][0]*45+dp[1-k][2]*55)%oo; }else { sum=(sum*10)%oo; p2=s2[x]-'0'; dp[k][0]=dp[1-k][0]; dp[k][2]=(dp[1-k][0]*p2+dp[1-k][2]*(p2+1))%oo; p2=9-p2; dp[k][1]=(dp[1-k][0]*p2+dp[1-k][1]*(p2+1))%oo; } }else if (s2[x]=='?') { sum=(sum*10)%oo; p1=s1[x]-'0'; dp[k][0]=dp[1-k][0]; dp[k][1]=(dp[1-k][0]*p1+dp[1-k][1]*(p1+1))%oo; p1=9-p1; dp[k][2]=(dp[1-k][0]*p1+dp[1-k][2]*(p1+1))%oo; } else { if (s1[x]==s2[x]) { dp[k][0]=dp[1-k][0]; dp[k][1]=dp[1-k][1]; dp[k][2]=dp[1-k][2]; }else if (s1[x]>s2[x]) dp[k][1]=(dp[1-k][0]+dp[1-k][1])%oo; else dp[k][2]=(dp[1-k][0]+dp[1-k][2])%oo; } } sum=(3*oo+sum-dp[k][0]-dp[k][1]-dp[k][2])%oo; printf("%I64d\n",sum); return 0; }