WA on #11
查看原帖
WA on #11
398152
MinimumSpanningTree最小生成树楼主2024/6/8 21:42
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int N=100100;
int n,a[N],b[N];
ll ans=1,cnt1=1,cnt2=1,cnt3=1;
string s1,s2;
int main()
{
	scanf("%d",&n);
	cin>>s1>>s2;
	for(int i=1;i<=n;i++)
	{
		if(s1[i-1]=='?') a[i]=-1,ans*=10;
		else a[i]=s1[i-1]-'0';
		if(s2[i-1]=='?') b[i]=-1,ans*=10;
		else b[i]=s2[i-1]-'0';
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]==-1&&b[i]==-1) cnt1=(cnt1*55)%MOD;
		else if(a[i]==-1) cnt1=(cnt1*(10-b[i]))%MOD;
		else if(b[i]==-1) cnt1=(cnt1*(a[i]+1))%MOD;
		else if(a[i]<b[i])
		{
			cnt1=0;
			break;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]==-1&&b[i]==-1) cnt2=(cnt2*55)%MOD;
		else if(a[i]==-1) cnt2=(cnt2*(b[i]+1))%MOD;
		else if(b[i]==-1) cnt2=(cnt2*(10-a[i]))%MOD;
		else if(a[i]>b[i])
		{
			cnt2=0;
			break;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]==-1&&b[i]==-1) cnt3=(cnt3*10)%MOD;
		else if(a[i]!=-1&&b[i]!=-1&&a[i]!=b[i])
		{
			cnt3=0;
			break;
		}
	}
	ans=(ans+MOD*2-cnt1-cnt2+cnt3)%MOD;
	printf("%lld",ans);
	return 0;
}
2024/6/8 21:42
加载中...